Pinsker's inequality

In information theory, Pinsker's inequality, named after its inventor Mark Semenovich Pinsker, is an inequality that bounds the total variation distance (or statistical distance) in terms of the Kullback-Leibler divergence. The inequality is tight up to constant factors.[citation needed]

Pinsker's inequality states that, if P and Q are two probability distributions, then

$\delta(P,Q) \le \sqrt{\frac{1}{2} D_{\mathrm{KL}}(P\|Q)}$

where

$\delta(P,Q)=\sup \{ |P(A) - Q(A)| : A\text{ is an event to which probabilities are assigned.} \}$

is the total variation distance (or statistical distance) between P and Q and

$D_{\mathrm{KL}}(P\|Q) = \sum_i \ln\left(\frac{P(i)}{Q(i)}\right) P(i)\!$

is the Kullback-Leibler divergence in nats.

Pinsker first proved the inequality with a worse constant. The inequality in the above form was proved independently by Kullback, Csiszár, and Kemperman.[1]

An inverse of the inequality cannot hold: There are distributions with $\delta(P,Q)\le\epsilon$ for any $\epsilon>0$ but $D_{\mathrm{KL}}(P\|Q) = \infty$.[citation needed]

References

• Thomas M. Cover and Joy A. Thomas: Elements of Information Theory, 2nd edition, Willey-Interscience, 2006
• Nicolo Cesa-Bianchi and Gábor Lugosi: Prediction, Learning, and Games, Cambridge University Press, 2006
1. ^ Tsybakov, Alexandre (2009). Introduction to Nonparametric Estimation. Springer. p. 132. ISBN 9780387790527.