Concatenating two Markov chains

238 Views Asked by At

Consider three discrete random variables $X$, $Y$, and $Z$ with corresponding probability mass functions $p(x)$, $p(y)$, and $p(z)$.

Let $X \rightarrow Y$ (i.e., $X$ and $Y$ form a Markov chain in that order) and $Y \rightarrow Z$ (i.e., $Y$ and $Z$ form a Markov chain in that order). Is it true that $X \rightarrow Y \rightarrow Z$? Do $X$, $Y$, and $Z$ form a Markov chain? That is, is it the case that $p(x,y,z) = p(x)p(y|x)p(z|y)$?

1

There are 1 best solutions below

1
On

Yes!

This can be proven as follows:

If $X \rightarrow Y \rightarrow Z$, then,

$p(x,y)\\ = \sum_{z} p(x,y,z)\\ = \sum_{z} (p(x)p(y|x)p(z|y))\\ = p(x)p(y|x) \sum_{z} (p(z|y))\\ = p(x)p(y|x)$.

Similarly,

$p(y,z)\\ = \sum_{x} p(x,y,z)\\ = \sum_{x} (p(x)p(y|x)p(z|y))\\ = p(z|y) \sum_{x} (p(x)p(y|x))\\ = p(z|y) \sum_{x} \left(p(x) \frac{p(x,y)}{p(x)}\right)\\ = p(z|y) \sum_{x} (p(x,y))\\ = p(z|y)p(y)$.

Thus $X \rightarrow Y \rightarrow Z$ implies $X \rightarrow Y$ and $Y \rightarrow Z$. The other side of the implication is trivial as both $X \rightarrow Y$ and $Y \rightarrow Z$ refer to the same $Y$.