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.[1]

Formal statement

Pinsker's inequality states that, if ${\displaystyle P}$ and ${\displaystyle Q}$ are two probability distributions on a measurable space ${\displaystyle (X,\Sigma )}$, then

${\displaystyle \delta (P,Q)\leq {\sqrt {{\frac {1}{2}}D_{\mathrm {KL} }(P\parallel Q)}},}$

where

${\displaystyle \delta (P,Q)=\sup {\bigl \{}|P(A)-Q(A)|\mid \quad A\in \Sigma {\text{ is a measurable event}}{\bigr \}}}$

is the total variation distance (or statistical distance) between ${\displaystyle P}$ and ${\displaystyle Q}$ and

${\displaystyle D_{\mathrm {KL} }(P\parallel Q)=\operatorname {E} _{P}\left(\log {\frac {\mathrm {d} P}{\mathrm {d} Q}}\right)=\int _{X}\left(\log {\frac {\mathrm {d} P}{\mathrm {d} Q}}\right)\,\mathrm {d} P}$

is the Kullback–Leibler divergence in nats. When the sample space ${\displaystyle X}$ is a finite set, the Kullback–Leibler divergence is given by

${\displaystyle D_{\mathrm {KL} }(P\parallel Q)=\sum _{i\in X}\left(\log {\frac {P(i)}{Q(i)}}\right)P(i)\!}$

Note that in terms of the total variation norm ${\displaystyle \|P-Q\|}$ of the signed measure ${\displaystyle P-Q}$, Pinsker's inequality differs from the one given above by a factor of two:

${\displaystyle \|P-Q\|\leq {\sqrt {2D_{\mathrm {KL} }(P\parallel Q)}}.}$

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. ${\displaystyle D_{KL}}$ is defined using ${\displaystyle \ln }$ (logarithm in base ${\displaystyle e}$), whereas ${\displaystyle D}$ is typically defined with ${\displaystyle \log _{2}}$ (logarithm in base 2). Then,

${\displaystyle D(P\parallel Q)={\frac {D_{KL}(P\parallel Q)}{\ln 2}}.}$

Given the above comments, there is an alternative statement of Pinsker's inequality in some literature that relates information divergence to variation distance:

${\displaystyle D(P\parallel Q)={\frac {D_{KL}(P\parallel Q)}{\ln 2}}\geq {\frac {1}{2\ln 2}}V^{2}(p,q),}$

i.e.,

${\displaystyle {\sqrt {\frac {D_{KL}(P\parallel Q)}{2}}}\geq {\frac {V(p,q)}{2}},}$

in which

${\displaystyle V(p,q)=\sum _{x\in {\mathcal {X}}}|p(x)-q(x)|}$

is the (non-normalized) variation distance between two probability density functions ${\displaystyle p}$ and ${\displaystyle q}$ on the same alphabet ${\displaystyle {\mathcal {X}}}$.[2]

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 ${\displaystyle r(x)=P(x)/Q(x)-1\geq -1}$:

${\displaystyle {\begin{aligned}D_{KL}(P\parallel Q)&=E_{Q}[(1+r(x))\log(1+r(x))-r(x)]\\&\geq {\frac {1}{2}}E_{Q}\left[{\frac {r(x)^{2}}{1+r(x)/3}}\right]\\&\geq {\frac {1}{2}}{\frac {E_{Q}[|r(x)|]^{2}}{E_{Q}[1+r(x)/3]}}&{\text{(from Titu's lemma)}}\\&={\frac {1}{2}}E_{Q}[|r(x)|]^{2}&{\text{(As }}E_{Q}[1+r(x)/3]=1{\text{ )}}\\&={\frac {1}{2}}V(p,q)^{2}.\end{aligned}}}$

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 ${\displaystyle D_{\mathrm {KL} }(P\parallel Q)>2}$, since the total variation distance is at most ${\displaystyle 1}$. For such distributions, an alternative bound can be used, due to Bretagnolle and Huber[3] (see, also, Tsybakov[4]):

${\displaystyle \delta (P,Q)\leq {\sqrt {1-e^{-D_{\mathrm {KL} }(P\parallel Q)}}}.}$

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.[5]

Inverse problem

A precise inverse of the inequality cannot hold: for every ${\displaystyle \varepsilon >0}$, there are distributions ${\displaystyle P_{\varepsilon },Q}$ with ${\displaystyle \delta (P_{\varepsilon },Q)\leq \varepsilon }$ but ${\displaystyle D_{\mathrm {KL} }(P_{\varepsilon }\parallel Q)=\infty }$. An easy example is given by the two-point space ${\displaystyle \{0,1\}}$ with ${\displaystyle Q(0)=0,Q(1)=1}$ and ${\displaystyle P_{\varepsilon }(0)=\varepsilon ,P_{\varepsilon }(1)=1-\varepsilon }$.[6]

However, an inverse inequality holds on finite spaces ${\displaystyle X}$ with a constant depending on ${\displaystyle Q}$.[7] More specifically, it can be shown that with the definition ${\displaystyle \alpha _{Q}:=\min _{x\in X:Q(x)>0}Q(x)}$ we have for any measure ${\displaystyle P}$ which is absolutely continuous to ${\displaystyle Q}$

${\displaystyle {\frac {1}{2}}D_{\mathrm {KL} }(P\parallel Q)\leq {\frac {1}{\alpha _{Q}}}\delta (P,Q)^{2}.}$

As a consequence, if ${\displaystyle Q}$ has full support (i.e. ${\displaystyle Q(x)>0}$ for all ${\displaystyle x\in X}$), then

${\displaystyle \delta (P,Q)^{2}\leq {\frac {1}{2}}D(P\parallel Q)\leq {\frac {1}{\alpha _{Q}}}\delta (P,Q)^{2}.}$

References

1. Csiszár, Imre; Körner, János (2011). Information Theory: Coding Theorems for Discrete Memoryless Systems. Cambridge University Press. p. 44. ISBN 9781139499989.
2. Raymond W., Yeung (2008). Information Theory and Network Coding. Hong Kong: Springer. p. 26. ISBN 978-0-387-79233-0.
3. Bretagnolle, J.; Huber, C, Estimation des densités: risque minimax, Séminaire de Probabilités, XII (Univ. Strasbourg, Strasbourg, 1976/1977), pp. 342–363, Lecture Notes in Math., 649, Springer, Berlin, 1978, Lemma 2.1 (French).
4. Tsybakov, Alexandre B., Introduction to nonparametric estimation, Revised and extended from the 2004 French original. Translated by Vladimir Zaiats. Springer Series in Statistics. Springer, New York, 2009. xii+214 pp. ISBN 978-0-387-79051-0, Equation 2.25.
5. Tsybakov, Alexandre (2009). Introduction to Nonparametric Estimation. Springer. p. 132. ISBN 9780387790527.
6. The divergence becomes infinite whenever one of the two distributions assigns probability zero to an event while the other assigns it a nonzero probability (no matter how small); see e.g. Basu, Mitra; Ho, Tin Kam (2006). Data Complexity in Pattern Recognition. Springer. p. 161. ISBN 9781846281723..
7. see Lemma 4.1 in Götze, Friedrich; Sambale, Holger; Sinulis, Arthur (2019). "Higher order concentration for functions of weakly dependent random variables". Electronic Journal of Probability. 24. arXiv:1801.06348. doi:10.1214/19-EJP338. S2CID 52200238.

Further 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