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?$$

  • $\begingroup$ Could you please specify what are domains and ranges of these functions? $\endgroup$ – R W Jul 28 '14 at 22:09
  • $\begingroup$ does this mean you can have markov relation x->w->y->w->y->w->...? $\endgroup$ – guest Jul 28 '14 at 22:10
  • $\begingroup$ @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. $\endgroup$ – math-Student Jul 28 '14 at 22:51
  • $\begingroup$ @geust, I dont know what you mean by the Markov relation you mention .... $\endgroup$ – math-Student Jul 28 '14 at 22:53
  • 1
    $\begingroup$ 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)$? $\endgroup$ – 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)$.

  • $\begingroup$ The random variable $J$ defined above can be shown to be equal to Gacs-Korner common information. $\endgroup$ – math-Student Jul 30 '14 at 2:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.