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.
Builds on
Not sure where to start? Take the ten-question placement test.