Data Processing and Product-Sample Divergence

Why Transformations and Repeated Samples Matter

In statistical learning, distributions describe what an experiment can reveal about an unknown state. A procedure may discard part of the data, summarize it with a statistic, or randomize it before producing an output. Such processing cannot make two distributions more distinguishable when the same procedure is applied to both. In contrast, independent observations accumulate evidence: their Kullback–Leibler divergence adds.

These facts are useful in lower-bound arguments. Data processing lets us compare the information in an observation with the information retained after a transformation, while product additivity quantifies how distinguishability changes with sample size. The results below apply to probability measures on measurable spaces; no densities with respect to Lebesgue measure are required.

Kullback–Leibler Divergence and Markov Kernels

The negative part of \(r\log r\) is integrable because \(t\log t\geq -1/e\) for \(t\geq0\). Thus the displayed integral is well-defined, possibly with value \(+\infty\). Nonnegativity follows from Jensen’s inequality: \(t\mapsto t\log t\) is convex, and \(\int r\,dQ=1\), so \(\int r\log r\,dQ\geq 1\log 1=0\).

A measurable function \(T:\mathcal X\to\mathcal Y\) is a special case: use the deterministic kernel \(K(x,B)=\mathbf 1\{T(x)\in B\}\). A randomized procedure is represented by a general Markov kernel. In both cases, the same kernel must be applied to \(P\) and \(Q\).

Data Processing: The Divergence Cannot Increase

This statement holds on arbitrary measurable spaces. The proof uses a joint probability measure and conditional expectation, which exist without a standard Borel assumption.

Proof. If \(D(P\|Q)=+\infty\), the inequality holds because every divergence is at most \(+\infty\). Otherwise \(P\ll Q\); set \(r=dP/dQ\). Construct the joint law \(R\) of \((X,Y)\) by first drawing \(X\sim Q\), then drawing \(Y\) from \(K(X,\cdot)\). Its \(Y\)-marginal is \(QK\). Under this joint law, \(E_R[r(X)]=1\).

Because \(P\ll Q\), also \(PK\ll QK\): if \((QK)(B)=0\), then \(K(x,B)=0\) for \(Q\)-almost every \(x\), and hence \((PK)(B)=\int K(x,B)P(dx)=0\). Let \(g=d(PK)/d(QK)\). For each measurable \(B\subseteq\mathcal Y\), $$ E_R\!\left[r(X)\mathbf 1\{Y\in B\}\right] =\int K(x,B)P(dx) =(PK)(B) =\int_B g(y)(QK)(dy). $$ Thus \(g(Y)\) is a version of \(E_R[r(X)\mid \sigma(Y)]\): the equality holds on every event \(\{Y\in B\}\), which generates \(\sigma(Y)\). Conditional Jensen’s inequality for the convex function \(\phi(t)=t\log t\) now gives $$ D(PK\|QK) =E_R[\phi(g(Y))] \leq E_R[\phi(r(X))] =D(P\|Q). $$ The expectations are well-defined because \(\phi\) is bounded below; if the right side is finite, conditional Jensen applies directly. This proves the inequality. \(\square\)

Independent Product Samples

For independent observations, the joint law is a product measure. The next result states exactly how its divergence depends on the component distributions.

Proof when every component divergence is finite. Finiteness implies \(P_i\ll Q_i\); write \(r_i=dP_i/dQ_i\). The density of the product measure \(\bigotimes_i P_i\) with respect to \(\bigotimes_i Q_i\) is \(\prod_i r_i(x_i)\). Indeed, integrating this product density over a measurable rectangle gives the product of the component probabilities, which determines the product measure. Therefore the log density is \(\sum_i\log r_i(x_i)\) wherever the product density is positive.

Each \(\log r_i(X_i)\), under \(X_i\sim P_i\), is integrable when \(D(P_i\|Q_i)<\infty\). To check the negative part, write \(r_i=dP_i/dQ_i\): $$ E_{P_i}\!\left[(-\log r_i(X_i))_+\right] =\int_{\{r_i<1\}} -r_i\log r_i\,dQ_i \leq \frac{1}{e}. $$ The positive part is then finite because the divergence is finite. Thus expectation of the finite sum can be taken term by term under the product law, giving $$ D\!\left(\bigotimes_{i=1}^nP_i\,\middle\|\,\bigotimes_{i=1}^nQ_i\right) =\sum_{i=1}^n E_{P_i}[\log r_i(X_i)] =\sum_{i=1}^nD(P_i\|Q_i). $$

Proof when at least one component divergence is infinite. Choose an index \(j\) with \(D(P_j\|Q_j)=+\infty\). Projection of the product observation onto coordinate \(j\) is a deterministic Markov kernel. The data-processing inequality just proved gives $$ D\!\left(\bigotimes_{i=1}^nP_i\,\middle\|\,\bigotimes_{i=1}^nQ_i\right) \geq D(P_j\|Q_j)=+\infty. $$ Hence the product divergence is infinite, matching the extended sum. This argument is valid on arbitrary measurable spaces because the data-processing result above was proved at that level of generality. \(\square\)

Randomized Processing and a Numerical Check

Common Pitfalls and Why the Results Matter

• Assuming any processing increases divergence. The inequality goes in the opposite direction when the same kernel is applied to both distributions: \(D(PK\|QK)\leq D(P\|Q)\). The output cannot recover distinctions that the channel has erased.
• Applying different procedures to the two distributions. Data processing compares \(PK\) with \(QK\) for a common kernel \(K\). If the procedures differ, the theorem does not provide this comparison.
• Adding divergences without independence. Product additivity concerns product distributions, which encode independence. A dependent joint distribution is not in general the product of its marginals, so the theorem cannot be applied by simply summing marginal divergences.
• Ignoring infinite component divergences. The finite-density calculation alone does not cover that case. Coordinate projection and data processing show that an infinite divergence in any component forces the product divergence to be infinite.

Together, these properties separate two effects. A common transformation can only discard distinguishability, while independent repetition adds divergence exactly. They allow an analyst to compare the information available in a full experiment with that in a reduced observation, and to track how evidence accumulates across independent samples.