【ランダムウォーク】再帰時間の確率分布

等しい確率$1 / 2$で$\pm 1$だけ移動するランダムウォーク$x_{n} \, (n = 0, 1, 2, \dots)$を考える．ここで，$n$はステップを表し，$x_{0} = 0$とする．このような1次元ランダムウォークには再帰性があることが知られており，十分に長い時間（ステップ）を経ると必ず出発点に戻ってくる．この再帰時間の確率分布を求めるというのがここでの目的である．

$N = 2M$ステップで初めて$x = 0$に戻る確率

このランダムウォークが$n = N$で初めて$x_{N} = 0$に戻ってくるとする．これは$N$が偶数の場合に限られるから，$N = 2M$と置くと，そのような経路の総数$c_{2M}$は，

\[ c_{2M} = \frac{2}{2M – 1} {_{2M – 1}}C_{M} = \frac{1}{2M – 1} \frac{(2M)!}{(M!)^{2}} . \]

と求めることができる．したがって，$2M$ステップ後に初めて$x_{2M} = 0$に戻る確率$p_{2M}$は，これを$2M$ステップの経路の総数$2^{2M}$で割って，

\[ p_{2M} = \frac{1}{2^{2M}(2M – 1)} \frac{(2M)!}{(M!)^{2}} \ , \]

と求まる．

再帰時間の確率分布

さて，我々が知りたいのは「$N$ステップ経過後に初めて$x = 0$に戻ってくる確率」ではなく，「ランダムウォークが$x = 0$に戻ってきたとき，その経過時間（ステップ）$N$がどのような確率分布に従うか」である．

前者は$N$が与えられている（定数である）が，我々が知りたいのは，$N$の分布そのものである．前者の確率の分母は$N$ステップの経路の総数，つまり$2^{N}$であるのに対して，後者の分母は「いずれ$x = 0$に戻ってくるような経路の総数」，つまり「無限大」である．

したがって，一見して前節で求めた確率$p_{2M}$と，我々が知りたい$N \, (= 2M)$の確率分布とは直接の関係が無いように思える．しかし，「1次元ランダムウォークの再帰性」に着目すれば，$p_{2M}$を$N \, (= 2M)$の確率分布とみなせることがわかる．

くどいようであるが補っておくと，前者は$p_{2M}$の$2M$を定数とみなし，後者は確率変数とみなすという，視点の違いがある．

1次元ランダムウォークには再帰性があるため，全ての経路は十分な時間（ステップ）が経過すれば必ず出発点に戻ってくる．そして，そのような経路は「2ステップで初めて出発点に戻る経路」，「4ステップで初めて出発点に戻る経路」，「6ステップ…」，…と，排他的に分類できる．ここで，「2ステップで初めて出発点に戻る経路」は，2ステップ目で終わるのではなく，3ステップ目以降も無限に続いていることに注意．また，「$2M$ステップで初めて出発点に戻る経路」の総数は$M$によらず等しい．「等しい」と言っても経路の数は無限大なので，この点が気になる人は，どこか大きな$N_{\text{max}} = 2M_{\text{max}}$までで止めて議論をしておき，最後に無限大の極限をとればよい．

したがって，「全ての経路の数」に対する「$n = 2M$で初めて$x = 0$に戻る経路（$n = 2M$以降も続く）」の割合は，「$n = 2M$までの経路の総数$2^{2M}$」に対する「$n = 2M$で初めて$x = 0$に戻る経路（$n = 2M$で終了）$c_{2M}$」の割合と等しくなり，$2M$の確率分布は上で求めた$p_{2M}$そのものとなる．

また，再帰性から$p_{2M}$は$\displaystyle{\sum_{M = 1}^{\infty}} p_{2M} = 1$という規格化条件を満たし， 確かに確率としての性質を満たすこともわかる．

再帰時間の確率分布（別の導出）

上の説明ですっきりしない人のために，別の説明を試みよう．（自分もそのひとりである）

先に述べたように，求めたい確率分布の分母（いつか$x = 0$に戻ってくるようなランダムウォークの総数）は無限大なので，経路を数え上げる方法よりも，確率の「比」に着目したほうがわかりやすい．

