不等式 Pinsker's Inequality
$\Omega$を標本空間都市, $p,q$を$\Omega$上の確率分布とする.$A\subset \Omega$とする.
\begin{equation} 2\left(p(A)-q(A)\right)^2\leq \text{KL}(p,q) \end{equation}
ただし,
\begin{equation}
\text{KL}(p,q) = \sum_{x\in\Omega}p(x)\ln\dfrac{p(x)}{q(x)}
\end{equation}
まず, 式1を証明する.
\begin{equation} \sum_{x\in B}p(x)\dfrac{p(x)}{q(x)} \geq p(B)\dfrac{p(B)}{q(B)} \tag{1} \end{equation}
$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{eqnarray}
\sum_{x\in B}p(x)\dfrac{p(x)}{q(x)}
&=&\sum_{x\in B}p_B(x)p(B)\ln\dfrac{p_B(x)p(B)}{q_B(x)q(B)}\\
&=&p(B)\sum_{x\in B}p_B(x)\ln\dfrac{p_B(x)p(B)}{q_B(x)q(B)}\\
&=&p(B)\sum_{x\in B}p_B(x)\ln\left(\dfrac{p_B(x)}{q_B(x)}+\ln\dfrac{p(B)}{q(B)}\right)\\
&=&p(B)\sum_{x\in B}p_B(x)\ln\dfrac{p_B(x)}{q_B(x)}
+ p(B)\sum_{x\in B}p_B(x)\ln\dfrac{p(B)}{q(B)}\\
&=&p(B)\text{KL}(p_B,q_B) + p(B)\ln\dfrac{p(B)}{q(B)}\\
&\geq&p(B)\ln\dfrac{p(B)}{q(B)} \ \ (\because \text{KL}(p_B,q_B)\geq 0)
\end{eqnarray}
$a=p(A)$, $b=q(A)$とおく.
\begin{eqnarray} \text{KL}(p,q) &=&a\ln\dfrac{a}{b} + (1-a)\ln\dfrac{1-a}{1-b}\\ &=&\int_{a}^{b}\left(-\dfrac{a}{x}+\dfrac{1-a}{1-x}\right)\\ &=&\int_{a}^{b}\dfrac{x-a}{x(1-x)}dx\\ &\geq&\int_{a}^{b}4(x-a)dx \ \ (\because x(1-x)\leq 1/4)\\ &=&2(b-a)^2 \end{eqnarray}
