確率分布間の全変動距離

abstract　確率分布間の全変動距離を定義します。また、この定義と同値な条件を紹介し、証明を与えます。

1　Introduction

二つの確率分布の間の距離の例に全変動距離があります。以下、議論を簡単にするため、離散型の確率分布だけを考えます。二つの確率分布の確率質量関数をそれぞれ $${p(x), q(x)}$$ と表すとき、

$$
\begin{align*}
d_{TV}(p, q) &:= \frac{1}{2}\sum_{x=-\infty}^{\infty}|p(x)-q(x)|
\end{align*}
$$

のことを確率分布 $${p(x),q(x)}$$ の間の全変動距離（total variation distance）といいます。

このnoteでは、全変動距離が距離の公理を満たすことを確認します。また同値な定義を紹介し、証明を与えます。

2　全変動距離が距離の公理を満たすこと

$${X}$$ を集合とするとき、関数 $${d:X\times X\rightarrow\mathbb{R}}$$ が距離（distance）であるとは、以下の三条件を満たす場合を指します。この三条件を距離の公理といいます。
①　非退化性　$${d(x,y)=0}$$ ならば $${x=y}$$。その逆も正しい。
②　対称性　$${d(x,y)=d(y,x)}$$
③　三角不等式　$${d(x,z)\leq d(x,y) + d(y,z)}$$

定理　全変動距離は、離散型の確率分布全体の集合上に距離を定めます。つまり距離の公理を満たします。

証明　以下、$${p(x),q(x),r(x)}$$ を離散型確率分布の確率質量関数とします。非退化性は、すべての $${x}$$ について $${a_x\geq 0}$$ のとき

$$
\begin{align*}
\displaystyle\sum_{x=-\infty}^{\infty}a_x&=0
\end{align*}
$$

ならば $${a_x= 0}$$ が成り立つことからわかります。対称性は、$${|p(x)-q(x)|=|q(x)-p(x)|}$$ に注意すれば以下のように確認できます。

$$
\begin{align*}
d_{TV}(p,q) = \frac{1}{2}\sum_{x=-\infty}^{\infty}|p(x)-q(x)| =  \frac{1}{2}\sum_{x=-\infty}^{\infty}|q(x)-p(x)| = d_{TV}(q, p)
\end{align*}
$$

三角不等式は、絶対値に成り立つ三角不等式

$$
|p(x)-r(x)|\leq |p(x)-q(x)|+|q(x)-r(x)|
$$

に注意すれば、以下のように確認できます。

$$
\begin{align*}
d_{TV}(p(x), r(x)) &=\frac{1}{2}\sum_{x=-\infty}^{\infty}|p(x)-r(x)|\\
&\leq \frac{1}{2}\sum_{x=-\infty}^{\infty}\left(|p(x)-q(x)|+|q(x)-r(x)|\right)\\
&= \frac{1}{2}\sum_{x=-\infty}^{\infty}|p(x)-q(x)|+ \frac{1}{2}\sum_{x=-\infty}^{\infty}|q(x)-r(x)|\\
&= d_{TV}(p, q) + d_{TV}(q, r)
\end{align*}
$$

以上で、全変動距離が距離の公理を満たすことが証明できました。■

3　全変動距離の別の定義の方法

関数 $${h(x)}$$ に対して、$${\|h\|_{\infty}:=\displaystyle\sup_{x}|h(x)|}$$ を関数 $${h(x)}$$ の一様ノルムといいます。$${\sup}$$ は上限という意味ですが、分かりづらければ最大値 $${\max}$$ と読み替えても便宜上差し支えありません。

実は、全変動距離は以下のように定義することもできます。

定理　以下の等式が成り立つ。

$$
\begin{align*}
d_{TV}(p, q) &= \frac{1}{2}\sup_{h:\|h\|_{\infty}\leq 1}\left(\mathbb{E}_{X\sim p(x)}[h(X)]-\mathbb{E}_{X\sim q(x)}[h(X)]\right)
\end{align*}
$$

ただし、$${\mathbb{E}_{X\sim p(x)}[h(X)]}$$ は確率分布 $${p(x)}$$ における統計量 $${h(X)}$$ の期待値です。$${\mathbb{E}_{X\sim q(x)}}$$ についても同様とします。

この全変動距離の定義は、Steinの方法に代表される正規近似の成立具合を評価する議論など、統計学や機械学習のさまざまな場面で役に立ちます。

4　第3節の定理の証明

右辺の最大値が全変動距離になること、そして一様ノルムが $${\|h\|_{\infty}\leq 1}$$ の関数 $${h(x)}$$ のなかに最大値を達成するような関数が存在することを示します。定理を証明する準備として、4.1節の補題を準備します。

4.1　定理を証明するための準備

補題　$${p(x)-q(x)\geq 0}$$ が成り立つ $${x}$$ の値全体を $${\mathcal{X}_{+}}$$、$${p(x)-q(x)< 0}$$ が成り立つ $${x}$$ の値全体を $${\mathcal{X}_{-}}$$ と表すことにします。このとき、

$$
\begin{align*}
\sum_{x\in\mathcal{X}_{+}}(p(x)-q(x)) &= \sum_{x\in\mathcal{X}_{-}}(q(x)-p(x))
\end{align*}
$$

が成り立ちます。特に、$${\displaystyle d_{TV}(p,q)=\sum_{x\in\mathcal{X}_{+}}(p(x)-q(x))}$$ が成り立ちます。

