1
$\begingroup$

EDIT. I'm adding a missing hypothesis and a really TL;DR version of the core problem. Warning: This short statement is the strongest form of what I want, hence not as plausible as the original form.

I'll try to state the problem as succinctly as I can and afterwards I'll give some motivation for it.

Assume $(S, \Sigma)$ is a standard Borel space, and for each $s\in S$, $T(s)$ is a set of two probability measures $\{\mu_s,\nu_s\}\subseteq P(S)$ on $S$ such that
each measurable set $ \xi\subseteq P(S)$, $$ \{s : \mu_s\in\xi\} \cup \{s : \nu_s\in\xi\} $$ is in $\Sigma$. Is there any way to find choice functions $s\mapsto \mu_s\in T(s)$ and $s\mapsto \nu_s\in T(s)$ such that both of the sets appearing in the union are measurable for each $s$?


Original statement.

Given a measurable space $(S, \Sigma)$, the set  $P(S)$ of probability measures on $S$ also is a measurable space with $\sigma$-algebra generated by the sets $$ \beta (<q,Q) \doteq \{ \mu\in P(S) : \mu (Q)<q\} $$ with $Q\in\Sigma $ and $q $ a rational.

A Markov kernel is a measurable map $\tau: S\to P(S)$, and a nondeterministic kernel is, in turn,  a  function $T: S\to \mathrm{Pow}(P(S))$ such that for each measurable set of measures $ \xi\subseteq P(S)$, the set $\{s : T_a(s) \cap \xi \neq \emptyset\} $ is in $\Sigma$. I'm mainly interested in the case where all the sets $T (s)$ are countable.

Now assume that $(S, \Sigma)$ is standard Borel, i.e., it is the Borel space of a separable completely metrizable topological space. (Thanks @MichaelGreinecker for pointing this hypothesis out.) It can be shown that if the sets $T(s)$ are finite then they are of the form $$ \{ \tau_n(s): n \in\mathbb{N}\}, $$ where each $\tau_n$ is a Markov kernel. Note that, although we have a sequence of kernels, for each $s$ we might nevertheless have a finite set of measures.  This follows from Kuratowski & Ryll-Nardzewski selection theorem.

For the sake of simplicity, assume that for all $s$ we have $|T(s)|=2$.

Question. Can one do with just two Markov kernels? Or finitely many?

That is, given a nondeterministic kernel  $T$ with $|T(s)|=2$ for all $s$, are there finitely Markov kernels  $\tau_n$ ($1\leq n \leq N $) such that $$ T(s)=\{ \tau_n(s): 1\leq n \leq N \}? $$


Background. In Computer Science, Markov decision processes have been used to model situations where a user interacts with a system having probabilistic behaviour. The  labelled Markov DPs have a measurable space $(S, \Sigma)$ as its set of states and for each $a $ in a set $L $ of labels, a transition probability, i.e., a function $\tau_a: S\times\Sigma\to [0,1] $ such that $\tau_a(s,\cdot): \Sigma\to [0,1] $ is  a probability measure on $S$ for each $s $ and $\tau_a(\cdot,Q): S\to [0,1] $ is a measurable map for each  $Q $. This is exactly the same as a Markov kernel.

There is nondeterministic version of labelled Markov processs (i.e., a probabilistic generalization of Kripke frames or labeled transition systems) for which the main ingredient is an indexed family $T_a$ ($a\in L$) of nondeterministic kernels. Associated to these processes we have a modal logic that allows to express properties of the form “there is a transition with label $a$ such that the probability to reach a state in which the property $\phi$ holds is less than $q$”. This is written as $\langle a\rangle_q \phi$, and a state satisfies this formula if belongs to the set $$ \{s : T_a(s) \cap \beta (<q,[\!| \phi |\!])\neq \emptyset\}, $$ where $[\!| \phi |\!]$ is the set of states that satisfy $\phi$.

When one wants to express more complex properties, such that $\langle b\rangle_p\langle a\rangle_q \phi$, one needs to require the measurability condition on kernels discussed above.

$\endgroup$
2
  • $\begingroup$ Why are the assumptions of the Kuratowski & Ryll-Nardzewski selection theorem satisfied here? $\endgroup$ Jul 23, 2015 at 21:48
  • $\begingroup$ @MichaelGreinecker Right, that's not true as stated. I forgot to add the hypothesis that $S$ is standard Borel. I'll edit the question accordingly. $\endgroup$ Jul 24, 2015 at 3:48

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.