Inequality in information theory
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.
Formal statement.
Pinsker's inequality states that, if formula_1 and formula_2 are two probability distributions on a measurable space formula_3, then
formula_4
where
formula_5
is the total variation distance (or statistical distance) between formula_1 and formula_2 and
formula_8
is the Kullback–Leibler divergence in nats. When the sample space formula_9 is a finite set, the Kullback–Leibler divergence is given by
 formula_10
Note that in terms of the total variation norm formula_11 of the signed measure formula_12, Pinsker's inequality differs from the one given above by a factor of two:
formula_13
A proof of Pinsker's inequality uses the partition inequality for "f"-divergences.
Alternative version.
Note that the expression of Pinsker inequality depends on what basis of logarithm is used in the definition of KL-divergence. formula_14 is defined using formula_15 (logarithm in base formula_16), whereas formula_17 is typically defined with formula_18 (logarithm in base 2). Then,
formula_19
Given the above comments, there is an alternative statement of Pinsker's inequality in some literature that relates information divergence to variation distance: 
formula_20
i.e.,
formula_21
in which 
formula_22
is the (non-normalized) variation distance between two probability density functions formula_23 and formula_24 on the same alphabet formula_25.
This form of Pinsker's inequality shows that "convergence in divergence" is a stronger notion than "convergence in variation distance".
A simple proof by John Pollard is shown by letting formula_26:
formula_27
Here Titu's lemma is also known as Sedrakyan's inequality.
Note that the lower bound from Pinsker's inequality is vacuous for any distributions where formula_28, since the total variation distance is at most formula_29. For such distributions, an alternative bound can be used, due to Bretagnolle and Huber (see, also, Tsybakov):
formula_30
History.
Pinsker first proved the inequality with a greater 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 formula_31, there are distributions formula_32 with formula_33 but formula_34. An easy example is given by the two-point space formula_35 with formula_36 and formula_37.
However, an inverse inequality holds on finite spaces formula_9 with a constant depending on formula_2. More specifically, it can be shown that with the definition formula_40 we have for any measure formula_1 which is absolutely continuous to formula_2
 formula_43
As a consequence, if formula_2 has full support (i.e. formula_45 for all formula_46), then
 formula_47
References.
 ;templatestyles src="Reflist/styles.css" / ;