VIII-th stone: Mixing Markov Chains (2)

--What I've learned--
前回、finiteかつergodicなMarkov Chainは必ずstationary distributionに収束し、
そのChainがSymmetricな場合はuniformになることがわかった。

ではより複雑な定常確率分布(stationary distribution)に収束するようなランダムウォークはどのように構成すればいいのだろうか？そしてそれはどれくらいの長さをシミュレートしたらstationary distributionに収束するのだろうか？
これにはMetroPolis algorithmというものがある、このアルゴリズムは任意のstationary distributionに収束させることができるランダムウォーク構成法である。これは２０００年のComputing in Science and Engineering のTop10アルゴリズムにランクされているそうだ

The MetroPolis algorithm
これは非常にシンプルかつロバストなアルゴリズムで、任意の希望するstationary distriution π に収束させることができるランダムウォークを構成する。

The MetroPolis Algorithm
Starting at x, repeat;
1. Pick a neighbor y uniformly with probability 1/2Δ(max degree)
2. Move to y with probability min(1, π(y)/π(x))
3. With all remaining probability stay at x

このTransitionと、πは前回のThm2.を満たし、そしてuniqueなものにしか収束しないことがわかっているので、このπはstationary distributionとなる。

前回のindependent set すべての集合Ωに対しては任意の正定数λ＞0によって、
π(x)=λ^|x|/Z (Z=sum(λ^|x|))
とする。すると、(x,y)という辺がHにあるときπ(y)/π(x)=λとなる。

あとは、このランダムウォークがどのくらい速く収束するかがわかるといい。

そこでMixing Timeという概念を導入する。所望のstationary distribution πとシミュレーション途中のdistribution Ptに対してそのtotal variation distanceを定義する

Definition: The total variation is
||Pt,π||=max_{x}( 0.5sum_{y}(|Pt(x,y)-π(x)|))

この距離によってMixing Time τは

Definition: Given ε>0, the mixing time　τ(ε) is
τ(ε)=min{t : ||Pt',π||＜ε, forall t'≧t}

そして、あるMarkov Chain　MCについて、τ(ε)=Poly(n,log ε^{-1})となるとき、MC is rapidly mixingという。

また一般的なτのバウンドとしてTransition Matrix の固有値(eigen value)を用いたものがある。

Thm3. let q=min(π(x)), Define Gap(P)=1-|λ1|(λ1 is max eigenvalue), then
・τ(e)≦1/Gap(P) log(1/qe)
・τ(e)≧|λ1|/2Gap(P) log(1/2e)


もうひとつ収束時間をboundするための方法としてCouplingというものがある。

Coupling
coupling はΩ×Ω上のMarkov Chainで以下の２つの性質を満たす確率過程(Xt,Yt)とする1.Xt,YtはそれぞれもともとのM(Ω上のMarkov Chain)のコピーである。初期状態はそれぞれx0,y0
2.If Xt=Yt , then Xt+1=Yt+1

これは初期状態x0,y0から独立にスタートしたランダムウォークが時刻t以降同じパスを通るというものである。次に任意の初期状態の対x0,y0に対してTxy=min{t : Xt=Yt|X0=x0,Y0=y0}としてcoupling Timeを

Definition: coupling time T of M is
T=max_(x0,y0)(E[Txy])

とする。このcoupling time Tと 許容誤差ε(>0)を用いて収束時間τは以下で抑えられる

Thm4. τ(ε)≦ceil(T e ln(ε^{-1}))

このcouplingについても、E[Txy]をどうすればよいのか？という疑問がのこる。
これを解決したのがpath couplingという方法である。これはまた次回。