IX-th stone: Mixing Markov Chains(3)

前回couplingを使ったmixing time を算出した。今回はn-cube上のランダムウォークによって。2^n個のサイズを持つ空間がで許容誤差εを用いてO(n ln(nε^(-1)) ) 時間でサイズの見積もりが可能なことを示す（randomized アルゴリズムにすると、誤差がありながらもいかに時間が減るのかが実感できるよい例になっているだろう)

まずn-Cubeの定義をしよう
Definition: n-Cube Cn=(V,E) (undirected)
V={0...2^n-1},E={(a,b)| aとbを二進表現したときのHamming distanceが1}

再帰的に表現することもできて、 CnはCn-1 を２つ用意してそれぞれのCn-1の同じラベルを持つ頂点どうしをつなぐことで得られる。C0は頂点のみからなるグラフ。

さて、Cn上のMarkov Chain　MCc を考えよう。それは以下のとおり

MCc: random walk on Cn
starting vertex X0=0 repeat:
1.pick (i,b)∈　{1...n}×{0,1}
2.Xt+1 をXtのi-th bit をb に変更したものとする

こうすると任意の頂点間X,Yの遷移確率Pは

P(X,Y)=
1/2n if Hamming(X,Y)=1
1/2 if X=Y
0 otherwise

ここでMCcはirreducibleであることは自明。そしてもともとCnにはないselfloopも状態遷移に加わっているのでaperiodic.すなわちergodicである。しかもsymmetricである。よってこのMCcはuniform distributionに収束する。あとはMixing　Timeがどれくらいかである。それをcouplingを使って算出してみよう。

その前に、算出のために必要な面白い問題をひとつ。

coupon collecting problem:
n種類のクーポン券が無限にあります。クーポン券は毎回どの種類かはランダムに選ばれます。全種類集めるためには何回クーポン券をもらわないといけないでしょうか？
略解）　k種類集まった時点より後では、新しいクーポンをもらえる確率は毎回 1-k/n である。また、確率pの事象が起こるまでの回数の期待値は1/pであるから、答えは
Answer= sum(k=0,n-1) n/(n-k) = n(1/1+1/2+1/3+...+1/n) ≦n log n+n
よって回数の期待値はO(n log n)であることが分かる

この問題を使ってMCc上のcoupling時間を見積もることができる。
次回、実際にこのCoupling Timeを見積もってみる。