maximal coupling

abstract　全変動距離を評価する方法にmaximal couplingがあります。今回はmaximal couplingを導入し、その応用としてPoisson近似の精度を知るために全変動距離を評価するLe Camの定理を証明します。

1　Introduction

確率変数 $${X, Y}$$ の同時分布を考えます。$${X}$$ の周辺分布と $${Y}$$ の周辺分布を固定した状況で、$${X}$$ と $${Y}$$ が同じ値を取る確率 $${\mathbb{P}[X=Y]}$$ が最大になるような同時分布を探してください。このような同時分布が存在する場合、この分布に従う確率変数 $${\left(\hat{X},\hat{Y}\right)}$$ をmaximal couplingといいます。

maximal couplingの定義を理解するために、単純な例を一つ考えておきましょう。確率変数 $${X, Y}$$ が同じ離散型の確率分布に従うとし、この確率質量関数を $${p(x)}$$ と表すことにします。この場合、maximal coupling $${\left(\hat{X}, \hat{Y}\right)}$$ は存在し、特にその同時確率質量関数は以下のようになります。

$$
\begin{align*}
\mathbb{P}\left[\hat{X}=x, \hat{Y}=y\right] &= \begin{cases}
p(x)&x=y\\
0&x\neq y
\end{cases}
\end{align*}
$$

さて実際に興味があるのは、確率変数 $${X, Y}$$ の分布、つまり周辺分布が異なる場合のmaximal couplingです。この場合のmaximal couplingは確率変数 $${X}$$ と $${Y}$$ が従う確率変数間の全変動距離を評価する際に役に立ちます。

そこでこのnoteでは、離散型確率分布の場合にmaximal couplingが存在することを証明し、全変動距離との関係を導きます。さらにこの事実の応用として、二項分布のPoisson近似の精度を評価します。

2　maximal couplingの存在と構成

周辺分布が離散型の確率分布の場合にmaximal couplingが存在することを示します。特に、具体的に周辺分布の情報からmaximal couplingの同時確率質量関数を構成します。

2.1　定理の紹介

以下の定理によって、離散型の確率分布の場合にmaximal couplingを構成できます。ここで、$${x\land y=\min(x, y)}$$ を $${x,y}$$ の最小値を表す記号とします。

定理　確率変数 $${X, Y}$$ は離散型の確率分布に従うとし、確率質量関数を $${p_X(x), p_Y(y)}$$ と表すとします。このとき、以下のように定義した関数 $${p(x, y)}$$ は確率変数 $${(X, Y)}$$ の同時密度関数になり、特にmaximal couplingを与える。

$$
\begin{align*}
p(x, y) &= \begin{cases}
p_X(x)\land p_Y(x)& x=y\\
\displaystyle\frac{\left(p_X(x)-p_X(x)\land p_Y(x)\right)\left(p_Y(y)-p_X(y)\land p_Y(y)\right)}{1-\sum_{z}p_X(z)\land p_Y(z)}&x\neq y
\end{cases}
\end{align*}
$$

2.2節ではこの関数が同時確率質量関数を与えると仮定して、maximal couplingを与えることを示します。2.3節では、この関数が同時確率質量関数を与えることを示します。

2.2　maximal couplingであることの証明

もし関数 $${p(x,y)}$$ が同時確率質量関数だとすると、これはmaximal couplingを与えます。実際、$${\mathbb{P}[X=z, Y=z]\leq \mathbb{P}[X=z]\land\mathbb{P}[Y=z]}$$ から以下の不等式が従います。

$$
\begin{align*}
\mathbb{P}[X=Y] = \sum_{z}\mathbb{P}[X=z, Y=z] \leq \sum_{z}\mathbb{P}[X=z]\land\mathbb{P}[Y=z]
\end{align*}
$$

右辺は $${\displaystyle\sum_{z}p(z,z)}$$ に等しいので、$${p(x, y)}$$ を確率質量関数にもつ同時分布はmaximal couplingを与えていることがわかります。

2.3　同時確率質量関数を与えていることの証明

関数 $${p(x,y)}$$ が同時確率質量関数を与えることを示すには、周辺分布の確率質量関数について

