分布の距離と混合時間 - バナナでもわかる話

前回までで、MCMCの話に必要な基礎的な話は大体終わりです。
bananarian.hatenablog.com

細かく見てくとまだまだ話はあるわけですが、その辺は触っているとキリがないので触りません。
今回は知っていなくてもまあMCMCの話は雰囲気で理解出来るけども、知ることでMCMCをより深く理解できるカップリングという概念を説明するために、一旦寄り道して分布の距離の概念と混合時間という概念の説明をします。少々込み入った話になりますので苦しい方は飛ばしてもらってもMCMCを理解するうえで支障はありません。

全変動ノルム

まず、可測空間 $(E,ε)$ 上の二種類の確率分布として $\mu_1,\mu_2$ を考えます。何を言っているか分からんという方のために例をあげると

$E=(1,2),\mu_1=(0.8,0.2),\mu_2=(0.5,0.5)$ を考えると、これはどういう状況かというと $\mu_1$ の分布に従っている時、1が出る確率が0.8,2が出る確率は0.2ということを意味します。

今回は、この2つの分布の何らかの意味での距離、もしくは違いを数値的に評価したいとします。この時に考えられる評価方法の一つに全変動ノルムという概念があります。 $\mu_1,\mu_2$ の全変動ノルム $||||_{TV}$ は次のようになります。

$||\mu_1-\mu_2||_{TV}= \frac{1}{2}(|0.8-0.5|+|0.2-0.5|)=0.3$

まさに分布の違いを表していますね。

次のように連続の分布を二つ書いてみるとわかりやすいです。
f:id:bananarian:20180829151331p:plain

この絵の二つの分布における全変動ノルムは黄色の部分と緑の部分を足したものを2で割ったものになります。共通部分は紫色の部分なので、まさに違いを表したものになりますね。

前回までのマルコフ連鎖の話の確認

ここで前回までのマルコフ連鎖の話を一瞬確認しておきます。
要は適当な条件の下で確率行列 $P^n$ は時間 $n$ を大きくしていくと不変確率分布 $Π$ に収束するというわけでした。

混合時間

・全変動ノルムを用いて2つの分布の距離を評価することが出来る
・ $P^n$ は $Π$ に収束する

ここから、どれくらいnを大きく取るとおおよそ収束したとみなせるかという考え方が必要になってきます。

これが混合時間です。

数式で表してみます。 $P^n$ のx行を $P^n(x,・)$ と書くことにします。また、 $P^n(x,・)$ の収束先を $Π(x,・)$ と書くことにします。

更に、全ての $x \in E$ のうち、ある $n＞0$ において $d(n)=max_x ||P^n(x,・)-Π(x,・)||_{TV}$ とおくことにします。

そして $\epsilon \in (0, 1 ]$ なるεを用意してやると、

この時混合時間 $t_{mix}$ は次のようになります。

$t_{mix}( \epsilon )=inf\{ n>0: d(n)≦\epsilon \}$

例えばεに $\frac{1}{4}$ を入れるとこのようになります。
$t_{mix}=t_{mix}(\frac{1}{4})$

正直 $\frac{1}{4}$ に意味はありません。別に4じゃなくて3や2でも良いわけですが、評価精度に合わせていじります。

カエルの例でチェック

毎度おなじみのカエルの例です。

石1,石2があって、どちらかの石の上にカエルが乗っています。そして、1秒後に
・石1にいて石2に乗り移る確率が50%
・石1にいてそのまま石1に居続ける確率が50%
・石2にいて石1に移る確率を80％
・石2にいてそのまま石2に居続ける確率が20％
であるとします。この時推移確率行列Pは次のようになる。
$P=\left( \begin{array}{ccc} 0.5 & 0.5 \\ 0.8 & 0.2 \\ \end{array} \right)$