Pinsker不等式建立了两个概率分布的total variation距离和KL散度间的关系。我们先看它的一般形式，然后再证明其离散形式，一般情形的证明方法是完全一致的。

证明方法将会摘录三种。第一种自然一些，从Hoeffding不等式出发，利用信息论中的结果，步步为营。第二种技巧性更强，利用微积分中的技巧，巧妙地得出一个关键性不等式估计后快速得证。第三种也是利用了信息论中的结果，我们需要的是KL散度的data processing不等式，在这个基础上，只需要证明Bernoulli变量的情形就可以了，简洁明快。

三种证法分别改编自以下资料：

1. BOBKOV, Sergej G.; GÖTZE, Friedrich. Exponential integrability and transportation cost related to logarithmic Sobolev inequalities. Journal of Functional Analysis, 1999, 163.1: 1-28.
2. Probability tools, tricks, and miracles ©David Pollard
3. CANONNE, Clément L. A short note on an inequality between KL and TV. arXiv preprint arXiv:2202.07198, 2022.

其中证明三存在一定gap，已经补充在最后一节。

一般形式

这两个量定义的一般定义为
\begin{aligned}
\|P-Q\| _ {\mathrm{TV}}&=\sup _ A|P(A)-Q(A)|=\frac12\sup _ A((P-Q)(A)-(P-Q)(A^c)),\\
D _ {\mathrm{KL}}(P\|Q)&=\mathbb E _ {Q}\Big[\frac{\mathrm dP}{\mathrm dQ}\log\frac{\mathrm dP}{\mathrm dQ}\Big]=\mathbb E _ P\Big[\log\frac{\mathrm dP}{\mathrm dQ}\Big],\quad P\ll Q.
\end{aligned}当P\not\ll Q，KL散度定义为+\infty。KL散度也可以等价定义为（可参见 信息论基本内核）：
D _ {\text{KL}}(P\|Q)=
\begin{cases}
-\mathbb E _ P\Big[\log\frac{\mathrm dQ}{\mathrm dP}\Big],& Q\ll P;\\
+\infty,&Q\not\ll P.
\end{cases}
Pinsker不等式：考虑\log的底数取\mathrm e，那么
\|P-Q\| _ {\mathrm{TV}}^2\leqslant \frac12D _ {\mathrm{KL}}(P\|Q).

离散形式证明一

现在来考虑Pinsker不等式的离散形式。不难看出，若令A^\ast=\{x\mid p(x)\geqslant q(x)\}，TV距离可以写成
\sup _ A|P(A)-Q(A)|=P(A^\ast)-Q(A^\ast).注意到P,Q均为概率分布，|P(A)-Q(A)|和|P(A^c)-Q(A^c)|是相等的。因此TV距离和L1距离有如下关系
\|P-Q\| _ {\mathrm{TV}}=\frac12\|P-Q\| _ 1=\frac12\sum _ x|p(x)-q(x)|.而KL散度可以写成
D _ {\mathrm{KL}}(P\|Q)=\sum _ x p(x)\ln\frac{p(x)}{q(x)}=-\sum _ x p(x)\ln\frac{q(x)}{p(x)}.先来看引理。

---

引理(Hoeffding引理)：设随机变量\mathrm x满足a\leqslant \mathrm x\leqslant b，那么对任意\lambda\in\mathbb R，总有
\mathbb{E}[\exp(\lambda(\mathrm x-\mathbb E\mathrm x))]\leqslant\exp\Big(\frac{(b-a)^2\lambda^2}8\Big).
引理的证明：不失一般性，可设\mathbb E(\mathrm x)=0。首先注意到|\mathrm x-\frac{a+b}2|\leqslant\frac{b-a}{2}，因此不难看出
\operatorname{Var}(\mathrm x)\leqslant\mathbb E\Big[\Big(\mathrm x-\frac{a+b}2\Big)^2\Big]\leqslant\Big(\frac{b-a}2\Big)^2.