$$
\begin{align*}
\sum_{y}p(x, y)=p_X(x),\quad \sum_{x}p(x, y)=p_Y(y)
\end{align*}
$$

を確認すれば十分です。以下では $${\displaystyle\sum_{y}p(x, y)=p_X(x)}$$ を示します。$${p_X(x)\land p_Y(x)=p_X(x)}$$ が成り立つ場合と $${p_X(x)\land p_Y(x)=p_Y(x)}$$ が成り立つ場合とに分けて考えてみましょう。

$${p_X(x)\land p_Y(x)=p_X(x)}$$ が成り立つ場合には、$${y\neq x}$$ に対して

$$
\begin{align*}
p(x, y) &\propto \left(p_X(x)-p_X(x)\land p_Y(x)\right)\left(p_Y(y)-p_X(y)\land p_Y(y)\right)\\
&=  \left(p_X(x)-p_X(x)\right)\left(p_Y(y)-p_X(y)\land p_Y(y)\right)\\
&= 0
\end{align*}
$$

が成り立つので、以下のようにして $${\displaystyle\sum_{y}p(x, y)=p_X(x)}$$ が確認できます。

$$
\begin{align*}
\displaystyle\sum_{y}p(x,y) = p(x,x) = p_X(x) \land p_Y(x)=p_X(x)
\end{align*}
$$

$${p_X(x)\land p_Y(x)=p_Y(x)}$$ が成り立つ場合には、$${x\neq y}$$ の場合の $${p(x,y)}$$ の分子について、以下の等式が成り立ちます。ここで5行めには余事象の公式を用いました。2行めと6行めには $${p_X(x)\land p_Y(x)=p_Y(x)}$$ を用いました。　

$$
\begin{align*}
&\sum_{y\neq x}(p_X(x)-p_X(x)\land p_Y(x))(p_Y(y)-p_X(y)\land p_Y(y))\\
&= \sum_{y\neq x}(p_X(x)-p_Y(x))(p_Y(y)-p_X(y)\land p_Y(y))\\
&= (p_X(x)-p_Y(x))\sum_{y\neq x}(p_Y(y)-p_X(y)\land p_Y(y))\\
&= (p_X(x)-p_Y(x))\left(\sum_{y\neq x}p_Y(y)-\sum_{y\neq x}p_X(y)\land p_Y(y)\right)\\
&= (p_X(x)-p_Y(x))\left(1-p_Y(x)-\sum_{y\neq x}p_X(y)\land p_Y(y)\right)\\
&= (p_X(x)-p_Y(x))\left(1-\sum_{y}p_X(y)\land p_Y(y)\right)\\
\end{align*}
$$

従って、以下のようにして $${\displaystyle\sum_{y}p(x, y)=p_X(x)}$$ が確認できます。

$$
\begin{align*}
\sum_{y}p(x, y) &= p(x, x) + \sum_{y\neq x}p(x, y)\\
&= p_Y(x) + (p_X(x) - p_Y(y))\frac{1-\sum_{z}p_X(z)\land p_Y(z)}{1-\sum_{z}p_X(z)\land p_Y(z)}\\
&= p_X(x)
\end{align*}
$$

$${\displaystyle\sum_{x}p(x, y)=p_Y(y)}$$ についても同様に確認できます。以上で証明が完了しました。

3　全変動距離との関係

確率変数 $${X, Y}$$ が従う確率分布の間の全変動距離 $${d_{TV}(X, Y)}$$ は、次のように定義されるのでした[U]。

$$
\begin{align*}
d_{TV}(X, Y) := \frac{1}{2}\sum_{z}\left|p_X(z)-p_Y(z)\right|
\end{align*}
$$

ここで、$${p_X(x)}$$ は確率変数 $${X}$$ の確率質量関数、$${p_Y(y)}$$ は確率変数 $${Y}$$ の確率質量関数です。

実は、全変動距離はmaximal couplingを用いて評価することができます。

定理　$${\left(\hat{X}, \hat{Y}\right)}$$ を確率変数 $${X, Y}$$ のmaximal couplingと表します。このとき、$${X}$$ と $${Y}$$ が従う確率分布の間の全変動距離について以下の公式が成り立ちます。

$$
\begin{align*}
d_{TV}(X, Y) = \mathbb{P}\left[\hat{X}\neq\hat{Y}\right]
\end{align*}
$$

