TITLE: On Optimality of Deterministic and Non-Deterministic Transformations
SPEAKER: Roman Belavkin (Middlesex University)

ABSTRACT:

Dynamical systems can be modelled by Markov semigroups, and we use Markov transition kernels to model computational machines and algorithms.  We study points on a simplex of all joint probability measures corresponding to various types of transition kernels.  In particular, deterministic or non-deterministic (e.g. randomised) algorithms correspond respectively to boundary or interior points of the simplex.  The performance of the corresponding systems is evaluated by expected cost (or expected utility), which is a linear functional. The domain of optimisation is defined by information constraints.  We use our result on mutual absolute continuity of optimal measures to show that optimal transition kernels cannot be deterministic, unless information is unbounded.  As an illustration, we construct an example where any deterministic kernel can only have unbounded expected cost, unless the information constraint is removed.  On the other hand, a non-deterministic kernel can have finite expected cost under the same information constraint.