Contents

Pinsker's inequality

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 divergenceinnats. 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[edit]

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[edit]

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[edit]

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[edit]

Further reading[edit]

• 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