Data Processing Inequality
The data processing inequality is a foundational theorem of information theory stating that no deterministic or randomized processing of data can increase the mutual information between that data and any variable it is correlated with. Formally, if X → Y → Z forms a Markov chain — meaning Z depends on X only through Y — then I(X;Y) ≥ I(X;Z). The inequality is intuitively obvious and mathematically profound: every stage of processing is an irreversible act of compression, and compression cannot create information that was not already present.
The inequality has devastating consequences for naive theories of artificial intelligence and data analytics. It means that no algorithm, however sophisticated, can extract from a dataset information that the dataset does not contain. A machine learning model trained on biased data cannot, by any computational magic, discover the unbiased truth. The data processing inequality is the mathematical warrant for the slogan 'garbage in, garbage out' — but it is stronger than the slogan, because it applies even when the input is not garbage, merely incomplete. The inequality is the information-theoretic boundary that separates inference from invention.
When the Inequality Fails — and What It Reveals
The data processing inequality holds under specific conditions: the processing must be a Markov kernel, and the mutual information must be computed with respect to a fixed probability distribution. When these conditions are violated, the inequality can fail — and the failures are as instructive as the theorem itself.
In quantum information theory, the data processing inequality is replaced by a subtler set of constraints. Quantum channels can preserve or even increase certain quantum correlations that have no classical analog, and the monotonicity of quantum relative entropy under completely positive trace-preserving maps is the quantum generalization of the classical result. The classical inequality is not violated in the quantum domain; it is transcended. The quantum case reveals that the classical inequality was never about information per se, but about classical probability distributions — a narrower domain than physicists sometimes assume.
A different kind of apparent violation occurs in the presence of side information. If the processing of Y into Z has access to additional variables correlated with X but not part of the Markov chain X → Y → Z, then I(X;Z) can exceed I(X;Y). This is not a violation of the theorem; it is a violation of the theorem's assumptions. The Markov condition fails because Z depends on X through channels other than Y. But the confusion is common enough — particularly in machine learning, where models regularly incorporate auxiliary features — that it deserves explicit mention. The data processing inequality does not say that no processing can increase predictive power; it says that no processing of Y alone can increase the information that Y carries about X.
The most philosophically interesting limit of the inequality arises in the context of causal inference. Judea Pearl's do-calculus demonstrates that interventions — which are not mere observations — can change the causal structure of a system in ways that passive data analysis cannot capture. The data processing inequality governs observation; it does not govern intervention. An experimenter who intervenes on Y can break the Markov chain and establish new information channels that the inequality does not constrain. This distinction between observation and intervention is the boundary where the data processing inequality ends and causal reasoning begins.
The data processing inequality is often invoked as a universal limit on what algorithms can achieve, but this invocation mistakes a theorem about probability distributions for a theorem about the world. The inequality tells us what information a dataset contains; it does not tell us what information the world contains. The gap between the two — between the data we have and the reality that produced it — is where science, engineering, and occasionally luck operate. To treat the data processing inequality as a bound on discovery is to confuse the map with the territory, and to forget that the most important information is often the information we have not yet thought to collect.