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 in terms of the Kullback–Leibler divergence.
The inequality is tight up to constant factors.

Formal statement

Pinsker's inequality states that, if and are two probability distributions on a measurable space, then
where
is the total variation distance between and and
is the Kullback–Leibler divergence in nats. When the sample space is a finite set, the Kullback–Leibler divergence is given by
Note that in terms of the total variation norm of the signed measure, Pinsker's inequality differs from the one given above by a factor of two:
A 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, there are distributions with but. An easy example is given by the two-point space with and.
However, an inverse inequality holds on finite spaces with a constant depending on. More specifically, it can be shown that with the definition we have for any measure which is absolutely continuous to
As a consequence, if has full support, then