Data Processing Inequality

For a Markov chain X → Y → Z, I(X; Z) ≤ I(X; Y) — processing can only destroy information.

The idea

Theorem (Data processing inequality).

If $X \to Y \to Z$ is a Markov chain, meaning that $Z$ depends on $X$ only through $Y$, so that $X$ and $Z$ are conditionally independent given $Y$, then $I(X; Z) \le I(X; Y).$

However $Z$ is produced from $Y$ — by a deterministic function, an algorithm, or a computation that adds its own randomness — $Z$ cannot carry more information about $X$ than $Y$ does, because each of these produces a $Z$ that reaches $X$ only through $Y$.

The inequality does not say an estimate of $X$ cannot improve; a good algorithm applied to $Y$ beats reading $Y$ directly. It says the total information about $X$ available downstream was fixed at the moment $Y$ was recorded, and later processing can only repackage that information or lose some of it.

This is why the inequality is the standard tool for proving impossibility results: model the pipeline as a chain, bound the mutual information at its narrowest link, and conclude that no later stage exceeds that bound.

Ways to work on it

• Walkthrough. Prove the data-processing inequality from the mutual-information chain rule and check the equality condition.
• Practice. Compute the effective crossover probability of a cascade of binary symmetric channels.
• Hardest. Decide what the data-processing inequality implies in a range of settings.

Not sure where to start? Take the ten-question placement test.