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

[] [] []


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

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

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

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

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

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

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

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

であり、その母関数は(f0=0と定義して)

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

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

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

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

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

であることに注意すると

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

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

◇◇

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

ここで2項係数の2和は

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

だから

らに2項係数の漸近形(→補足-2項分布の正規分布による近似

を使うと

したがって

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

◇◇◇

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

少し書き変えると

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

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

を使って上限を抑えると

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

これと

を使うとu2nの上限の漸近形は

したがって

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

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

次元

いつかは原点に

戻って来る確率

1

1

2

1

3

0.34

4

0.19

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

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

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

n

Σ(m=1..n) u2

0

1

1

1.166

2

1.236

3

1.276

4

1.303

10

1.374

100

1.470

1000

1.502

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


[] [] []