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$
相关阅读:
ZZNUOJ_C语言1027：判断水仙花数(完整代码)
使用idea中git创建分支，并推送代码
 基于FPGA的正弦PWM产生系统verilog实现
 【王道】操作系统OS第三章存储系统(三)
牛批阿里P8熬夜冠军手码的Docker容器+k8s技术PDF,你还等啥呢
 常见编写JavaScript代码时容易出现的错误（2）
秋招将临如何准备算法面试、回答算法面试题
 如何提升网站排名优化（百度SEO优化，轻松提升排名）
DOM——文件对象模型（事件响应链、阻止冒泡和系统默认事件、事件代理、样式操作css、防抖和节流、预加载和懒加载、async,defer）
《计算机组成原理/CSAPP》网课总结（二）——编译原理基础
原文地址：https://blog.csdn.net/qq_21149391/article/details/126844824

1. Statement:

2. 证明:

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

2.2 证明