Relative entropy and data processing

For finite laws P and Q on one alphabet, define D(P||Q) as the P-weighted logarithm of their probability ratio. We use base two, so the value is in bits. A point with positive P probability and zero Q probability makes divergence infinite. Zero P terms contribute zero. Nonnegativity follows from the logarithm inequality or convexity; equality occurs exactly when the two probability laws agree, including their supported masses.

Interchanging P and Q changes both the weights and the ratio, so divergence is not generally symmetric. It also lacks a metric triangle inequality. Its coding interpretation is precise: using ideal lengths based on Q instead of the true P costs D(P||Q) expected bits beyond the entropy of P, before integer code-length overhead. That statement needs Q positive wherever P is positive; a proposed code assigning zero probability to an observed symbol has no finite ideal description length.

Let K be one stochastic kernel applied to either input law. Summing over the unobserved input and using the log-sum inequality gives D(PK||QK) at most D(P||Q). The channel may be deterministic binning, randomized corruption or deletion of coordinates. The shared-kernel assumption is essential: choosing different transformations under the two hypotheses could manufacture different output distributions even from identical input laws.

Mutual-information data processing is the corresponding dependence statement. If X to Y to Z forms a Markov chain, meaning the conditional law of Z given X,Y only depends on Y, then I(X;Z) is at most I(X;Y). A randomized representation cannot gain information about X merely by further postprocessing. Equality is possible when the retained statistic preserves the relevant likelihood information; the theorem does not assert that every noninvertible transformation must lose a strictly positive amount.

Divergence adds across independent samples because the log-likelihood ratio becomes a sum. With dependent data, the chain rule instead involves conditional divergences; multiplying a one-sample value by the sample size need not be correct. Similarly, applying a deterministic summary can collapse two distinct laws to the same output distribution and make the processed divergence zero. This is information loss relative to a particular pair of models, not a judgment that the summary is useless for every purpose.

The displayed quantities concern known probability laws. Replacing them by empirical frequencies introduces sampling error and support problems, especially when a finite sample misses outcomes. Smoothing can make an estimate finite but changes the estimated laws. Data processing still applies to the actual probability distributions and a fixed common kernel; it is not a general promise that arbitrary numerical estimators of divergence will satisfy every population inequality on every observed sample.