Markov Chains and partial views/Coarsenings

From GusWiki

[edit] definition of coarsening

Given two Markov chains, $Z$ taking values in and $Y$ taking values in , $Y$ is a coarsening of $Z$ when there exists a function such that $Y(t) = f(Z(t))$.

(More formally yet, $Z$ is a measurable function from the basic probability space Ω to , such that the induced measure on the space of paths (i.e. on ) has the Markov property. Thus $Z(t)$ is really Z(t,ω). Another stochastic process $Y$ is a Markovian coarsening of $Z$ when $Y$ is also a Markov chain, and there exists an $f$ such that, for all $t$ and ω, Y(t,ω) = f(Z(t,ω)). This may be weakened to "for almost all ω" without real loss.)

The necessary and sufficient condition for coarsening is as follows. Let $P(z,z')$ be the transition matrix for $Z$, i.e., $Pr(Z(t+1)=z'|Z(t)=z)=P(z,z')$. For a set , define Let $C = \{C_1, C_2, \ldots C_m\}$ be a partition of . By a slight abuse of notation, let $C$ also be the canonical mapping from to this partition. Then the stochastic process $Y$, defined by $Y(t) = C(Z(t))$, is a Markov chain, and hence a coarsening of $Z$, if and only if

for all $C_i$ in $C$

for all $C_j$ in $C$,

for all $z, z'$ in $C_i$

$P(z,C_j) = P(z',C_j)$

In words, all ways of entering a cell $C_i$ leave us with the same distribution over future cells $C_j$.

[edit] The next step

The next step for us is to specialize to the case where we want to be a product space, and we want to each coordinate projection to be Markovian. That is, each $z$ is really $(x,y)$, and the mapping $C$ is just $(x,y) \mapsto x$ (say). So our constraint is that

for all

for all

for all

∑	P((x,y),(x',u)) =	∑	P((x,y'),(x',u))
u		u

In fact, we want

∑	P((x,y),(x',u)) = Q(x,x')
u

for a stochastic matrix $Q$ which we specify. Similarly,

∑	P(x,y),(v,y')) = R(y,y')
v

for another stochastic matrix $R$.

For example, and , with the transition matrices being respectively

$Q(a,.) = (0.5, 0.5)$

$Q(b,.) = (0.75, 0.25)$

i.e.

$R(A,.) = (0.3,0.7)$

$R(B,.) = (0.7,0.3)$

i.e.

Now by taking P to be the Kronecker product we can get something which coarsens to both the respective chains.

But if we modify the first row of this to be

$P(aA,aA) = 0.1$

$P(aA,aB) = 0.4$

$P(aA,bA) = 0.2$

$P(aA,bB) = 0.3$

i.e.

i.e.

then unless I have made an arithmetic mistake, we have a valid Markov chain which still coarsens to the Markov chains whose transition matrices are $Q$ and $R$.