Pinsker's inequality

In information theory, Pinsker's inequality, named after its inventor Mark Semenovich Pinsker, is an inequality that relates Kullback-Leibler divergence and the total variation distance. It states that if P, Q are two probability distributions, then

$\sqrt{D(P\|Q)/2} \ge \sup \{ |P(A) - Q(A)| : A\text{ is an event to which probabilities are assigned.} \}$

where D(P || Q) is the Kullback-Leibler divergence in nats and

$\sup_A |P(A) - Q(A)|\,$

is the total variation distance between P and Q.

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