The Exercise

Three random variables $X$, $Y$ and $Z$ take values in finite sets $\mathcal{X}$, $\mathcal{Y}$ and $\mathcal{Z}$ and have a joint distribution $p(x,y,z)$. Suppose they form a Markov chain $X \to Y \to Z$, as when $Y$ is the output of a noisy channel fed with $X$ and $Z$ is produced from $Y$ alone. The exercise is to show that the same variables, taken in the opposite order, also form a Markov chain $Z \to Y \to X$.

In the library the Markov condition is an identity between $p$ and three of its marginals, and the reversed chain is the triple $(Z,Y,X)$ with the reversed distribution.

Marginals and the Markov Condition

The second marginal $q_V$ of a joint distribution $q$ of two random variables $U$ and $V$ is the distribution of $V$ alone, obtained by summing out $U$: $$q_V(v) = \sum_{u} q(u,v).$$(1)^✦ With $X$ as the first variable and the pair $(Y,Z)$ as the second, the second marginal of $p$ is the marginal of $(Y,Z)$, $p_{YZ}(y,z) = \sum_x p(x,y,z)$.

The middle marginal $p_Y$ of $p$ is the distribution of $Y$ alone, obtained from $p_{YZ}$ by summing out $Z$: $$p_Y(y) = \sum_{z} p_{YZ}(y,z).$$(2)^✦ Summing $Z$ out of $p$ itself gives the marginal $p_{XY}$ of the pair $(X,Y)$, their joint distribution: $$p_{XY}(x,y) = \sum_{z} p(x,y,z).$$(3)^✦

Three random variables $X$, $Y$, $Z$ with joint distribution $p$ form a Markov chain $X \to Y \to Z$ when $X$ and $Z$ are conditionally independent given $Y$, that is, when $$p(x,y,z)\, p_Y(y) = p_{XY}(x,y)\, p_{YZ}(y,z) \qquad \text{for all } x, y, z.$$(4)^✦

The reversed distribution $\tilde p$ of $p$ is the joint distribution of the triple $(Z,Y,X)$ on $\mathcal{Z} \times \mathcal{Y} \times \mathcal{X}$ that gives each reversed triple of values the weight of the original one: $$\tilde p(z,y,x) = p(x,y,z).$$(5)^✦ Its marginals $\tilde p_{ZY}$, $\tilde p_{YX}$ and $\tilde p_Y$ are formed as in (1) to (3), with $Z$ in the first place and $X$ in the last.

The Claim

What Is Checked

The claim is stated over the Markov condition (4), built from the marginals (1) to (3), and over the reversed distribution (5). What the library proves about these constructions is the theorem above, for every real function $p$ on $\mathcal{X} \times \mathcal{Y} \times \mathcal{Z}$ and not only for probability distributions.