$X, Y_1, Y_2$ are random variables with (possibly) different finite alphabets. For given conditional probability mass functions $\mathbb{P}(Y_1|X)$ and $\mathbb{P}(Y_2|X)$, is it always possible to find joint conditional probabilities $\mathbb{P}(Y_1, Y_2|X)$ such that $X\rightarrow Y_1\rightarrow Y_2$ is a Markov chain? Outline the procedure please. The set of joint probabilities need not be unique, but is at least one set guaranteed to exist?

P. S. The problem is basically taken from the context of broadcast channel capacity where I am trying to prove that any two user scalar broadcast channel can be converted to an equivalent degraded channel. I tried my best to present it in a way so that someone not familiar with information theory can appreciate the problem. Let me know if I left anything unclear.


Not always. For a slightly degenerate example, assume that $X$, $Y_1$ and $Y_2$ take values in $\{+,-\}$ with $Y_1=Y_2=+$ if $X=+$ and $Y_1=+$ and $Y_2=-$ if $X=-$.

The paths of the triple $(X,Y_1,Y_2)$ are $(+,+,+)$ and $(-,+,-)$ hence the distribution of $Y_2$ conditionally on $(X,Y_1)$ depends on $X$, that is, $(X,Y_1,Y_2)$ cannot be a Markov chain.

For a less degenerate example, assume that $Y_1$ conditionally on $X$ is $+$ with probability $1-p$ and $-$ with probability $p$, independently of $X$, and that $Y_2$ conditionally on $X$ is $X$ with probability $1-p$ and $-X$ with probability $p$. One can then check that, for every $p\ne\frac12$, the process $(X,Y_1,Y_2)$ cannot be made into a Markov chain.


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.