Pinsker 不等式证明(Proof of Pinsker‘s Inequality)

Pinsker 不等式证明(Proof of Pinsker‘s Inequality)

防盗:https://blog.csdn.net/qq_21149391/article/details/126844824?spm=1001.2014.3001.5502

1. Statement:

$\sum_{i=1}^{n}p_i \log \frac{p_i}{q_i} \geq \frac{1}{2}\left ( \sum_{i=1}^{n}|p_i-q_i| \right )^2$

其中, 不等号左侧等价于 $D_{\rm KL}(P||Q)$ , 关于 KL散度可以看这篇介绍: KL Divergence 与 JS Divergence.

不等号右侧等价于 $2||P-Q||_{\rm TV} ^2$ , 其中 $||P-Q||_{\rm TV}$ 是分布PQ之间的Total Variation Distance, 记为 TV 距离, 关于 TV 距离可以看这篇的介绍: Total Variation Distance 总变差 - 知乎

需要注意的是不等式右侧的常数 $\frac{1}{2}$ : 当 KL 散度中的 log 是以 e 为底时, 这个常数为 $\frac{1}{2}$ ; 当 KL 散度中的 log 是以 2 为底时, 这个常数为 $\frac{1}{2 \ln 2}$ , 所以我们在网上会看到不同形式的 Pinsker’s Inequality.

2. 证明:

首先给出2.1的结论, 然后使用这个结论进行证明

2.1 KL散度的链式法则(Chain rule for KL divergence)

$D_{KL}(P(X,Y)||Q(X,Y))=\sum_{x,y} p(x,y)\log\frac{p(x,y)}{q(x,y)}\\ =\sum_{x,y} p(x)q(y|x) [\log \frac{p(x)}{q(x)}+\log \frac{p(y|x)}{q(y|x)}]\\ =\sum_x p(x)\log \frac{p(x)}{q(x)}\sum_y p(y|x) + \sum_x p(x) \sum_y p(y|x)\log\frac{p(y|x)}{q(y|x)}\\ =D_{KL}(P(X)||Q(X))+\sum_xp(x)D_{KL}(P(Y|X=x)||Q(Y|X=x))\\ =D_{KL}(P(X)||Q(X)) + D_{KL}(P(Y|X)||Q(Y|X))$

如果 , , 那么有

$D_{KL}(P(X,Y)||Q(X,Y))=D_{KL}(P_1(X)||Q_1(X))+D_{KL}(P_2(Y)||Q_2(Y))$

.

2.2 证明

Pinsker 定理等价于:

P, Q 是定义在 universe U 上的两个分布, 那么

$D_{KL}(P||Q)\geq \frac{1}{2}||P-Q||_1^2$

证明:

1) a special case

$P=\left\{\begin{matrix} 1 & w.p. & p \\ 0 & w.p. & 1-p \end{matrix}\right. \;\;\;\;\;\;Q =\left\{\begin{matrix} 1 & w.p. & q \\ 0 & w.p. & 1-q \end{matrix}\right.$

假设 , 令

$f(p,q)=p\log \frac{p}{q}+(1-p)\log\frac{p}{q} - \frac{1}{2}(2(p-q))^2$

当时, $\frac{\partial f}{\partial q}\leq 0$ , 且, 所以当 $q\leq p$ , 有 $f\geq 0$

2) a general case

令 $A\subset U$ , 且 $A=\{x|p(x)\leq q(x)\}$ , 且:

$P_A=\left\{\begin{matrix} 1 & w.p. & \sum_{x\in A}p(x) \\ 0 & w.p. & \sum_{x \notin A}p(x) \end{matrix}\right. \;\;\;\;\;\;Q_A =\left\{\begin{matrix} 1 & w.p. & \sum_{x \in A}q(x) \\ 0 & w.p. & \sum_{x \notin A}q(x) \end{matrix}\right.$

那么:

$||P-Q||_1 = \sum_x |p(x)-q(x)|=||P_A-Q_A||_1$

---- (1).

定义一个随机变量 Z, 且 Z 满足:

$Z=\left\{\begin{matrix} 1 &, & if \;\; x \in A\\ 0 & , & if \;\; x \notin A \end{matrix}\right.$

有:

$D_{KL}(P||Q)=D_{KL}(P(Z)||Q(Z))+D_{KL}(P||Q|Z)$

因为:

$D_{KL}(P(Z)||Q(Z)) = D(P_A||Q_A)$

且

$P(P||Q|Z)\geq 0$

结合(1)和special case有:

$D_{KL}(P||Q)\geq D_{KL}(P_A||Q_A)\geq \frac{1}{2}||P_A-Q_A||_1^2\geq \frac{1}{2}||P-Q||_1^2$
相关阅读:
Go语言进阶，并发通道机制搭建一个可注册昵称的聊天室
 R语言中实现马尔可夫链蒙特卡罗MCMC模型
 Vue（模板语法1）
【纠错】遗传算法求解VRP计算车辆容量限制的代码有bug
【运维小知识】（一）——centos系统安装（小白入门级）
Java生成SSL证书
 【数据恢复篇】浅谈FTK Imager数据恢复功能
 线上Timeout waiting for connection from pool问题分析和解决方案
 C++ 实现运算符重载
 ABAP 导入Excel表示例程序
原文地址：https://blog.csdn.net/qq_21149391/article/details/126844824

1. Statement:

2. 证明:

2.1 KL散度的链式法则(Chain rule for KL divergence)

2.2 证明