AI Glossary / Probabilistic machine learning / Intermediate
Data processing inequality
Definition
The data processing inequality states that processing an observation cannot increase its mutual information about an upstream variable when the processing has no additional access to that variable. Formally, if X → Y → Z is a Markov chain, then I(X; Z) ≤ I(X; Y).
What it means
Suppose X is an underlying signal, Y is a measurement, and Z is a processed version of that measurement. The Markov condition says that once Y is known, Z does not receive extra information about X. Z may be a deterministic transformation of Y or a randomized transformation using independent randomness.
The theorem concerns statistical information, measured by mutual information. It does not say processing is useless. A good representation can make relevant information easier for a person or limited-capacity algorithm to use, even though it cannot create additional information about X from Y alone.
How it works
Mutual information measures how much knowing one variable reduces uncertainty about another. The chain rule lets us express information in the pair (Y, Z) in two ways: I(X; Y, Z) = I(X; Y) + I(X; Z | Y), and also I(X; Z) + I(X; Y | Z).
Under the Markov condition, I(X; Z | Y) is zero. Therefore I(X; Y) − I(X; Z) = I(X; Y | Z), which is nonnegative. This establishes the inequality.
Equality is possible when Z preserves all of Y's information relevant to X. The result does not require every processing step to lose information strictly. Related data-processing results apply to divergences when the same channel acts on two distributions.
Three practical examples
- Data compression: evaluate whether a reduced representation preserves information needed for a target task, recognizing that discarded evidence cannot be recovered from that representation alone.
- Feature engineering: transform measurements into features that make a prediction problem easier without claiming that the transformation adds new evidence about the target.
- Communication systems: reason about how additional noisy stages can preserve or reduce information about a transmitted signal, unless another source of information is introduced.
Think of it this way
Think of copying a document into a shorter set of notes. Good notes may be easier to understand and may retain everything needed for a particular question. But notes created only from that document cannot contain new evidence about its subject. The analogy is bounded: mutual information is a property of a joint probability distribution, not a count of words, apparent detail, or human understanding.
Worked example
Consider an original example where X = (A, B) consists of two independent fair bits. Its entropy is 2 bits. Let Y reveal only A. Then I(X; Y) = 1 bit: knowing A leaves B unknown.
Now create Z by keeping Y with probability 0.75 and replacing it with an erasure symbol “?” with probability 0.25. The erasure decision is independent of A and B. This gives the Markov chain X → Y → Z.
When Z is 0 or 1, one bit of uncertainty about X remains. When Z is “?”, both bits remain unknown. Hence H(X | Z) = 0.75 × 1 + 0.25 × 2 = 1.25 bits. Therefore I(X; Z) = 2 − 1.25 = 0.75 bits, below the original 1 bit.
The output Z has three possible symbols while Y has only two. A larger output alphabet therefore does not imply more information about X. The extra erasure randomness adds possible outputs without adding signal evidence.
Illustrative case study
Fictional case: Alder Forecasting compresses a set of sensor measurements into a few features. A simple predictor performs better on those features than on the raw inputs because it is easier to fit with the available data and training procedure.
The team does not claim this violates the data processing inequality. It distinguishes predictive performance of a particular learner from the information available in the full measurements. Analysts also retain a test set to check whether the improvement generalizes. The example illustrates model limitations and representation choices, not a measured company result.
Common misconceptions and mistakes
The inequality does not say every deterministic function destroys information. An invertible transformation can preserve it, and a noninvertible statistic can preserve all information relevant to a particular target.
It also does not say output entropy can never increase: added randomness can increase uncertainty in the output while reducing its information about the signal. Mutual information and entropy are different quantities.
If processing uses side information correlated with X, the simple chain may no longer apply. A model using external measurements or relevant learned information must include those inputs in the analysis rather than pretending it used Y alone.
Business use
For businesses, the result helps separate making information usable from creating new evidence. Summaries, embeddings, dashboards, and denoised outputs can improve workflows, but their usefulness should not be confused with an unlimited ability to reconstruct omitted facts.
Identify the actual inputs and target, and validate what the chosen representation preserves. If information is lost during collection or irreversible aggregation, downstream sophistication may not repair it. Where an output introduces new details, determine whether they come from additional evidence, prior assumptions, or generated guesses.
People also ask
Does data processing always reduce information?
It cannot increase the specified mutual information under the Markov condition, but equality is possible.
Can denoising improve prediction?
Yes. It can help a particular predictor use existing information or incorporate additional assumptions. That is different from violating the theorem.
Does the result apply to one individual sample?
It is a statement about distributions and mutual information, not a guarantee that every single processed observation is less useful in every practical sense.
Check your understanding
Let Z be an invertible recoding of Y, such as replacing each symbol with a unique new label. Does the inequality require strict information loss?
Answer: No. Since Y can be recovered exactly from Z, the two carry the same information about X, and I(X; Z) = I(X; Y).
Related terms
- Mutual information
- Markov Chain
- Conditional independence
- Entropy
- Sufficient statistic
- information bottleneck
- lossless transformation
- KL divergence
Learn next
Learn entropy and mutual information using small probability tables. Then calculate the erasure example and prove the inequality with the chain rule. Next, compare invertible recoding, lossy compression, and processing with side information to see exactly when the assumptions change.
More in Probabilistic machine learning
- Coupling flow - A coupling flow is a normalizing flow built from invertible coupling transformations.
- Covariance graph - A covariance graph is a graphical representation of marginal independence assumptions, commonly expressed through zeros in a Gaussian covariance matrix.
- Covariance matrix adaptation evolution strategy - Covariance matrix adaptation evolution strategy, or CMA-ES, is a randomized method for optimizing functions of continuous parameters without requiring their...
- Data tempering - Data tempering is a Bayesian computational strategy that moves through a sequence of posterior distributions by gradually incorporating observations or...
- Deadly triad in reinforcement learning - The deadly triad in reinforcement learning is the combination of function approximation, bootstrapping, and off-policy learning.
- Deep ensemble - A deep ensemble combines predictions from several trained deep neural networks.
Sources
John Duchi, original Lecture Notes on Statistics and Information Theory, section 2.1.3, data processing inequalities: https://web.stanford.edu/class/stats311/lecture-notes.pdf Independent source review: Duchi section 2.1.3, Proposition 2.1.9 and its chain-rule proof, plus the adjacent KL contraction statement, were read.
Previous: Data privacy Next: Data proliferation