The Data Processing Inequality

Markovity

A Markov Chain is a random process that describes a sequence of possible events where the probability of each event depends only on the outcome of the previous event. Thus, we say that $X,Y,Z$ is a Markov chain in this order, denoted as:

$X\rightarrow Y\rightarrow Z$

(1)

If we can write:

$P\left(X=x,Y=y,Z=z\right)=P\left(Z=z\mid Y=y\right)\cdot P\left(Y=y\mid X=x\right)\cdot P\left(X=x\right)$

(2)

Or in a more compact form:

$P\left(x,y,z\right)=P\left(z\mid y\right)\cdot P\left(y\mid x\right)\cdot P\left(x\right)$

(3)

We can use Markov chains to model how a signal is corrupted when passed through noisy channels. For example, if $X$ is a binary signal, it can change with a certain probability, $p$, to $Y$, and it can again be corrupted to produce $Z$.

Consider the joint probability $P\left(x,z\mid y\right)$. We can express this as:

$P\left(x,z\mid y\right)={\frac {P\left(x,y,z\right)}{P\left(y\right)}}$

(4)

And if $X\rightarrow Y\rightarrow Z$, we get:

$P\left(x,z\mid y\right)={\frac {P\left(z\mid y\right)\cdot P\left(y\mid x\right)\cdot P\left(x\right)}{P\left(y\right)}}$

(5)

Since $P\left(y,x\right)=P\left(y\mid x\right)\cdot P\left(x\right)=P\left(x\mid y\right)\cdot P\left(y\right)$, we can write:

$P\left(x,z\mid y\right)={\frac {P\left(z\mid y\right)\cdot P\left(y,x\right)}{P\left(y\right)}}=P\left(z\mid y\right)\cdot P\left(x\mid y\right)$

(6)

Thus, we can say that $X$ and $Z$ are conditionally independent given $Y$. If we think of $X$ as some past event, and $Z$ as some future event, then the past and future events are independent if we know the present event $Y$. Note that this property is good definition of, as well as a useful tool for checking Markovity.

We can rewrite the joint probability $P\left(x,y,z\right)$ as:

${\begin{aligned}P\left(x,y,z\right)&=P\left(z\mid y\right)\cdot P\left(y\mid x\right)\cdot P\left(x\right)\\&={\frac {P\left(z,y\right)}{P\left(y\right)}}\cdot P\left(y,x\right)\\&={\frac {P\left(z,y\right)}{P\left(y\right)}}\cdot P\left(x\mid y\right)\cdot P\left(y\right)\\&=P\left(z,y\right)\cdot P\left(x\mid y\right)\\&=P\left(x\mid y\right)\cdot P\left(y\mid z\right)\cdot P\left(z\right)\\\end{aligned}}$

(7)

Therefore, if $X\rightarrow Y\rightarrow Z$, then it follows that $Z\rightarrow Y\rightarrow X$.

Entropy Chain Rules

Figure 1: Entropy visualization for two random variables using Venn diagrams.

As we increase the number of random variables we are dealing with, it is important to understand how this increase affects entropy. We have previously shown that for two random variables $X$ and $Y$:

${\begin{aligned}H\left(X,Y\right)&=H\left(X\right)+H\left(Y\mid X\right)\\&=H\left(Y\right)+H\left(X\mid Y\right)\\&=H\left(Y,X\right)\end{aligned}}$

(8)

We can use Venn diagrams to visualize these relationships, as seen in Fig. 1. For three random variables $X$, $Y$, and $Z$:

${\begin{aligned}H\left(X,Y,Z\right)&=H\left(X\right)+H\left(Y,Z\mid X\right)\\&=H\left(X\right)+H\left(Y\mid X\right)+H\left(Z\mid Y,X\right)\\\end{aligned}}$

(9)

In general:

$H\left(X_{1},X_{2},\ldots ,X_{n}\right)=\sum _{i=1}^{n}H\left(X_{i}\mid X_{i-1},X_{i-2},\ldots ,X_{1}\right)$

(10)

Conditional Mutual Information

Conditional mutual information is defined as the expected value of the mutual information of two random variables given the value of a third random variable, and for three random variables $X$, $Y$, and $Z$, it is defined as:

${\begin{aligned}I\left(X;Y\mid Z\right)&=\sum _{z\in Z}P\left(z\right)\sum _{y\in Y}\sum _{x\in X}P\left(x,y\mid z\right)\cdot \log _{2}{\frac {P\left(x,y\mid z\right)}{P\left(x\mid z\right)\cdot P\left(y\mid z\right)}}\\&=\sum _{z\in Z}\sum _{y\in Y}\sum _{x\in X}P\left(x,y,z\right)\cdot \log _{2}{\frac {P\left(x,y,z\right)\cdot P\left(z\right)}{P\left(x,z\right)\cdot P\left(y,z\right)}}\\\end{aligned}}$

