Pinskerの不等式の簡単な証明

 Pinskerの不等式とは, KLダイバージェンスと統計距離(total variation distance)の関係を表す不等式です. 本記事ではこれを紹介し, こちらの論文やYihong Wuの講義資料のTheorem 4.5に載っている非常にトリッキーな証明を紹介します.

有限集合$\Omega$を値域とする二つの確率変数$X,Y$に対して

• 統計距離: $d_{\mathrm{TV}}(X,Y) = \frac{1}{2}\sum_{x\in \Omega}|\Pr[X=x] - \Pr[Y=y]| = \sup_{A\subseteq \Omega}|\Pr[X\in A] - \Pr[Y \in A]|$.
• KLダイバージェンス: $\mathrm{KL}(X||Y)=\sum_{a\in\mathsf{supp}(Y)}\Pr[X=a]\ln\frac{\Pr[X=a]}{\Pr[Y=a]}$.

定理 (Pinskerの不等式)

$$d_{\mathrm{TV}}(X,Y) \leq \sqrt{\frac{1}{2}\mathrm{KL}(X||Y)}.$$

証明では, KLダイバージェンスに関する以下のデータ処理不等式(data processing inequality)を認めることにします.

補題 (データ処理不等式)

$\Omega,\Omega'$を有限集合とする. 任意の関数$f\colon \Omega\to\Omega'$と$\Omega$上に値をとる任意の確率変数$X,Y$に対し
$$\mathrm{KL}(f(X),f(Y)) \leq \mathrm{KL}(X,Y).$$

KLダイバージェンス$\mathrm{KL}(X||Y)$は直感的には二つの確率変数$X,Y$の識別しにくさを表す指標であり, データ処理不等式とは二つのデータ$X,Y$をアルゴリズム$f$で処理して得られるデータ$f(X),f(Y)$を考えたとき, データ処理不等式とはデータを処理しても識別しにくさは上がらないことを意味します.

一般にデータ処理不等式は決定的アルゴリズム$f$を乱択アルゴリズムに置き換えても成り立ちます. こちらの講義資料が参考になると思います.

Pinskerの不等式の証明.

大まかな流れとしてはデータ処理不等式を用いて$01$値確率変数の場合に帰着して, あとは積分を計算します.

統計距離の定義および$\Omega$が有限であることから, ある集合$E\subseteq \Omega$が存在して$d_{\mathrm{TV}}(X,Y)=\Pr[X\in A] - \Pr[Y \in A]$が成りたちます. この集合$A$の指示関数を$f$とします. すなわち$f\colon\Omega\to\{0,1\}$は$x\in A$ならば$f(x)=1$, そうでなければ$f(x)=0$です.

データ処理不等式から$\mathrm{KL}(f(X),f(Y))\leq \mathrm{KL}(X,Y)$なので, ベルヌーイ試行$f(X),f(Y)$に対してPinskerの不等式が証明できれば証明が完了します.

では, $X,Y$がそれぞれベルヌーイ試行で$X\sim\mathrm{Ber}(p),Y\sim\mathrm{Ber}(q)$とします (すなわち$\Pr[X=1]=p,\Pr[Y=1]=q$). このとき

• $d_{\mathrm{TV}}(X,Y)=|p-q|$,
• $\mathrm{KL}(X||Y)=p\ln\frac{p}{q} + (1-p)\ln\frac{1-p}{1-q}$

です. 従って, 任意の$p,q\in[0,1]$に対して不等式
$$\begin{align} 2(p-q)^2 \leq p\ln\frac{p}{q} + (1-p)\ln\frac{1-p}{1-q} \end{align}$$
を示せば良いです. $p,q\in\{0,1\}$の場合は4通り試せば明らかに成り立つことが確認できます.

$p,q\in(0,1)$とし, $f(x) = p\log x + (1-p)\log(1-x)$とします. すると
$$\begin{align*} (\mathrm{RHS}) &= f(p) - f(q) \\ &= \int_q^p f'(x)\mathrm{d}x \\ &= \int_q^p \frac{p-x}{x(1-x)}\mathrm{d}x \\ &\geq 4\int_q^p (p-x)\mathrm{d}x \\ &= 2(p-q)^2 = (\mathrm{LHS}) \end{align*}$$
より証明を得ます. (証明終)