証明　次のように式変形することで証明できます。

$$
\begin{align*}
&\sum_{z}\left|p_X(z)-p_Y(z)\right|\\
&= \sum_{p_X(z)>p_Y(z)}(p_X(z)-p_Y(z)) + \sum_{p_X(z)\leq p_Y(z)}(p_Y(z)-p_X(z))\\
&= \sum_{p_X(z)>p_Y(z)}p_X(z) + \sum_{p_X(z)\leq p_Y(z)}p_Y(z) - \sum_{z}p_X(z)\land p_Y(z)\\
&= 2 -  \sum_{p_X(z)\leq p_Y(z)}p_X(z) - \sum_{p_X(z)>p_Y(z)}p_Y(z) - \sum_{z}p_X(z)\land p_Y(z)\\
&= 2\left(1 - \sum_{z}p_X(z)\land p_Y(z)\right)\\
&= 2\left(1 - \mathbb{P}[\hat{X}=\hat{Y}]\right)\\
&= 2\mathbb{P}\left[\hat{X}\neq\hat{Y}\right]
\end{align*}
$$

ここで、4行めは余事象の公式を使いました。■

4　Poisson近似の精度評価

二項分布 $${Bin(n,p)}$$ は確率 $${p}$$ が十分に小さいとき、期待値 $${\lambda=np}$$ のPoisson分布 $${Po(\lambda)}$$ に近似されることがあります。これを二項分布のPoisson近似といいます[K]。ところで実際のところ、Poisson近似はどれくらい良い近似になっているのでしょうか。この疑問に答えてくれる定理としてLe Camの定理[LC]を紹介します。

4.1　Le Camの定理

定理　確率変数 $${X_1,\cdots,X_n}$$ は独立に確率 $${p_1,\cdots,p_n}$$ のBernoulli分布に従っているとします。$${S_n=X_1+\cdots+X_n}$$、$${Y}$$ を期待値 $${\lambda=p_1+\cdots+p_n}$$ のPoisson分布 $${Po(\lambda)}$$ としたとき、以下の不等式が成り立ちます。

$$
\begin{align*}
d_{TV}(S_n, Y) &\leq \sum_{i=1}^{n}p_{i}^2
\end{align*}
$$

Le Camの定理の主張を具体的に考えてみます。例えば二項分布 $${Bin(100,0.01)}$$ の場合にPoisson近似を考えたとき、期待値が $${\lambda=100\times0.01=1}$$ のPoisson分布 $${Po(1)}$$ に近似しても全変動距離にして高々 $${0.01}$$ しか差がないことが、Le Camの定理の右辺からわかります。

実際、この場合の全変動距離をR言語を用いて計算すると $${0.00278}$$ ほどしかないことが確認できます。

# 二項分布とPoisson分布の全変動距離の計算
tv_double <- 0    # 2*全変動距離の結果を代入するためのオブジェクト

for (x in 0:1e+06) {
    prob_diff <- abs(dbinom(x, size=100, prob=0.01) - dpois(x, lambda=1)) 
    tv_double <- tv_double + prob_diff
}

(1/2)*tv_double   # -> 0.002775295

4.2　全変動距離に関する補題

全変動距離に関する以下の補題は、Le Camの定理を証明する際に重要です。この補題の証明はmaximal couplingを用いて与えることができます。

補題　確率変数 $${X_1,\cdots,X_n}$$ は独立、確率変数 $${Y_1,\cdots,Y_n}$$もまた独立とします。それぞれの総和を $${\displaystyle X=\sum_{i=1}^{n}X_i}$$, $${\displaystyle Y=\sum_{i=1}^{n}Y_i}$$ とします。このとき、以下の不等式が成り立ちます。

$$
\begin{align*}
d_{TV}(X, Y) &\leq \sum_{i=1}^{n}d_{TV}(X_i, Y_i)
\end{align*}
$$

証明　確率変数 $${X, Y}$$ が従う確率分布の間の全変動距離は、maximal coupling $${\left(\hat{X}, \hat{Y}\right)}$$ を用いて次のように表されるのでした。

