ランダムウォークでいつかは原点x=0に戻って来る確率

[←]　[↑]　[→]

・1次元のランダムウォークで、いつかは原点x=0に戻って来る確率は100%

・2次元のランダムウォークで、いつかは原点x=0に戻って来る確率は100%

・3次元のランダムウォークで、いつかは原点x=0に戻って来る確率は34%

一般に、d次元のランダムウォーク

「粒子は原点x=0から出発して、時刻t=n⊿t(n=1,2,...)ごとに1/2dの確率でd軸のうち1つの軸上を+⊿xか-⊿xだけ動く」

を考えると、次元が増えると原点に戻って来る確率(再帰確率)は小さくなることが予想される。実際に、1,2次元までは必ず戻って来るのに、3次元以上では戻るとはかぎらないそうで、ある次元から様相ががらりと変わるのはおもしろい。

以下の計算は「確率論とその応用(第2版)」(フェラー)の第XIV章によっている。

◇

1次元のランダムウォークでt=2nで初めて原点x=0に戻って来る確率は(→ランダムウォークでt=2nに初めて原点x=0に戻る確率)

であり、その母関数は（f₀=0と定義して）

であった。t=∞までに原点に戻って来る確率はf_2nの和だからF(1)に等しく

と100%であることがわかる。

このように、t=∞までに原点に戻って来る確率は、もしf_2nがわからなくてもF(1)が計算できればよい。

しかもF(z)は、ちょうどt=2nで原点x=0にいる確率u_2nの母関数U(z)と

という関係があったからU(1)が計算できればよいことになる。ここでu₀=1でu_2n>0だから

であることに注意すると

U(1)が発散するならばF(1)=1となるので、いつかは原点に戻って来る

U(1)が収束するならばF(1)<1となるので、いつまでたっても原点x=0に戻ってこないことがありうる

◇◇

2次元のランダムウォークで、ちょうどt=2nで原点x=0にいる確率u_2nは、2n回中、x軸上を正負方向に同数(k歩ずつ)、y軸上を正負方向に同数(n-k 歩ずつ)、進んだときだから、

ここで2項係数の2乗和は

（∵(1+z)ⁿ(1+z)ⁿ=(1+z)²ⁿの両辺を2項定理で展開してzⁿの係数を比較する）

だから

を使うと

したがって

は調和級数Σ1/nと同程度になるから発散する。すなわち2次元のランダムウォークは、いつかは原点に戻って来る。

◇◇◇

3次元のランダムウォークで、ちょうどt=2nで原点x=0にいる確率u_2nは、2n回中、x軸上を正負方向に同数(j歩ずつ)、y軸上を正負方向に同数(k歩ずつ)、z軸上を正負方向に同数(n-j-k 歩ずつ)、進んだときだから、

少し書き変えると

と3項係数の2乗和が現れる。2次元のときは2項係数の2乗和だったので計算できたが、3項係数の2乗和は閉じた式で書けない。

そこで、3項係数の最大値M_n

を使って上限を抑えると

最大値M_nは、3項係数の真ん中j=k=n/3付近の値だから、スターリングの公式を使って漸近形を求めると、

これと

を使うと、u_2nの上限の漸近形は

したがって

はΣ1/n^1.5と同程度なので収束する。すなわち、3次元のランダムウォークはいつまでたっても原点に戻って来こないことがある。

原点に戻ってくる確率を求めるにはU(1)を計算すればよいが、それには高級な数学が必要になるらしく、Pólya's Random Walk Constantsというサイトによると34%になるらしい。

解析的に計算するのは高級すぎるので、ためしに数値計算してみた。

この式は分母と分子が大きすぎてすぐにオーバーフロウしてしまうので、3項係数を2項係数の積に書きなおして、j,kの2重和をj+k=mとkの和に分けると、

と1つの和に表せた。十進BASICで15桁の精度で計算するとこの式ではn=100ぐらいまでしか計算できなかったので、1000桁の精度でn=1000まで計算してみた。

この値を使うと、原点に戻って来る確率は33%とかなり正確な値になった。

[←]　[↑]　[→]