マルコフ連鎖の収束のための条件とMCMCとの関係

前回までで不変分布はMCMCでどう役に立っているのかををざっと確認しました。
bananarian.hatenablog.com

今回は今までスルーしていた結局どういう条件の下で収束しているのかについてやります。

本当に収束の話を理解するためには、前にやったカップリングや混合時間に関する話も交えねばならないのですが、その辺は話がゴチャゴチャするので省略します。

確率行列 $P$ について

$Π=ΠP$

が成り立つような $Π$ を不変分布と呼び、
PはΠ-不変であると言う。

そして、MCMCにおいては不変分布が目標分布になるようなマルコフ連鎖を見つけてくることでサンプリングを行います。

まず、収束するための条件として、どの状態からでも有限回のステップで他のどの状態にでもいけるという性質を持つ必要があります。これを既約性と呼びます。

例えば下の例は既約性を持ちます。
$P=\left( \begin{array}{ccc} 0.5 & 0.5 \\ 0.8 & 0.2 \\ \end{array} \right)$

一方で下のような例では既約性を持ちません。
$P=\left( \begin{array}{ccc} 0.5 & 0 \\ 0.8 & 0.2 \\ \end{array} \right)$

状態2から状態1にはいけますが、状態1から状態2にはいけませんね。

元の状態に戻るために必要なステップ数の最大公約数を周期と呼び、全ての状態での周期が1であるようなマルコフ連鎖は非周期性を持つと言います。

$P=\left( \begin{array}{ccc} 0.5 & 0.5 \\ 0.8 & 0.2 \\ \end{array} \right)$

例えばこの行列の例だと
状態1から状態1へはステップ数1でも2でも3でも....戻ることが出来ます。つまり、最大公約数は1です。
状態2も同様で最大公約数が1なので非周期です。

また

$P=\left( \begin{array}{ccc} 0 & 0.5 \\ 0.8 & 0.2 \\ \end{array} \right)$

では、状態1から状態1へはステップ数2,3,4,....で戻ることが出来るので最大公約数は1,
状態2から状態2も最大公約数が1でこの行列も非周期です。

一方
$P=\left( \begin{array}{ccc} 0 & 0.5 \\ 0.8 & 0 \\ \end{array} \right)$

これは周期的です。
状態1から状態1へはステップ数2,4,6,...で戻ることが出来るので最大公約数は2になります。
また、状態2から状態2へも同様に最大公約数が2になります。
よってこれは周期的です。

そして、次のような話が成り立ちます。
既約かつ非周期なマルコフ連鎖は不変分布に収束する。

で、MCMCにおいては上のようなマルコフ連鎖を構成する必要があるわけですが、細かい話はさておいて重要かつ便利な条件として詳細つり合い条件というものがあります。

$Π(x,・),Π(y,・)$ が不変分布になるようなマルコフ連鎖を作るにあたって、詳細つり合い条件さえ満たしていれば作ることが出来るという条件です。で、その条件はどうなるかというと次のようなものになります。

$Π(x,・)p(xからyへいく)=Π(y,・)p(yからxへいく)$

今回は状態xと状態yしかない、つまり2状態しかない状況を考えているのでこれだけですが、この条件が全ての状態で成り立つ必要があります。

以上でマルコフ連鎖の話終了です。詳細つり合い条件から、結局どうMCMCをつくってくかというと、サンプルをとりたい分布 $Π$ を用意してやって、適当な確率分布 $p$ を持ってきて詳細つり合い条件を満たすようマルコフ連鎖を構成してやればよいということになります。

しかし $p$ が何でもよいかというとそういうわけでもなくて、これの選び方によって効率性や収束スピードが変わってきます。よって、効率的なアルゴリズムを構成するためには、適切な分布選択をしなければいけないわけです。

次回からその方法について書いていきます。