VI-th stone: Mixing on Markov Chains

--What I've learned--
このページにリンクがあるLance Fortnow氏のMy Computational Complexity WeblogにFOCS2003でのDana Randall氏のMarkov chainでのMixingに関するTutorialの記事がのっていた。組み合わせ理論に興味があるのに伴って、いやべつに伴っていないかもしれないが、特定の条件をみたす組み合わせが何通り存在するかという数え上げにも興味がある。その数え上げの方法のひとつしてMarkov Chain Monte Carloというものがある。それは対象とする組み合わせ全体の集合を考えてその上にランダムウォークを定義する。するとその集合のサイズがある程度の誤差のもとでわかるというものらしい。実際誤差を縮めようとすればするだけ計算時間がかかる。しかしそれはすべてその誤差の逆数の多項式で抑えられる。

そして今日は以前図書館に頼んであったarc coloring is NP-Completeの証明ののっている論文もとどいた。これはまた次に読むことにしよう。Complexity WeblogにのっていたEli Upfal氏のPerformance Analysis of Dynamic Network Processesも興味深い。また時間をとって読むことにするか。もしかしたら読まないかもしれないが。

Mixing on Markov Chains
Markov Chain Monte Carloとは非常に大きく、そして複雑な集合を計算機的に解析するための一般的なフレームワークである。メインのアイデアはある特定の性質(ergodicかつsymmetric)を満たすマルコフ課程上のランダムウォークを定義してそれを何ステップかシミュレートするとそれがuniform distributionに収束する。すなわち何ステップが後にはそのランダムウォークで各状態にいる確率がすべて等しく1/（空間のサイズ）となるものである。

ここからは例をつかって説明していこう。あるグラフG=(V,E),|V|=nの独立点集合全体の集合を考えよう。Ω={all independent set of G},and connect I and I' iff |I XOR I'|=1として状態空間を構成する。そして次にこの有向グラフH上のランダムウォークPを構成する。それは次のとおり

Transition P:
Random walk on H starting at x:
1.Pick a neighbor y.
2.Move to y with prob. P(x,y)=1/Δ
3.With all remaining prob. stay at x.

ここでMarkov Chain MCがergodic(エルゴード的)であることの定義をしよう。

Definition: Markov Chain MC is ergodic if it is:
1. irreducible: for all x,y∈Ω, there exists t s.t. Pt(x,y)>0; Hがconnectedを示している。どこからスタートしてもどの状態へもたどり着けるということ。
2. aperiodic: for all (x,y)∈E(H),g.c.d{t:Pt(x,y)>0}=1;xからyへ遷移する確率が０でないステップの最大公約数は1。すなわちxからyへ遷移することが周期的には起こらないということ。

そしてfiniteかつergodicなMarkov Chainに対して以下の２つの定理が成り立つ。

Thm1. Any finite and ergodic MC converges to a unique stationary distribution.
Thm2. The stationary distribution Pi satisfies: Pi(x)P(x,y)=Pi(y)P(y,x)

先に作ったランダムウォークはsymmetricなのでPi(x)=P(y)が成り立つ。よってPiはuniformになる。あとはどうやって収束の早いランダムウォークを作り、それがどのくらいのステップで収束（stationary distributionに近づく)かを調べなくてはいけない。

これ以降は明日につづく。