我们先来看 A short proof of Hoeffding's lemma 的证明方法（只证明右边分母为4的情形）。
现在引入另一个随机变量\mathrm x'，其与\mathrm x独立且有相同的分布。那么\mathbb E(\mathrm x-\mathrm x')=0；由Jensen不等式，
\begin{aligned}
\sout{\mathbb E(\exp(\lambda \mathrm x))}&\sout{=\mathbb E(\exp(\lambda \mathrm x))\exp(\mathbb E(-\lambda\mathrm x'))}\\
&\sout{\leqslant \mathbb E(\exp(\lambda \mathrm x))\mathbb E(\exp(-\lambda\mathrm x'))=\mathbb E[\exp(\lambda(\mathrm x-\mathrm x'))].}
\end{aligned}
现在令\mathrm y=\mathrm x-\mathrm x'，其均值方差都可计算，\mathbb E(\mathrm y)=0，\operatorname{Var}(\mathrm y)=2\operatorname{Var}(\mathrm x)\leqslant\frac{(b-a)^2}{2}。

这个证明的关键之点在于注意到\mathrm y的奇数阶矩都等于0。由Taylor定理，存在0和\mathrm y之间的\epsilon使得
\begin{aligned}
\sout{\mathrm e^{\lambda \mathrm y}} &\sout{= 1 + \lambda \mathrm y + \frac{\lambda^2}{2} \mathrm y^2 + \frac{\lambda^3}{6} \mathrm y^3 \mathrm e^{\lambda \epsilon}}\\
&\sout{\leqslant 1 + \lambda \mathrm y + \frac{\lambda^2}{2} \mathrm y^2 + \frac{\lambda^3}{6} \mathrm y^3 \mathrm e^{\lambda \mathrm y}}\\
&\sout{\leqslant 1 + \lambda \mathrm y + \frac{\lambda^2}{2} \mathrm y^2 + \frac{\lambda^3}{6} \mathrm y^3 \mathrm e^{|\lambda| (b-a)}.}
\end{aligned}
注意第一个不等号并非显然，\mathrm y和\lambda均有可能取正负。继续取期望得
\begin{aligned}
&\sout{\mathbb E(\exp(\lambda\mathrm x))\leqslant\mathbb E(\exp(\lambda\mathrm y))}\\
\leqslant{}& \sout{1+\frac{\lambda^2}2\mathbb E(\mathrm y^2)=1+\frac{\lambda^2}2\operatorname{Var}(\mathrm y)}\\
={}&\sout{1+\frac{\lambda^2(b-a)^2}{4}\leqslant\exp\Big(\frac{\lambda^2(b-a)^2}{4}\Big).}
\end{aligned}
现在来看 Wikipedia 里对这个引理的证明。

首先，对任一x\in[a,b]，利用指数函数的凸性，应用Jensen不等式，
\begin{aligned}
\lambda x&=\frac{b-x}{b-a}\lambda a+\frac{x-a}{b-a}\lambda b\\
\exp(\lambda x)&\leqslant\frac{b-x}{b-a}\exp(\lambda a)+\frac{x-a}{b-a}\exp(\lambda b)\\
\mathbb E(\exp(\lambda \mathrm x))&\leqslant\frac{b}{b-a}\exp(\lambda a)-\frac{a}{b-a}\exp(\lambda b)\\
&=\exp(\lambda a)\Big[1+\frac{a}{b-a}-\frac a{b-a}\exp(\lambda(b-a))\Big]
\end{aligned}于是我们要证明上式右边对所有\lambda都小于等于\exp(\lambda^2(b-a)^2/8)，作换元\lambda\leftarrow\lambda(b-a)，再令c=\frac {-a}{b-a}，即要证
\exp(-\lambda c)[1-c+c\exp(\lambda)]\leqslant\exp\Big(\frac{\lambda^2}8\Big).考虑取对数。
f(\lambda):=-\lambda c+\ln[1-c+c\exp(\lambda)],\\
f'(\lambda)=-c+\frac{c\exp(\lambda)}{1-c+c\exp(\lambda)},\\
f''(\lambda)=\frac{c\exp(\lambda)}{1-c+c\exp(\lambda)}-\frac{c^2\exp^2(\lambda)}{(1-c+c\exp(\lambda))^2}.可以发现f''(\lambda)恰好可以写成t(1-t)的形式，于是f''\leqslant\frac14。现在由Taylor定理，
f(\lambda)=f(0)+f'(0)\lambda+f''(\theta\lambda)\frac{\lambda^2}2\leqslant\frac{\lambda^2}{8}.这就证明了Hoeffding引理。

---

Pinsker不等式的证明：令A=\{x\mid p(x)\geqslant q(x)\}，再令y=\mathbf 1 _ {A}（即x\in A时y(x)=1，否则y(x)=0），则
\|P-Q\| _ {\mathrm{TV}}=\sum _ {x\in A}(p(x)-q(x))=E _ {\mathrm x\sim P}[y(\mathrm x)]-E _ {\mathrm x\sim Q}[y(\mathrm x)].现在y(x)\in[0,1]，由Hoeffding引理，
\begin{aligned}
&E_{\mathrm x\sim Q}[\exp(\lambda(\mathrm y-E_{\mathrm x\sim Q}\mathrm y))]\leqslant \exp({\lambda^2}/{8}),\quad \lambda\in\mathbb{R}\\
\implies{}& E_{\mathrm x\sim Q}[\exp(\lambda(\mathrm y-E_{\mathrm x\sim Q}\mathrm y)-\lambda^2/8)]\leqslant 1\\
\implies{}& E_{\mathrm x\sim Q}[\exp(\lambda\mathrm z-\lambda^2/8)]\leqslant1,\quad (\mathrm z=\mathrm y-E_{\mathrm x\sim Q}\mathrm y).
\end{aligned}
令r(x)=p(x)/q(x)，KL散度可以写成\sum _ xq(x)\cdot r(x)\ln r(x)=E _ Q[r(\mathrm x)\ln r(\mathrm x)]。下面证明
\begin{aligned}
&E_{Q}[r(\mathrm x)\cdot(\lambda\mathrm z-\lambda^2/8)]\leqslant E_Q[r(\mathrm x)\ln r(\mathrm x)]\\
\Longleftarrow{}& E_P[\lambda\mathrm z-\lambda^2/8]\leqslant E_P\Big[\ln\frac{p(\mathrm x)}{q(\mathrm x)}\Big]\\
\Longleftarrow{}& 0\leqslant\sum_x p(x)\ln \frac{p(x)}{q(x)\exp(\lambda z-\lambda^2/8)}.
\end{aligned}
前面已经推导出\sum _ x q(x)\exp(\lambda z-\lambda^2/8)=E _ {\mathrm x\sim Q}[\exp(\lambda\mathrm z-\lambda^2/8)]\leqslant1，不妨设等号成立（小于的情形可由取等的情形推出），那么原式右边变为一个KL散度，自然是非负的。这就证明了E _ {Q}[r(\mathrm x)\cdot(\lambda\mathrm z-\lambda^2/8)]\leqslant E _ Q[r(\mathrm x)\ln r(\mathrm x)]。

于是由\mathbb E _ Q[r(\mathrm x)]=1，
\begin{aligned}
&E _ Q[\mathrm z\mathrm r]\leqslant\frac{\lambda}{8}+\frac{1}{\lambda}E _ Q[r(\mathrm x)\ln r(\mathrm x)],\quad \forall \lambda>0,\\
\implies{}&E _ Q[\mathrm z\mathrm r]\leqslant2\sqrt{\frac18E _ Q[r(\mathrm x)\ln r(\mathrm x)]},\\
\implies{}&E _ P[\mathrm {y}]-E _ Q[\mathrm y]\leqslant\sqrt{\frac12D _ {\mathrm{KL}}(P\|Q)}.
\end{aligned}这就证明了
\|P-Q\| _ {\mathrm{TV}}^2\leqslant\frac12D _ {\mathrm{KL}}(P\|Q).

离散形式证明二

证明要用到一个关键不等式，下面作为引理给出。

引理：当x>-1，
(1+x)\ln(1+x)-x\geqslant\frac{x^2/2}{1+x/3}.
为了证明这个不等式，令f(x)=(1+x)\ln(1+x)-x，有f'(x)=\ln(1+x)，f''(x)=1\mathbin{/}(1+x)；再令
F(x)=\frac{f(x)-f(0)-f'(0)x}{x^2/2}=\frac{f(x)}{x^2/2},而F(0):=\lim _ {x\to0}F(x)=1，从而使其连续。分子部分有
f(x)-f(0)-f'(0)x=\int _ {0}^x{f''(t)}(x-t)\, \mathrm dt=x^2\int _ 0^1f''(xt)(1-t)\, \mathrm dt.易见t\mapsto f''(xt)是凸函数，由Jensen不等式
\frac{x^2}2\int _ 0^1f''(xt)\cdot2(1-t)\, \mathrm dt\geqslant\frac{x^2}2f''\Big(x\int _ 0^1t\cdot2(1-t)\, \mathrm dt\Big)=\frac{x^2}2f''\Big(\frac x3\Big).从而
F(x)=\frac{f(x)}{x^2/2}\geqslant f''\Big(\frac x3\Big)=\frac{1}{1+x/3}.这就证明了引理。

现在重定义r(x)=p(x)/q(x)-1，那么易见\mathbb E _ {Q}[r(\mathrm x)]=0，由Cauchy-Schwartz不等式，
\begin{aligned}
D _ {\mathrm{KL}}(P\|Q)&=\mathbb E _ {Q}[(1+r(\mathrm x))\ln(1+r(\mathrm x))]\\
&=\mathbb E _ {Q}[(1+r(\mathrm x))\ln(1+r(\mathrm x))-r(\mathrm x)]\\
&\geqslant\frac12\mathbb E _ Q\Big[\frac{r(\mathrm x)^2}{1+r(\mathrm x)/3}\Big]\\
&=\frac12\mathbb E _ Q\Big[\frac{r(\mathrm x)^2}{1+r(\mathrm x)/3}\Big]\mathbb E _ Q[1+r(\mathrm x)/3]\\
&\geqslant\frac12\mathbb E _ Q^2|r(\mathrm x)|=\frac12\Big(\sum _ x |p(x)-q(x)|\Big)^2.
\end{aligned}前面已提及\frac12\|P-Q\| _ 1=\|P-Q\| _ {\mathrm {TV}}，Pinsker不等式即证。

离散形式证明三

我们沿用证明一里的记号。

当\mathrm x\sim P时，y(\mathrm x)\sim \mathrm{Bernoulli}(P(A))=:P'；当\mathrm x\sim Q时，y(\mathrm x)\sim \mathrm{Bernoulli}(Q(A))=:Q'。那么
\|P'-Q'\| _ {\mathrm{TV}}^2=(P(A)-Q(A))^2=\|P-Q\|^2 _ {\mathrm{TV}}.而由data processing不等式，
D _ {\mathrm{KL}}(P'\|Q')\leqslant D _ {\mathrm {KL}}(P\|Q).

---

Gap：通常data processing不等式是用互信息表示的，所以这种KL散度的不等式需要额外考虑。我们将上面的不等式表述为如下的命题：

命题：对一个随机变量\mathrm x，定义随机变量\mathrm y=\mathbf 1 _ A(\mathrm x)，设\mathrm x\sim P _ {\mathrm x}时\mathrm y\sim P _ {\mathrm y}、\mathrm x\sim Q _ {\mathrm x}时\mathrm y\sim Q _ {\mathrm y}，那么
D _ {\mathrm{KL}}(P _ {\mathrm{y}}\| Q _ {\mathrm{y}})\leqslant D _ {\mathrm{KL}}(P _ {\mathrm{x}}\| Q _ {\mathrm x}).在下一节证明这个命题。

---

这表明我们只需要证明Bernoulli分布的情形即可，这样有了2\|P'-Q'\| _ {\mathrm{TV}}^2\leqslant D _ {\mathrm{KL}}(P'\|Q')，Pinsker不等式也就得证。我们只需要证明
2(p-q)^2\leqslant p\ln\frac{p}{q}+(1-p)\ln\frac{1-p}{1-q},\quad p,q\in(0,1).而当p,q取0或1的情形是容易的。

令f(x)=p\ln x+(1-p)\ln(1-x)，那么上式右边恰为f(p)-f(q)，于是由微积分基本定理
\begin{aligned}
&f(p)-f(q)=\int _ q^pf'(x)\, \mathrm dx=\int _ q^p\Big(\frac px-\frac{1-p}{1-x}\Big)\, \mathrm dx\\={}&\int _ q^p\frac{p-x}{x(1-x)}\, \mathrm dx\leqslant4\int _ q^p(p-x)\, \mathrm dx=2(p-q)^2.
\end{aligned}这就完成了证明。

KL散度的data processing不等式

为了证明上一节的命题，我们考虑一般情况下，KL散度的链式法则：

定理（KL散度的链式法则）：设有两个联合分布P _ {\mathrm{x,y}},Q _ {\mathrm{x,y}}及对应的边缘分布P _ {\mathrm x},Q _ {\mathrm x}，且都有对应的正则条件分布P _ {\mathrm{y}|\mathrm x},Q _ {\mathrm{y}|\mathrm x}，那么
D _ {\mathrm{KL}}(P _ {\mathrm {x,y}}\| Q _ {\mathrm{x,y}})=D _ {\mathrm{KL}}(P _ {\mathrm{y}|\mathrm x}\|Q _ {\mathrm{y}|\mathrm x}\operatorname{|}P _ {\mathrm x})+D _ {\mathrm{KL}}(P _ {\mathrm x}\|Q _ {\mathrm {x}}).其中的D _ {\mathrm{KL}}(P _ {\mathrm{y}|\mathrm x}\|Q _ {\mathrm{y}|\mathrm x}\operatorname{|}P _ {\mathrm x})表示条件KL散度，具体定义为
D _ {\mathrm{KL}}(P _ {\mathrm{y}|\mathrm x}\|Q _ {\mathrm{y}|\mathrm x}\operatorname{|}P _ {\mathrm x})=\mathbb E _ {\mathrm x\sim P _ {\mathrm x}}[D _ {\mathrm{KL}}(P _ {\mathrm{y}|\mathrm x}\|Q _ {\mathrm{y}|\mathrm x})].这里不讨论可测性（默认可测），因而默认这个定义well-defined，可参看其它资料。

证明思路：不妨设P _ {\mathrm x}\ll Q _ {\mathrm x}且Q _ {\mathrm x}\ll P _ {\mathrm x}，否则上式两边都为+\infty，等式成立。从而\frac{\mathrm d P _ {\mathrm x}}{\mathrm dQ _ {\mathrm x}}几乎处处[P _ {\mathrm x}]有限。记R _ {\mathrm y|\mathrm x}=\frac12(P _ {\mathrm y|\mathrm x}+Q _ {\mathrm y|\mathrm x})、R _ {\mathrm x,\mathrm y}=Q _ {\mathrm x}R _ {\mathrm y|\mathrm x}，不难发现：R _ {\mathrm y|\mathrm x}是P _ {\mathrm y|\mathrm x},Q _ {\mathrm y|\mathrm x}的dominating测度、R _ {\mathrm x,\mathrm y}是P _ {\mathrm x,\mathrm y},Q _ {\mathrm x,\mathrm y}的dominating测度，即P _ {\mathrm y|\mathrm x},Q _ {\mathrm y|\mathrm x}\ll R _ {\mathrm y|\mathrm x}以及P _ {\mathrm x,\mathrm y},Q _ {\mathrm x,\mathrm y}\ll R _ {\mathrm x,\mathrm y}。对可测的E，有
Q _ {\mathrm x,\mathrm y}(E)=\int\mathrm dQ _ {\mathrm x}\int _ {\cdots} Q _ {\mathrm y|\mathrm x}(\mathrm dy| x)=\int _ E\frac{\mathrm dQ _ {\mathrm y|\mathrm x}}{\mathrm dR _ {\mathrm y|\mathrm x}}(y|x)\, R _ {\mathrm x,\mathrm y}(\mathrm dx,\mathrm dy).同样地，
P _ {\mathrm x,\mathrm y}(E)=\int\, \mathrm dQ _ {\mathrm x}\int _ {\cdots}\frac{\mathrm dP _ {\mathrm x}}{\mathrm dQ _ {\mathrm x}}(x)P _ {\mathrm y|\mathrm x}(\mathrm dy| x)=\int _ E\frac{\mathrm dP _ {\mathrm x}}{\mathrm dQ _ {\mathrm x}}(x)\frac{\mathrm dP _ {\mathrm y|\mathrm x}}{\mathrm dR _ {\mathrm y|\mathrm x}}(y|x)\, R _ {\mathrm x,\mathrm y}(\mathrm dx,\mathrm dy).从而
\begin{aligned}
D _ {\mathrm {KL}}(P _ {\mathrm {x,y}}\|Q _ {\mathrm {x,y}})&=\mathbb E _ {P _ {\mathrm {x,y}}}\bigg[\log\frac{\frac{\mathrm dP _ {\mathrm x}}{\mathrm dQ _ {\mathrm x}}(\mathrm x)\frac{\mathrm dP _ {\mathrm y|\mathrm x}}{\mathrm dR _ {\mathrm y|\mathrm x}}(\mathrm y|\mathrm x)}{\frac{\mathrm dQ _ {\mathrm y|\mathrm x}}{\mathrm dR _ {\mathrm y|\mathrm x}}(\mathrm y|\mathrm x)}\bigg]\\
&=\mathbb E _ {P _ {\mathrm {x,y}}}\bigg[\log\frac{\frac{\mathrm dP _ {\mathrm y|\mathrm x}}{\mathrm dR _ {\mathrm y|\mathrm x}}(\mathrm y|\mathrm x)}{\frac{\mathrm dQ _ {\mathrm y|\mathrm x}}{\mathrm dR _ {\mathrm y|\mathrm x}}(\mathrm y|\mathrm x)}\bigg]+\mathbb E _ {P _ {\mathrm {x,y}}}\Big[\log\frac{\mathrm dP _ {\mathrm x}}{\mathrm dQ _ {\mathrm x}}(\mathrm x)\Big]\\
&=D _ {\mathrm{KL}}(P _ {\mathrm{y}|\mathrm x}\|Q _ {\mathrm{y}|\mathrm x}\operatorname{|}P _ {\mathrm x})+D _ {\mathrm{KL}}(P _ {\mathrm x}\|Q _ {\mathrm {x}}).
\end{aligned}这就证明了KL散度的链式法则。

定理（KL散度的data processing不等式）：设给定随机变量\mathrm x=x时，\mathrm y\sim P _ {\mathrm y|\mathrm x}(y|x)。P _ {\mathrm y}=\int P _ {\mathrm y|\mathrm x}(\cdot|x)\, P _ {\mathrm x}(\mathrm dx)，Q _ {\mathrm y}=\int P _ {\mathrm y|\mathrm x}(\cdot|x)\, Q _ {\mathrm x}(\mathrm dx)，那么
D _ {\mathrm {KL}}(P _ {\mathrm y}\|Q _ {\mathrm y})\leqslant D _ {\mathrm {KL}}(P _ {\mathrm x}\|Q _ {\mathrm x}).
证明：由KL散度的链式法则，
\begin{aligned}D _ {\mathrm {KL}}(P _ {\mathrm x}\|Q _ {\mathrm x})&=D _ {\mathrm {KL}}(P _ {\mathrm x}\|Q _ {\mathrm x})+D _ {\mathrm {KL}}(P _ {\mathrm y|\mathrm x}\|Q _ {\mathrm y|\mathrm x}\operatorname{|}P _ {\mathrm x})\\&=D _ {\mathrm {KL}}(P _ {\mathrm x,\mathrm y}\| Q _ {\mathrm x,\mathrm y})\\&=D _ {\mathrm {KL}}(P _ {\mathrm y}\|Q _ {\mathrm y})+D _ {\mathrm {KL}}(P _ {\mathrm x|\mathrm y}\|Q _ {\mathrm x|\mathrm y}\operatorname{|}P _ {\mathrm y})\\&\geqslant D _ {\mathrm {KL}}(P _ {\mathrm y}\|Q _ {\mathrm y}).\end{aligned}
上面的命题是这个定理的特殊情况。

当只考虑离散情况，讨论会有所简化，但已不必赘述了。