Data processing inequality

The data processing inequality is a fundamental theorem in information theory stating that no processing of data can increase the information it contains about some underlying variable. Formally, for any Markov chain X → Y → Z, the mutual information satisfies I(X;Z) ≤ I(X;Y). Information about X can only be preserved or lost as it passes through processing stages; it can never be created.

This is not merely a technical result. It is a boundary condition on all systems that process information — biological, social, or artificial. Every filter, every algorithm, every institutional procedure that transforms data into decisions is subject to this inequality. The data processing inequality is the information-theoretic expression of a deeper principle: you cannot get more out than you put in, and what you get out is always less than or equal to what you had at the intermediate stage.

Formal Statement

Let X, Y, Z be random variables forming a Markov chain X → Y → Z, meaning that Z is conditionally independent of X given Y: P(Z|Y,X) = P(Z|Y). The data processing inequality states:

I(X;Z) ≤ I(X;Y)

where I(·;·) denotes mutual information. A stronger form applies to relative entropy: for any two distributions P and Q on X, and any Markov kernel P(Y|X), the Kullback-Leibler divergence satisfies D(P(Y)||Q(Y)) ≤ D(P(X)||Q(X)). Processing reduces the distinguishability of distributions.

The Proof and Its Intuition

The proof relies on the chain rule for mutual information: I(X;Y,Z) = I(X;Z) + I(X;Y|Z) = I(X;Y) + I(X;Z|Y). Since X and Z are conditionally independent given Y, I(X;Z|Y) = 0. Therefore I(X;Z) = I(X;Y) - I(X;Y|Z). Since conditional mutual information is non-negative, I(X;Z) ≤ I(X;Y).

The intuition is that Y is a "processed" version of X, and Z is a further processing of Y. Each processing stage can only preserve or destroy information; it cannot create new information about X that was not already present in Y. This is why the inequality is called the data processing inequality: it formalizes the impossibility of information alchemy.

Implications

The data processing inequality is the mathematical foundation of the Good Regulator theorem. Conant and Ashby's proof uses the inequality to show that a regulator must contain as much information about disturbances as the system would otherwise transmit to the essential variables. The regulator cannot create information it does not possess; it can only block the transmission of information from disturbance to essential variable.

In machine learning, the inequality explains why feature extraction cannot create information that was not present in the raw data. A neural network's hidden layers can only preserve or lose information about the target variable; they cannot invent new information. This is why data quality matters more than model complexity: a model cannot compensate for information that was never in the training data.

The inequality also underlies the information bottleneck method, which seeks to compress a representation Y of input X while preserving information about a target variable T. The bottleneck is the data processing inequality itself: you cannot compress Y without losing some information about X, and the art is to lose only the irrelevant information.

The Editor's Claim

The data processing inequality is the information-theoretic equivalent of the second law of thermodynamics, and it is treated with the same casual disrespect. Every day, data scientists claim to have "discovered" patterns in data that their preprocessing pipeline has manufactured. Every day, institutional reports claim to have "extracted insights" from data that their filtering algorithms have systematically distorted. The inequality is not a failure of technique; it is a law. And like all laws, it is most dangerous when it is ignored by those who believe they are above it.