不等式 Pinsker's Inequality

まず, 式1を証明する.

$$\begin{array}{}\text{(1)}& \sum _{x\in B}p(x){\displaystyle \frac{p(x)}{q(x)}}\ge p(B){\displaystyle \frac{p(B)}{q(B)}}\end{array}$$

$p(B)=\sum _{x\in B}p(x),q(B)=\sum _{x\in B}q(x)$とし,$p_B(x)=p(x)/p(B)$, $q_B(x)=q(x)/q(B)$とする.

このとき,
$$\begin{array}{rcl}\sum _{x\in B}p(x){\displaystyle \frac{p(x)}{q(x)}}& =& \sum _{x\in B}{p}_B(x)p(B)\ln {\displaystyle \frac{p_B(x)p(B)}{q_B(x)q(B)}}\\ & =& p(B)\sum _{x\in B}{p}_B(x)\ln {\displaystyle \frac{p_B(x)p(B)}{q_B(x)q(B)}}\\ & =& p(B)\sum _{x\in B}{p}_B(x)\ln ({\displaystyle \frac{p_B(x)}{q_B(x)}}+\ln {\displaystyle \frac{p(B)}{q(B)}})\\ & =& p(B)\sum _{x\in B}{p}_B(x)\ln {\displaystyle \frac{p_B(x)}{q_B(x)}}+p(B)\sum _{x\in B}{p}_B(x)\ln {\displaystyle \frac{p(B)}{q(B)}}\\ & =& p(B)\text{KL}(p_B,q_B)+p(B)\ln {\displaystyle \frac{p(B)}{q(B)}}\\ & \ge & p(B)\ln {\displaystyle \frac{p(B)}{q(B)}}(\because \text{KL}(p_B,q_B)\ge 0)\end{array}$$

$a=p(A)$, $b=q(A)$とおく.

$$\begin{array}{rcl}\text{KL}(p,q)& =& a\ln {\displaystyle \frac{a}{b}}+(1-a)\ln {\displaystyle \frac{1-a}{1-b}}\\ & =& {\int }_a^b(-{\displaystyle \frac{a}{x}}+{\displaystyle \frac{1-a}{1-x}})\\ & =& {\int }_a^b{\displaystyle \frac{x-a}{x(1-x)}}dx\\ & \ge & {\int }_a^{b}4(x-a)dx(\because x(1-x)\le 1/4)\\ & =& 2(b-a{)}^2\end{array}$$