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}\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}\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}\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}\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}\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}\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}\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}\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}\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}\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}\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}\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}\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}$
上面的命题是这个定理的特殊情况。

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