# Double Markovity

Suppose we have a double Markov relation for three random variables $X$, $Y$ and $W$ as follows $$X\to W\to Y,$$ and $$X\to Y\to W.$$

How to prove that there exist functions $f$ and $g$ such that $$X\to f(Y)\to Y, W$$ and $$\Pr(f(Y)=g(W))=1?$$

• Could you please specify what are domains and ranges of these functions? – R W Jul 28 '14 at 22:09
• does this mean you can have markov relation x->w->y->w->y->w->...? – guest Jul 28 '14 at 22:10
• @RW, the problem asks for the existence of some functions $f$ and $g$ with domains $\mathcal{X}$ and $\mathcal{W}$ which are the alphabets over which two random variables $X$ and $W$ are defined. The ranges can be anything. – math-Student Jul 28 '14 at 22:51
• @geust, I dont know what you mean by the Markov relation you mention .... – math-Student Jul 28 '14 at 22:53
• Do you mean that you have three random variables $X$,$Y$ and $W$ all defined on the same probability space, such that $\mathbb P(Y=y|X=x,W=w)=\mathbb P(Y=y|W=w)$ and $\mathbb P(W=w|X=x,Y=y)=\mathbb P(W=w|Y=y)$? – Anthony Quas Jul 28 '14 at 22:53

I think I could prove the existence of such functions but however, I can not show that we must have $X\to f(Y)\to Y, W$. However the proof for the first part might give some insight for the latter.
Suppose random variables $X$, $Y$ and $W$ are defined over alphabets $\mathcal{X}$, $\mathcal{Y}$ and $\mathcal{W}$.
Note than we can write $P_{X|YW}(\cdot|y, w)=P_{X|Y}(\cdot|y)=P_{X|W}(\cdot| w)$ from the double Markov relation. Now define $E_{x}:=\{y:~P_{X|Y}(x|y)=P_{X|Y}(x|1)\}$. Since $1\in E_{x}$, we have $P_{Y}(E_{x})>0$. The fact that $P_{Y}(E_{x})=1$ for all $x\in\mathcal{X}$ implies that $X$ and $Y$ are independent. Hence if they are not independent, then there exist $x_0\in\mathcal{X}$ such that $0<P_Y(E_{x_0})<1$. Now setting $F:=\{w:~P_{X|W}(x_0|w)=P_{X|Y}(x_0|1)\}$, we conclude from the fact $P_{X|Y}(\cdot|y)=P_{X|W}(\cdot|w)$ that $P_{YW}(E_{x_0}^c\times F)=P_{YW}(E_{x_0}\times F^c)=0$.
Hence there exist some subsets of $\mathcal{Y}$ and $\mathcal{W}$ like $E$ and $F$ such that each $(y, w)$ belong to each of $E\times F$. Let $J$ be the random variable which indexes this subsets. It is clear that $J$ is a deterministic function of $Y$ and $W$ and so there exist functions $f$ and $g$ such that $J=f(Y)=g(W)$.
• The random variable $J$ defined above can be shown to be equal to Gacs-Korner common information. – math-Student Jul 30 '14 at 2:56