$$
\begin{align*}
d_{TV}(X, Y) &= \mathbb{P}\left[\hat{X}\neq \hat{Y}\right]
\end{align*}
$$

ここでmaximal couplingの定義から、周辺分布を固定した確率変数 $${(X,Y)}$$ に対してどんな同時分布を想定したとしても $${\mathbb{P}\left[\hat{X}\neq \hat{Y}\right]\leq\mathbb{P}[X\neq Y]}$$ が成り立つので

$$
\begin{align*}
d_{TV}(X, Y) &\leq \mathbb{P}[X\neq Y]
\end{align*}
$$

が従うことに注意します。

確率変数 $${X_i, Y_i}$$ のmaximal couplingを $${\left(\hat{X_i}, \hat{Y_i}\right)}$$ と表し、特に$${\hat{X_1},\cdots,\hat{X_n}}$$ は独立、$${\hat{Y_1},\cdots,\hat{Y_n}}$$ は独立に取ります。このとき、$${X'=\hat{X_1}+\cdots+\hat{X_n}}$$ は $${X}$$ と同じ分布、 $${Y'=\hat{Y_1}+\cdots+\hat{Y_n}}$$ は $${Y}$$ と同じ分布に従います。従って周辺分布が同じなので、先ほどの不等式の右辺に $${(X', Y')}$$ を設定することができ

$$
\begin{align*}
d_{TV}(X, Y) &\leq \mathbb{P}[X'\neq Y']\\
&= \mathbb{P}\left[\sum_{i=1}^{n}\hat{X_i}\neq\sum_{i=1}^{n}\hat{Y_i}\right]\\
&\leq \mathbb{P}\left[\hat{X_1}\neq\hat{Y_1}\text{ or }\cdots\text{ or }\hat{X_n}\neq\hat{Y_n}\right]\\
&\leq \sum_{i=1}^{n}\mathbb{P}\left[\hat{X_i}\neq\hat{Y_i}\right]\\
&= \sum_{i=1}^{n}d_{TV}(X_i, Y_i)
\end{align*}
$$

が得られます。■

4.3　Le Camの定理の証明

4.2節の補題を用いて証明します。$${X_i}$$ を確率 $${p_i}$$ のBernoulli分布に従う確率変数、$${Y_i}$$ を期待値 $${p_i}$$ のPoisson分布とすれば、補題の確率変数 $${X}$$ は確率変数 $${S_n}$$ と同じ分布、補題の確率変数 $${Y}$$ は期待値 $${\lambda=p_1+\cdots+p_n}$$ のPoisson分布に従い、Le Camの定理の設定と一致します。

$${X_i, Y_i}$$ の全変動距離 $${d_{TV}(X_i, Y_i)}$$ を評価するために、max coupling $${\left(\hat{X_i},\hat{Y_i}\right)}$$ を取ります。max couplingの構成方法から

$$
\begin{align*}
\mathbb{P}\left[\hat{X_i}=\hat{Y_i}\right] &= \sum_{z=0}^{\infty}p_{X_i}(z)\land p_{Y_i}(z)\\
&= p_{X_i}(0)\land p_{Y_i}(0) + p_{X_i}(1)\land p_{Y_i}(0)\\
&= \min\left(1-p_i,e^{-p_i}\right) + \min\left(p_i,p_ie^{-p_i}\right)\\
&= 1-p_i+p_ie^{-p_i}\\
&= 1-p_i(1-e^{-p_i})\\
&\geq 1-p_i^2
\end{align*}
$$

が得られます。ここで、4行めと6行めでは微分を考えることでわかる不等式 $${1-p_i\leq e^{-p_i}}$$ を用いました。従って、$${d_{TV}(X_i, Y_i)\leq p_i^2}$$ が成り立ちます。

あとは、補題の右辺にこの結果を代入することで、定理で主張された不等式 $${\displaystyle d_{TV}(S_n,Y)\leq\sum_{i=1}^{n}p_i^2}$$ が得られます。

Acknowledgement

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

References

[K]　こんぴゅ, "ポアソン分布を導出する." note, 2017.
[LC]　Le Cam, Lucien. "An approximation theorem for the Poisson binomial distribution." (1960): 1181-1197.
[U]　Uchiba, Takayuki. "確率分布間の全変動距離." note, 2024.