ランダムウォークの基礎

等確率$1 / 2$で$\pm 1$だけ移動するランダムウォーク$x_{n} \, (n = 0, 1, 2, \dots)$を考える．ここで，$n$はステップ（時間）を表し，$x_{0} = 0$としておく．

以下，ランダムウォークについての基礎的な事項を，順を追ってまとめる．

$x_{N}$の平均$\mu_{N}$と分散$\sigma_{N}^{2}$

$N$ステップ後の位置$x_{N}$の平均値は，対称性から明らかに

\[ \mu_{N} \equiv \braket{x_{N}} = 0 \ , \]

である．

また，一回のランダムウォーク後の位置$x_{1}$の二乗平均$\braket{x_{1}^{2}}$は，

\[ \braket{x_{1}^{2}} = 1^{2} \cdot \frac{1}{2} + (-1)^{2} \cdot \frac{1}{2} = 1 \ , \]

であるから，$x_{1}$の分散$\sigma_{1}^{2}$は，$\sigma_{1}^{2} = 1$となる．ランダムウォークの各ステップは独立であるから，$N$ステップ後の位置$x_{N}$の分散$\sigma_{N}^{2}$は，

\[ \sigma_{N}^{2} = N\sigma_{1}^{2} = N \ , \]

となる．

$N$ステップ後に初めて$x_{N} = X$となる確率

$N$ステップ後に初めて$x_{N} = X$となる確率を求めよう．

問題の対称性から，$X > 0$と仮定して一般性を失わないので，以降これを仮定する．$N$ステップ後に初めて$x_{N} = X > 0$となるということは，数列$\{ x_{n} \}$の最大値が$x_{N} = X$であるということである．ここで，数列$\{ x_{n} \}$の隣接二項間の差を$dx_{n} \equiv x_{n} – x_{n – 1} \, (n = 1, \dots, N)$と書き，$dy_{n} \equiv dx_{N+1-n} \, (n = 1, \dots, N)$を定義する．これを用いて，新しい数列$\{ y_{n} \}$を

\[ y_{n} = \begin{cases} 0 & (n = 0) \\ \sum_{m = 1}^{n}dy_{m} & (n = 1, \dots, N) \end{cases} \ , \]

で定義する．このように作った$\{ y_{n} \}$は，各項が必ず$0$以上（$y_{n} \ge 0 \, (n = 0, 1, \dots, N)$）となる．あるいは，より強く$y_{n} > 0 \, (n = 1, \dots, N)$と言っても良い．数列$\{ y_{n} \}$の作り方から明らかなように，数列$\{ x_{i} \}$と数列$\{ y_{n} \}$は一対一に対応する．

数列$\{ y_{n} \}$は$y_{1} = 1$を必ず通り，以降$y_{n} > 0$であり続ける．このような経路の個数は，$y_{1} = 1$かつ$y_{N} = X$を満たす全ての可能な経路の個数から，そのような経路のうち，ある$n$で$y_{n} \le 0$となるものの個数を引いたものとして求めることができる．後者は，反射原理により，$y_{1} = -1$かつ$y_{N} = X$である全ての可能な経路の個数と等しい．したがって，$\{ y_{n} \}$の個数は，

\[ {_{N}}C_{(N-X)/2-1} – {_{N}}C_{(N+X)/2} = \frac{N!}{\{ (N + X) / 2 \}! \{ (N – X) / 2 \}!} = {_{N}}C_{(N+X)/2} \ , \]

と求まる．これは${x_{n}}$の個数と等しい．$N$ステップの全てのランダムウォークの個数は$2^{N}$個であるから，求める確率は

\[ P(X, N) = \frac{1}{2^{N}} \cdot {_{N}}C_{(N+X)/2} = \frac{1}{2^{N}} \cdot \frac{N!}{{(N + X) / 2}! {(N – X) / 2}!} \ , \]

となる．これは，値$X$を与えたとき，$N$ステップ後に初めて$x_{N} = X$となるとしたときの，$N$の確率分布に他ならない．

$P(X, N)$は$N \sim X^{2}$付近で最大値を取る

上の確率が，$N \sim X^{2}$付近で最大値を取ることを示そう．

$P(X, N)$と$P(X, N + 2)$の大小を比較すればよい．これらの比をとると，

\[ \frac{P(X, N)}{P(X, N + 2)} – 1 = \frac{4(\frac{N + X}{2} + 1)(\frac{N – X}{2} + 1)}{(N + 2)(N + 1)} – 1 = \frac{N^{2} + 4N + 4 – X^{2}}{(N + 2)(N + 1)} – 1 = \frac{N + 2 – X^{2}}{(N + 2)(N + 1)} \ . \]

これが$0$となる$N = N_{\text{max}}$は，

\[ N_{\text{max}} + 2 – X^{2} = 0 \ , \quad \therefore N_{\text{max}} = X^{2} – 2 \ . \]

したがって，$P(X, N)$は$N_{\text{max}} = X^{2} – 2$で最大値を取る．

$X$が大きいときには，$N_{\text{max}} \sim X^{2}$となる．これは，$N$ステップのランダムウォークの分散が$\sqrt{N}$となることから理解できる．

再帰確率

$n = N$で$x = 0$に戻る確率を求めよう．

$n = N$で$x = 0$に戻るとする．そのような経路の総数は${_{N}}C_{N/2}$個ある．$N$ステップのランダムウォークの総数は$2^{N}$個なので，求める確率は，

\[ P(x_{N} = 0) = \frac{1}{2^{N}} \cdot {_{N}}C_{N/2} = \frac{1}{2^{N}} \cdot \frac{N!}{{(N / 2)!}^{2}} \ , \]

となる．これは$N$に対して単調減少する．もちろん，$N$は偶数である．

初回再帰確率

$n = N$で初めて$x = 0$に戻る確率を求めよう．

$n \not= 1, N$のとき$x_{n} \not= 0$なので，$n \not= 1, N$で常に$x_{n} > 0$または$x_{n} < 0$と仮定して良い．対称性から両者の確率は等しいので，$n \not= 1, N$で常に$x_{n} > 0$の場合を考える．仮定から，経路は$x_{0} = 0$，$x_{N-1} = 1$を通る．このような経路の総数は，反射原理から

\[ \frac{1}{N – 1} \cdot {_{N – 1}}C_{N / 2} \ , \]

個ある．$x_{n} < 0 \, (n = 1, \dots, N – 1)$の場合もこれと同数あるので，求める確率は，これに$2$をかけて$2^{N}$で割って，

\[ \frac{2}{2^{N}} \cdot \frac{1}{N – 1} \cdot {_{N – 1}}C_{N / 2} = \frac{1}{2^{N}(N – 1)} \cdot \frac{N!}{\{ (N / 2)! \}^{2}} \ , \]

となる．これも$N$に対して単調減少するが，$P(x_{N} = 0)$よりも急激に減衰する．