(11)

We can rewrite the definition of conditional mutual information as:

${\begin{aligned}I\left(X;Y\mid Z\right)&=\sum _{z\in Z}\sum _{y\in Y}\sum _{x\in X}P\left(x,y,z\right)\cdot \log _{2}{\frac {P\left(x,y,z\right)\cdot P\left(z\right)}{P\left(x,z\right)\cdot P\left(y,z\right)}}\\&=\sum _{z\in Z}\sum _{y\in Y}\sum _{x\in X}P\left(x,y,z\right)\cdot \left(\log _{2}{\frac {P\left(z\right)}{P\left(x,z\right)}}-\log _{2}{\frac {P\left(y,z\right)}{P\left(x,y,z\right)}}\right)\\&=\sum _{z\in Z}\sum _{y\in Y}\sum _{x\in X}P\left(x,y,z\right)\cdot \log _{2}{\frac {P\left(z\right)}{P\left(x,z\right)}}-\sum _{z\in Z}\sum _{y\in Y}\sum _{x\in X}P\left(x,y,z\right)\cdot \log _{2}{\frac {P\left(y,z\right)}{P\left(x,y,z\right)}}\\&=\sum _{y\in Y}P\left(y\right)\sum _{z\in Z}\sum _{x\in X}P\left(x,z\mid y\right)\cdot \log _{2}{\frac {P\left(z\right)}{P\left(x,z\right)}}-\sum _{z\in Z}\sum _{y\in Y}\sum _{x\in X}P\left(x,y,z\right)\cdot \log _{2}{\frac {P\left(y,z\right)}{P\left(x,y,z\right)}}\\&=\sum _{z\in Z}\sum _{x\in X}P\left(x,z\right)\cdot \log _{2}{\frac {P\left(z\right)}{P\left(x,z\right)}}-\sum _{z\in Z}\sum _{y\in Y}\sum _{x\in X}P\left(x,y,z\right)\cdot \log _{2}{\frac {P\left(y,z\right)}{P\left(x,y,z\right)}}\\&=H\left(X\mid Z\right)-H\left(X\mid Y,Z\right)\\\end{aligned}}$

(12)

Figure 2: Entropy visualization for three random variables using Venn diagrams.

We can visualize this relationship using the Venn diagrams in Fig. 2. Compare this to our expression for the mutual information of two random variables $X$ and $Y$:

$I\left(X;Y\right)=H\left(X\right)-H\left(X\mid Y\right)$

(13)

Chain Rule for Mutual Information

For random variables $X$ and $Z$:

$I\left(X;Z\right)=H\left(X\right)-H\left(X\mid Z\right)$

(14)

And for random variables $X$, $Y$ and $Z$:

$I\left(X;Y,Z\right)=H\left(X\right)-H\left(X\mid Y,Z\right)$

(15)

We can then express the conditional mutual information as:

${\begin{aligned}I\left(X;Y\mid Z\right)&=H\left(X\mid Z\right)-H\left(X\mid Y,Z\right)\\&=H\left(X\right)-I\left(X;Z\right)+I\left(X;Y,Z\right)-H\left(X\right)\\&=I\left(X;Y,Z\right)-I\left(X;Z\right)\\\end{aligned}}$

(16)

Rearranging, we then obtain the chain rule for mutual information:

$I\left(X;Y,Z\right)=I\left(X;Y\mid Z\right)+I\left(X;Z\right)$

(17)

Thus, we can extend this for additional random variables:

${\begin{aligned}I\left(Y;X_{1},X_{2},X_{3}\right)&=I\left(Y;X_{3}\mid X_{2},X_{1}\right)+I\left(Y;X_{2},X_{1}\right)\\&=I\left(Y;X_{3}\mid X_{2},X_{1}\right)+I\left(Y;X_{2}\mid X_{1}\right)+I\left(Y;X_{1}\right)\\\end{aligned}}$

(18)

In general:

$I\left(Y;X_{1},X_{2},\ldots ,X_{n}\right)=\sum _{i=1}^{n}I\left(Y;X_{i}\mid X_{i-1},X_{i-2},\dots ,X_{1}\right)$

(19)

The Data Processing Inequality

Consider a Markov chain, $X\rightarrow Y\rightarrow Z$.