証明　確率の総和が $${1}$$ であることに注意すれば、以下のように証明できます。

$$
\begin{align*}
\sum_{x\in\mathcal{X}_{+}}(p(x)-q(x)) &= \left(1-\sum_{x\in\mathcal{X}_{-}}p(x)\right)-\left(1-\sum_{x\in\mathcal{X}_{-}}q(x)\right)\\
&= \sum_{x\in\mathcal{X}_{-}}(-p(x)+q(x))
\end{align*}
$$

また、全変動距離を $${\mathcal{X}_{+}}$$ と $${\mathcal{X}_{-}}$$ で表すことで

$$
\begin{align*}
d_{TV}(p, q) &= \frac{1}{2}\left\{\sum_{x\in\mathcal{X}_{+}}|p(x)-q(x)| + \sum_{x\in\mathcal{X}_{-}}|p(x)-q(x)|\right\}\\
&= \frac{1}{2}\left\{\sum_{x\in\mathcal{X}_{+}}(p(x)-q(x)) + \sum_{x\in\mathcal{X}_{-}}(-p(x)+q(x))\right\}\\
&= \sum_{x\in\mathcal{X}_{+}}(p(x)-q(x))
\end{align*}
$$

が従います。■

4.2　第3節の定理の右辺が全変動距離で抑えられること

$${\displaystyle\left|\sum_{x=-\infty}^{\infty}a_x\right|\leq \sum_{x=-\infty}^{\infty}|a_x|}$$ と $${|ab|\leq|a||b|}$$ を用いると、右辺を以下のように上から抑えることができます。

$$
\begin{align*}
\left|\mathbb{E}_{X\sim p(x)}[h(X)] - \mathbb{E}_{X\sim q(x)}[h(X)]\right|
&= \left|\sum_{x=-\infty}^{\infty}h(x)p(x) - \sum_{x=-\infty}^{\infty}h(x)q(x)\right|\\
&= \left|\sum_{x=-\infty}^{\infty}h(x)(p(x) - q(x))\right|\\
&\leq \sum_{x=-\infty}^{\infty}|h(x)||p(x)-q(x)|
\end{align*}
$$

さらに補題で導入した集合 $${\mathcal{X}_{+}}$$, $${\mathcal{X}_{-}}$$ を用いて式変形を続けると、以下のようになります。 ここで、四行めには一様ノルムの定義を用いました。

$$
\begin{align*}
&\sum_{x=-\infty}^{\infty}|h(x)||p(x)-q(x)|\\
&= \sum_{x\in\mathcal{X}_{+}}|h(x)||p(x)-q(x)|+\sum_{x\in\mathcal{X}_{-}}|h(x)||p(x)-q(x)|\\
&= \sum_{x\in\mathcal{X}_{+}}|h(x)|(p(x)-q(x))+\sum_{x\in\mathcal{X}_{-}}|h(x)|(-p(x)+q(x))\\
&\leq \sum_{x\in\mathcal{X}_{+}}(p(x)-q(x))+\sum_{x\in\mathcal{X}_{-}}(-p(x)+q(x))\\
&= 2\sum_{x\in\mathcal{X}_{+}}(p(x)-q(x))\\
&= 2d_{TV}(p, q)
\end{align*}
$$

得られた不等式から、定理の右辺は全変動距離を用いて上から抑えられることがわかります。

$$
\begin{align*}
\frac{1}{2}\sup_{h:\|h\|_{\infty}\leq 1}\left(\mathbb{E}_{X\sim p(x)}[h(X)]-\mathbb{E}_{X\sim q(x)}[h(X)]\right) &\leq d_{TV}(p, q)
\end{align*}
$$

4.3　等号が成立するような関数が存在すること

以下の関数 $${h(x)}$$ の場合には4.2節で示した不等式に等号が成立していることを確認します。

$$
\begin{align*}
h(x) &= \begin{cases}1&x\in\mathcal{X}_{+}\\-1&x\in\mathcal{X}_{-}\end{cases}
\end{align*}
$$

このとき、

$$
\begin{align*}
&\mathbb{E}_{X\sim p(x)}[h(X)] - \mathbb{E}_{X\sim q(x)}[h(X)]\\
&= \sum_{x=-\infty}^{\infty}h(x)p(x) - \sum_{x=-\infty}^{\infty}h(x)q(x)\\
&= \sum_{x=-\infty}^{\infty}h(x)(p(x)-q(x))\\
&= \sum_{x\in\mathcal{X}_{+}}h(x)(p(x)-q(x))+\sum_{x\in\mathcal{X}_{-}}h(x)(p(x)-q(x))\\
&= \sum_{x\in\mathcal{X}_{+}}(p(x)-q(x))+\sum_{x\in\mathcal{X}_{-}}(-p(x)+q(x))\\
&= 2\sum_{x\in\mathcal{X}_{+}}(p(x)-q(x)))\\
&= 2d_{TV}(p ,q)
\end{align*}
$$

が成り立つので、以下のように4.2節で示した不等式の等号が成り立つことがわかります。

$$
\begin{align*}
\frac{1}{2}\sup_{h:\|h\|_{\infty}\leq 1}\left(\mathbb{E}_{X\sim p(x)}[h(X)]-\mathbb{E}_{X\sim q(x)}[h(X)]\right) &= d_{TV}(p, q)
\end{align*}
$$

以上で第3節に掲げた定理を証明できました。

Acknowledgement

日頃からサポートしていただいている方々、株式会社すうがくぶんかの皆さんに感謝申し上げます。