Puneet Varma (Editor)

Pinsker's inequality

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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.

Contents

Formal statement

Pinsker's inequality states that, if P and Q are two probability distributions on a measurable space ( X , Σ ) , then

δ ( P , Q ) ≤ 1 2 D K L ( P ∥ Q ) ,

where

δ ( P , Q ) = sup { | P ( A ) − Q ( A ) | | A ∈ Σ  is a measurable event }

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

D K L ( P ∥ Q ) = E P ( log ⁡ d P d Q ) = ∫ X ( log ⁡ d P d Q ) d P

is the Kullback–Leibler divergence in nats. When the sample space X is a finite set, the Kullback–Leibler divergence is given by

D K L ( P ∥ Q ) = ∑ i ∈ X ( log ⁡ P ( i ) Q ( i ) ) P ( i )

Note that in terms of the total variation norm ∥ P − Q ∥ of the signed measure P − Q , Pinsker's inequality differs from the one given above by a factor of two:

∥ P − Q ∥ ≤ 2 D K L ( P ∥ Q ) .

The proof of Pinsker's inequality uses the partition inequality for f-divergences.

History

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

Inverse problem

A precise inverse of the inequality cannot hold: for every ϵ > 0 , there are distributions with δ ( P , Q ) ≤ ϵ but D K L ( P ∥ Q ) = ∞ .

Additional reading

  • 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

    • References

    Pinsker's inequality Wikipedia
    (Text) CC BY-SA