ピンスカーの不等式（Pinsker’s Inequality）

ピンスカーの不等式の意味

$P, Q$ は（同じ可測空間 $(X,\mathcal{F})$ に対する）確率分布とします。以下では、離散型の確率分布とします。

$\|P-Q\|$ は $L_1$ ノルムです：
$\|P-Q\|=\displaystyle\sum_{x\in X}|P(x)-Q(x)|$

$D(P||Q)$ はカルバックライブラー情報量と呼ばれる量です：
$D(P||Q)=\displaystyle\sum_{x\in X}P(x)\log\dfrac{P(x)}{Q(x)}$

$\delta(P,Q)$ は全変動距離(total variation distance)と呼ばれる量です：
$\delta(P,Q)=\displaystyle\sup_{A\in\mathcal{F}}|P(A)-Q(A)|$

ピンスカーの不等式は、カルバックライブラー情報量と別の量との関係を表す不等式です。

２つの不等式が同値であること

実は、$L_1$ ノルムと全変動距離の間には、以下の関係が成立します：
$\|P-Q\|=2\delta(P,Q)$
この関係式より、冒頭で述べた赤い不等式と青い不等式は同値であることが分かります。

大雑把に言うと、
・$\|P-Q\|$ は $P$ と $Q$ の差を足し合わせたもの
・$\delta(P,Q)$ は $P$ が $Q$ より大きい部分に限って差を足し合わせたもの
です。
$P$、$Q$ はいずれも確率分布なので、
「$P$ が $Q$ より大きい部分に限って差を足し合わせたもの」と「$Q$ が $P$ より大きい部分に限って差を足し合わせたもの」は一致します。
よって、
$\|P-Q\|=2\delta(P,Q)$
が成立します。（式できちんと証明することも難しくありません）

ピンスカーの不等式の証明

1. $\|P-Q\|=\|P’-Q’\|$ となるようなベルヌーイ分布 $P’,Q’$ を構成する
2. このとき $D(P||Q)\geq D(P’||Q’)$ が成立する
3. ベルヌーイ分布 $P’,Q’$ ではピンスカーの不等式が成立する
→以上3つの結果より $\|P-Q\|\leq\sqrt{2D(P||Q)}$

このページでは、手順3のみ説明します。手順２はカルバックライブラー情報量のチェインルールを使います。詳細はPinsker’s inequality and its applications to lower bounds
をご参照ください。

手順3. ベルヌーイ分布の場合

$P$ は確率 $p$ で $1$、確率 $1-p$ で $0$ となる確率分布、
$Q$ は確率 $q$ で $1$、確率 $1-q$ で $0$ となる確率分布とします。

このとき、
$2D(P||Q)-\|P-Q\|^2\\
=2p\log\dfrac{p}{q}-2(1-p)\log\dfrac{1-p}{1-q}-2(p-q)^2$
となります。上式を $f$ とおき、地道に偏微分 $\dfrac{\partial f}{\partial q}$ を計算すると、
$q\geq p$ のとき $\dfrac{\partial f}{\partial q}\geq 0$
$q\leq p$ のとき $\dfrac{\partial f}{\partial q}\leq 0$
（さらに $q=p$ のとき $f=0$）
となるので、$f\geq 0$ であることが分かります。

つまり、$\|P-Q\|^2\leq 2D(P||Q)$ であることが証明されました。

次回は ハードマージンSVMの定式化を丁寧にやってみる を解説します。