酔っ払いはもとの位置に戻ってこれるか? (ランダムウォークの再帰性)
この問題が何と1,2次元と3次元以上では違ってくるという話を聞きました.1,2次元では必ず(確率1で)帰ってくるが,3次元以上だと必ずしも帰ってくるとは限らない(帰ってくる確率 < 1)となるとのこと.人は空を飛べないので,酔っ払っても必ず帰ってこれるのかーと感心したのであります.しかしなぜ2次元と3次元の間にそのような差が出てくるのか,不思議に思った次第呟いたところ,先日友人が資料をくれて証明を説明してくれました!感謝
まぁその場ではイメージをつかんだだけで,証明まで追えなかったのですが,ようやく少し証明プロセスを飲みこめた気がするので,折角の機会に簡単に説明してみようかと思います!
- 1次元(対称)ランダムウォーク
定義:位置0から出発,確率1/2で+1,確率1/2で-1に移動する運動
1次元ランダムウォークが確率1で位置0に「帰ってくる」ことを,数学的には「再帰的」というらしい.
さて,このこのランダムウォークが位置0に戻る確率を調べよう.
奇数回の試行では帰ってこれないので,偶数回の試行,2n回のみ考える.
2nの試行の後,位置0に戻っている確率(u_2nとしよう)は,2n回の試行列からn個のプラスを選ぶプロセスだから,
じゃぁランダムウォークが位置0に戻る確率は か!と思いきや,これでは重複が(n回目に戻ってくるものの中に,m(
- 2次元ランダムウォーク
さ,2次元行きますか.打つの疲れてきたぜ笑
2次元では,+x,-x,+y,-yの4つ自由度があります.ゼロに戻るには,2n回から2k回のx方向試行を選び,2k回中k回の+x,2(n-k)回中(n-k)回のプラス+yを選んであげて,kが0からnまで足し合わせてあげるといいですね.ということで,
さてここでテクニックですよ!
ここでなんか展開するとこんな変形できる(知らないとできないよね・・・)
またスターリンの公式を使って
てことで,uの分母が1乗だから,Uが発散するのだよ!
- 3次元ランダムウォーク
さ,3次元行きますが,疲れたし証明もっと難しいからまいてくゎ
3項定理を使って場合分けしたりして頑張ると,
であることが示せるのです.ので,まぁ最初に類推したように,nの3/2乗になるのでU_nが有限に収束してしまい,故に0に戻る確率は1より小さくなる,というわけでした!
- 戻ってくるまでの時間の期待値
1,2次元では確率1で戻ってくると言っても,上記証明からわかるように,「無限の試行をすれば必ずいつかは」帰ってくる確率が1なのであります.すると,じゃぁ一体どのくらいの時間で帰ってくるのが期待できるのか?という期待値が気になるのでありますが,何と1次元でも期待値は無限大です.
よって,やっぱり酔っ払ってランダムに歩いた場合に帰ってこれることを期待するのはよしたほうがよさそうです.
- 対称じゃない場合
そもそも,この話の前提はプラスとマイナスに進む確率が1/2でしたが,よくよく考えると千鳥足は左右に進む確率が対称ではないような気もします.ランダムに歩ける位酔っているというのは相当です.証明は省きますがプラスに進む確率がp,マイナスがqとすると,1次元ランダムウォークがゼロに戻る確率は 1-|p-q| です.つまり,左右対称でなければそもそも1次元だろうと,原点に戻る確率は1ではありません.まぁ,良く考えれば当然ですが.
ゆえに,やっぱり酔っ払ってランダムに歩いた場合に帰ってこれることを期待するのはよしたほうがよさそうです.
以上,私の自己満足!!!!
脚注)
- 母関数を用いた証明テク!
まずuとfについて考える.u_nというのは,n回目にゼロにいる確率であるが,それを排反な事象に分割すると,k回目に初めてゼロに戻り(f_k),後n-k回で(どんな経路でもいいけど)ゼロに戻ってくる(u_{n-k}) とできることが分かる.よって,
ただし,u_0 = 1, f_0 = 0 とする.0回目にゼロである確率は1だが,初めてではないから,という感じか.まぁその後のための準備である.
さて,ここで,母関数というのは以下のように,数列u_n に対して以下のようにsのn乗をかけた数の和のこと
知りたいf_nに関しても母関数が以下のように定義される
ここで左辺は U(s)-u_0 s_0 = U(s) -1 .よって,
U(s) = F(s) U(s) + 1
F(s) = 1 - U(s)^{-1}
ここで,知りたかった はs=1の時に相当するため,が1になるか否かは F(1)が1になるか否かに相当する.更に上式より,F(s)→1に収束 が U(s)→無限大発散 と同値である.以上証明終わり.