$x = 2M$で初めて$x = 0$に戻る確率を$p_{2M}$と書くことにする．この時点では先ほど求めた確率$p_{2M}$と異なると想定しているので，別の文字（例えば$q_{2M}$など）で書くべきかもしれないが，混乱の心配はないので同じ文字を使う．

$p_{2M}$と$x = 2(M + 1)$で初めて$x = 0$に戻る確率$p_{2(M + 1)}$との比は，

\[ \frac{p_{2(M + 1)}}{p_{2M}} = \frac{c_{2(M + 1)}}{4c_{2M}} = \frac{M – 1 / 2}{M + 1} \ , \]

となる．ここで，中央の式で分母が$c_{2M}$ではなく$4c_{2M}$となっていることに注意しよう．$p_{2(M + 1)} \propto c_{2(M + 1)}$と比較する必要があるのは，$n = 2M$で初めて$x = 0$となってから$n = 2(M + 1)$の任意の点まで進む経路の総数$4c_{2M}$だからである．この漸化式を解くと，

\[ p_{2M} = \frac{M – 3 / 2}{M} p_{2(M – 1)} = \dots = \frac{(2M – 3)!}{2^{2M – 3}M!(M – 2)!} p_{2} = \frac{1}{2^{2M – 1}(2M – 1)} \frac{(2M)!}{(M!)^{2}} p_{2} \ , \]

が得られる．ここで，$p_{2} = 1 / 2$であれば，先ほどの表式と一致する．

この節での$p_{2M}$は，「$N = 2M$ステップで初めて$x = 0$に戻る確率」ではなく，$2M$は確率変数であることに注意しよう．したがって，$p_{2} = 1 / 2$は自明ではない．

実は，$p_{2} = 1 / 2$はランダムウォークの再帰性からの帰結である．全ての経路のうち半数は$x_{2} = 0$を通り，残りの半数は通らない．ここで，再帰性から「全ての経路の数」と「いずれ$x = 0$に戻る経路の総数」が（どちらも無限大ではあるが）等しいので，「いずれ$x = 0$に戻る経路」のうち，ちょうど半数が$x_{2} = 0$を通る．したがって$p_{2} = 1 / 2$であると結論できる．もし$x = 0$に戻ってこないような経路があるなら，「いずれ$x = 0$に戻る経路の総数」は「全ての経路の数」よりも少なく，確率の分母が小さくなるために，$p_{2}$は相対的に$1 / 2$よりも大きくなるはずである．もっとも，このような場合に$N = 2M$の確率分布などを考える意味があるかどうかは不明であるが．

以上から，再帰時間の確率分布は，

\[ p_{2M} = \frac{1}{2^{2M}(2M – 1)} \frac{(2M)!}{(M!)^{2}} \ , \]

と求まり，これは確かに先ほどの表式と一致している．

$N = 2M$が大きい時の振舞い

$p_{2M}$の表式が得られたので，任意の$2M$に対して具体的に確率を計算できるようになった．$p_{2M}$は$M$の減少関数であるが，この減り具合を調べておくことは有用である．

そこで，$N = 2M$が大きい時の$p_{N} = p_{2M}$の振舞いを調べてみよう．これには，$n \gg 1$の時に適用できる階乗$n!$に対するStirlingの近似

\[ n! \sim \sqrt{2\pi n} \left( \frac{n}{e} \right)^{n} \ , \]

を用いると良い．この近似を用いて$p_{2M}$を評価すると，

\[ p_{2M} \sim \frac{1}{(2M – 1)\sqrt{\pi M}} \simeq \frac{M^{-3 / 2}}{2\sqrt{\pi}} \ , \]

となる．補正項は$\mathcal{O}(M^{-5 / 2})$である． ここで，$2M$が大きいとき，もはや$N$が偶数か奇数かはあまり関係がないので，$M = N / 2$を戻して

\[ p_{N} \sim \sqrt{\frac{2}{\pi}} N^{-3 / 2} \ , \]

と書いておこう．

以上から，$N$が大きいとき，確率$p_{N}$はべき分布に従うことがわかる．

再帰時間の確率分布の数値実験

理論的な計算がやや込み入ったので，上で求めた表式が確かに正しいことを，数値実験を行うことで示そう．

[TBC]