酔っ払いが街灯の下に立っています。一歩ごとに右に行くか左に行くかをコイン投げで決めて歩きます。「十分な時間が経ったとき、酔っ払いは必ず元の場所に戻ってくるか？」— この問いに答えるのがランダムウォーク（random walk, 酔歩）の理論です。
ランダムウォークは確率論の最も基本的なモデルの一つであり、拡散現象、株価変動、高分子の形状、ギャンブラーの運命など、驚くほど多くの現象を統一的に記述します。離散的な空間と時間の上で定義されるにもかかわらず、その連続極限としてブラウン運動が得られるため、解析学・物理学・金融工学の橋渡しとしても中心的な役割を果たしています。
ランダムウォークを理解すると、以下のような応用が可能です。
- 金融工学: 株価モデルの基礎であり、ブラウン運動・幾何ブラウン運動の離散版です。ブラック・ショールズモデルの基盤となる確率過程を理解するための出発点です
- 物理学: 拡散方程式の離散的な対応物であり、分子のブラウン運動やポリマー鎖の形状をモデル化します。アインシュタインの1905年の拡散理論もこの枠組みで理解できます
- コンピュータ科学: ランダム化アルゴリズム、マルコフ連鎖モンテカルロ（MCMC）の基盤です。グラフ上のランダムウォークはPageRankアルゴリズムの核心でもあります
- 生態学: 動物の移動パターン（レヴィフライトを含む）のモデル化に使われます
本記事の内容
- 1次元単純ランダムウォークの定義と基本性質
- $S_n$ の分布と原点帰還確率の漸近形
- 再帰性（ポリアの定理）の証明
- ギャンブラーの破産問題の完全な解法
- 初到達時刻と反射原理
- アークサイン法則とその直感に反する帰結
- 中心極限定理とブラウン運動への収束（ドンスカーの不変原理）
- 多次元ランダムウォークと再帰性の次元依存性
- Pythonによるシミュレーションと可視化
前提知識
この記事を読む前に、以下の記事を読んでおくと理解が深まります。
- 大数の法則と中心極限定理 — 漸近定理の基礎
- 正規分布 — ランダムウォークの漸近分布
- マルコフ連鎖の理論 — 離散時間マルコフ連鎖
1次元単純ランダムウォーク
定義
1次元単純ランダムウォーク（simple random walk）は、各ステップで $+1$ または $-1$ に動く離散時間の確率過程です。数直線上に立つ人が、コインを投げて表なら右に1歩、裏なら左に1歩進む — このシンプルなルールから豊かな数学が生まれます。
形式的には、独立同一分布（i.i.d.）の確率変数列 $\{X_i\}_{i=1}^{\infty}$ を用いて、
$$ S_n = X_1 + X_2 + \cdots + X_n, \quad S_0 = 0 $$
と定義します。ここで各 $X_i$ は $P(X_i = +1) = p$, $P(X_i = -1) = 1 – p = q$ に従います。$p = q = 1/2$ のとき対称（symmetric）ランダムウォーク、$p \neq q$ のとき非対称（asymmetric）ランダムウォークと呼びます。
ランダムウォークはマルコフ連鎖の一種です。$S_n$ の将来の値は現在の位置 $S_n$ のみに依存し、過去の経路 $S_0, S_1, \dots, S_{n-1}$ には依存しません。これは各ステップ $X_i$ が独立であることから直ちにわかります。状態空間は整数全体 $\mathbb{Z}$ であり、推移確率は
$$ P(S_{n+1} = j \mid S_n = i) = \begin{cases} p & (j = i + 1) \\ q & (j = i – 1) \\ 0 & (\text{otherwise}) \end{cases} $$
です。ランダムウォークのシンプルさと豊かさの両方は、この推移構造の単純さに由来しています。
期待値と分散
対称ランダムウォーク（$p = 1/2$）の場合、$E[X_i] = 0$, $\text{Var}(X_i) = 1$ なので、
$$ E[S_n] = n \cdot E[X_1] = 0 $$
$$ \text{Var}(S_n) = n \cdot \text{Var}(X_1) = n $$
つまり、$S_n$ の標準偏差は $\sqrt{n}$ のオーダーで増加します。位置の平均はゼロのまま動きませんが、ばらつき（不確実性）は $\sqrt{n}$ で広がります。
この $\sqrt{n}$ スケーリングは直感的には「ランダムな変動は距離の二乗根で増大する」ことを意味します。$n = 100$ ステップ後の位置は、平均0の周りに標準偏差 $\sqrt{100} = 10$ の範囲で分布します。$n = 10000$ ステップ後は標準偏差 $\sqrt{10000} = 100$ です。ステップ数を100倍にしても、典型的な変位は10倍にしかなりません。
対称ランダムウォークはマルチンゲールでもあります。$E[S_{n+1} \mid S_0, S_1, \dots, S_n] = S_n + E[X_{n+1}] = S_n$ が成り立つため、将来の期待位置は現在の位置と等しいです。このマルチンゲール性は、ギャンブラーの破産問題など多くの結果を導く上で本質的な役割を果たします。
$S_n$ の分布
$n$ ステップ後の位置 $S_n$ の正確な分布を求めましょう。$n$ 回のステップのうち $+1$ が $k$ 回、$-1$ が $n-k$ 回出たとすると、$S_n = k – (n-k) = 2k – n$ です。
$$ P(S_n = 2k – n) = \binom{n}{k} p^k q^{n-k}, \quad k = 0, 1, \dots, n $$
$S_n$ は $-n, -n+2, -n+4, \dots, n-2, n$ の値のみを取ります（パリティの制約）。$n$ が偶数なら $S_n$ は偶数のみ、$n$ が奇数なら $S_n$ は奇数のみを取ります。特に $S_n = 0$ が可能なのは $n$ が偶数のときだけです。
対称ランダムウォーク（$p = 1/2$）では、$2n$ ステップ後に原点にいる確率は
$$ P(S_{2n} = 0) = \binom{2n}{n} \left(\frac{1}{2}\right)^{2n} $$
これは $2n$ ステップのうちちょうど $n$ 回が $+1$ である確率です。スターリングの公式 $n! \approx \sqrt{2\pi n}(n/e)^n$ を適用しましょう。
$$ \binom{2n}{n} = \frac{(2n)!}{(n!)^2} \approx \frac{\sqrt{4\pi n}(2n/e)^{2n}}{2\pi n (n/e)^{2n}} = \frac{4^n}{\sqrt{\pi n}} $$
よって、
$$ P(S_{2n} = 0) \approx \frac{4^n}{\sqrt{\pi n}} \cdot \frac{1}{4^n} = \frac{1}{\sqrt{\pi n}} $$
この確率は $n$ とともに0に近づきますが、減衰は非常にゆっくりです（$1/\sqrt{n}$ のオーダー）。$n = 100$ でも $P(S_{200} = 0) \approx 1/\sqrt{100\pi} \approx 0.056$ とそれなりの確率で原点にいます。
非対称ランダムウォークのドリフト
$p \neq 1/2$ のとき、ランダムウォークにはドリフト（系統的な偏り）が生じます。各ステップの期待値は
$$ E[X_i] = p \cdot 1 + q \cdot (-1) = p – q = 2p – 1 $$
なので、
$$ E[S_n] = n(2p – 1) = n\mu $$
ここで $\mu = 2p – 1$ がドリフト率です。$p > 1/2$ ならば $\mu > 0$ で正の方向にドリフトし、$p < 1/2$ ならば $\mu < 0$ で負の方向にドリフトします。
分散は $\text{Var}(X_i) = E[X_i^2] – (E[X_i])^2 = 1 – (2p-1)^2 = 4pq$ なので、
$$ \text{Var}(S_n) = 4npq $$
$p$ が $1/2$ から離れるほど分散は小さくなります。極端な場合 $p = 1$（確定的に右に進む）では分散はゼロです。ドリフトが大きいとき、ランダムウォークの挙動はドリフトに支配され、ランダムな変動は相対的に小さくなります。$n$ が大きいとき、$S_n \approx n\mu$ を中心に標準偏差 $2\sqrt{npq}$ の幅で分布します。
非対称ランダムウォークのマルチンゲール性は失われますが、指数マルチンゲール $M_n = (q/p)^{S_n}$ がマルチンゲールになるという性質を持ちます。$E[M_{n+1} \mid S_n] = p(q/p)^{S_n+1} + q(q/p)^{S_n-1} = (q/p)^{S_n}[p(q/p) + q(p/q)] = (q/p)^{S_n} = M_n$ が成り立ちます。この指数マルチンゲールはギャンブラーの破産問題の解法に直接使えます。
ランダムウォークの基本的な性質が把握できたところで、最も魅力的な性質の一つである「再帰性」について詳しく見ていきましょう。
再帰性 — ポリアの定理
1次元: 必ず戻ってくる
対称1次元ランダムウォークは再帰的（recurrent）です。つまり、原点から出発したランダムウォークは、確率1で原点に戻ります。
$$ P(S_n = 0 \text{ for some } n \geq 1) = 1 $$
しかも、何度でも戻ります。原点への帰還回数の期待値は無限大です。直感的には、1次元では左と右の2方向しかないため、ランダムウォークは何度も原点を通過する機会が十分にあるのです。
再帰性の証明（1次元）
再帰性の証明は、母関数を用いた解析で行います。原点帰還確率を $u_{2n} = P(S_{2n} = 0)$ とします（奇数ステップでは原点に戻れないため偶数のみ考えます）。先ほど求めた漸近形は
$$ u_{2n} = \binom{2n}{n} \left(\frac{1}{2}\right)^{2n} \sim \frac{1}{\sqrt{\pi n}} $$
です。初帰還時刻の分布 $f_{2n} = P(\text{ステップ } 2n \text{ で初めて原点に戻る})$ を定義すると、全確率の公式から更新関係（renewal relation）
$$ u_{2n} = \sum_{k=1}^{n} f_{2k} \cdot u_{2n-2k} + \delta_{n,0} $$
が成り立ちます。この式の意味は、ステップ $2n$ で原点にいるためには、あるステップ $2k$ で初めて原点に戻り（確率 $f_{2k}$）、残りの $2(n-k)$ ステップで再び原点にいる（確率 $u_{2(n-k)}$）ということです。
母関数 $U(s) = \sum_{n=0}^{\infty} u_{2n} s^n$, $F(s) = \sum_{n=1}^{\infty} f_{2n} s^n$ を定義すると、畳み込み関係は積に変換され、
$$ U(s) = 1 + F(s) \cdot U(s) $$
よって $F(s) = 1 – 1/U(s)$ です。
$U(s)$ の具体的な形を求めましょう。$u_{2n} = \binom{2n}{n} 2^{-2n}$ を代入して、
$$ U(s) = \sum_{n=0}^{\infty} \binom{2n}{n} \left(\frac{s}{4}\right)^n $$
これは有名な二項級数の公式 $\sum_{n=0}^{\infty} \binom{2n}{n} z^n = (1 – 4z)^{-1/2}$ を $z = s/4$ で適用して、
$$ U(s) = \frac{1}{\sqrt{1 – s}} $$
が得られます（$|s| < 1$ のとき）。したがって、
$$ F(s) = 1 – \sqrt{1 – s} $$
原点に帰還する確率は $F(1) = \lim_{s \to 1^-} F(s) = 1 – \sqrt{1-1} = 1$ です。
これが「1次元の対称酔歩は必ず家に帰る」ことの厳密な証明です。
初帰還時刻の期待値は $E[T_0] = F'(1) = \lim_{s \to 1^-} \frac{1}{2\sqrt{1-s}} = +\infty$ なので、初帰還時刻の期待値は無限大です。つまり「必ず帰るが、いつ帰るかの期待値は無限大」という不思議な状況です。これは「ヌル再帰」（null recurrent）と呼ばれる状態であり、正再帰（positive recurrent）ではありません。
初帰還時刻の分布 $f_{2n}$ を具体的に求めると、$F(s) = 1 – \sqrt{1-s}$ のテイラー展開から、
$$ f_{2n} = \frac{1}{2n-1}\binom{2n-2}{n-1} 2^{-(2n-2)} \cdot \frac{1}{2} \sim \frac{1}{2\sqrt{\pi} n^{3/2}} $$
これは $n^{-3/2}$ で減衰する重い裾を持つ分布です。期待値が無限大になるのは、この重い裾のためです。
再帰性の別証明 — 級数の発散
もう一つの証明方法は、原点訪問回数の期待値を直接計算する方法です。原点を訪問する回数を $R = \sum_{n=1}^{\infty} \mathbb{1}(S_n = 0)$ とすると、
$$ E[R] = \sum_{n=1}^{\infty} P(S_n = 0) = \sum_{n=1}^{\infty} u_{2n} \sim \sum_{n=1}^{\infty} \frac{1}{\sqrt{\pi n}} = \infty $$
訪問回数の期待値が無限大であることから、原点を訪問する確率は1です（もし帰還確率が $\rho < 1$ ならば、帰還回数は幾何分布に従い期待値は $\rho/(1-\rho) < \infty$）。
一般に、帰還確率を $\rho$ とすると、原点訪問回数の期待値は $E[R] = \rho/(1-\rho)$ となります。$E[R] = \infty$ ならば $\rho = 1$ であり、$E[R] < \infty$ ならば $\rho < 1$ です。この関係を使えば、$\sum u_{2n}$ の発散・収束から再帰性・非再帰性を判定できます。
高次元: ポリアの定理
ジョージ・ポリア（George Polya）は1921年に、ランダムウォークの再帰性が次元に依存することを証明しました。
$$ \text{再帰的} \iff d \leq 2 $$
- 1次元: 再帰的。酔っ払いは必ず家に帰る
- 2次元: 再帰的。平面上の酔っ払いも必ず家に帰る
- 3次元以上: 非再帰的（transient）。3次元の酔っ払い（酔った鳥）は家に帰れない確率が正
この結果はしばしば「酔っ払いは家に帰れるが、酔った鳥は巣に帰れない」と表現されます。
ポリアの定理の証明
証明の核心は、$d$ 次元対称ランダムウォークの原点帰還確率 $u_{2n}^{(d)} = P(\bm{S}_{2n} = \bm{0})$ の漸近形を求め、$\sum u_{2n}^{(d)}$ の発散・収束を判定することです。
1次元: すでに示した通り、
$$ u_{2n}^{(1)} \sim \frac{1}{\sqrt{\pi n}} $$
$\sum \frac{1}{\sqrt{\pi n}}$ は $p$-級数（$p = 1/2 < 1$）なので発散します。したがって再帰的です。
2次元: 2次元格子ランダムウォークでは、各ステップで上下左右の4方向に等確率 $1/4$ で動きます。$2n$ ステップで原点に戻るには、x方向に $j$ ステップ（$+j/2$ 回右、$-j/2$ 回左）、y方向に $2n – j$ ステップ動く必要があります。精密な計算を行うと、
$$ u_{2n}^{(2)} = \sum_{j=0}^{n} \left[\binom{2j}{j}\binom{2(n-j)}{n-j}\right] \left(\frac{1}{4}\right)^{2n} \sim \frac{1}{\pi n} $$
$\sum \frac{1}{\pi n}$ は調和級数であり発散します。したがって2次元も再帰的です。ただし、1次元（$1/\sqrt{n}$）よりも帰還確率の減衰が速い（$1/n$）ため、原点に戻るのにより長い時間がかかる傾向があります。
3次元: 6方向（$\pm x, \pm y, \pm z$）に等確率 $1/6$ で動きます。漸近形は
$$ u_{2n}^{(3)} \sim \frac{C}{n^{3/2}} $$
$\sum \frac{C}{n^{3/2}}$ は $p$-級数（$p = 3/2 > 1$）なので収束します。したがって3次元は非再帰的です。
一般の $d$ 次元では $u_{2n}^{(d)} \sim C_d / n^{d/2}$ であり、$\sum n^{-d/2}$ は $d \leq 2$ のとき発散、$d \geq 3$ のとき収束します。
この結果は次元の効果を美しく表しています。次元が上がるほど「広がる空間」が大きくなり、原点に戻ることが難しくなります。1次元では左右2方向しかなく原点を通過しやすいですが、3次元では6方向に散らばるため原点を「見逃す」確率が高くなるのです。体積のスケーリングとして考えると、半径 $\sqrt{n}$ の球の体積は $d$ 次元で $\propto n^{d/2}$ なので、その逆数 $n^{-d/2}$ が帰還確率の漸近形に対応しています。
ギャンブラーの破産問題
問題の設定
ランダムウォークの古典的な応用として、ギャンブラーの破産問題（gambler’s ruin problem）を考えましょう。ギャンブラーが初期資産 $k$ で始め、各ゲームで確率 $p$ で1単位の勝ち、確率 $q = 1 – p$ で1単位の負けとします。資産が $N$ になるか（目標達成）、$0$ になるか（破産）のどちらかが起きたとき終了します。
この問題はランダムウォークの吸収壁（absorbing barrier）付きモデルとして定式化できます。位置 $0$ と $N$ が吸収壁であり、ランダムウォークがこれらの壁に到達すると停止します。停止時刻は $T = \inf\{n \geq 0 : S_n = 0 \text{ or } S_n = N\}$ であり、$S_0 = k$ です。
破産確率の導出
状態 $k$ からスタートして破産する確率を $r_k$ とします。境界条件は $r_0 = 1$（すでに破産）、$r_N = 0$（目標達成）です。
ワンステップ先の分析（first-step analysis）から、再帰方程式が得られます。
$$ r_k = p \cdot r_{k+1} + q \cdot r_{k-1}, \quad k = 1, 2, \dots, N-1 $$
この式は「現在の状態 $k$ から、確率 $p$ で $k+1$ に行き（破産確率 $r_{k+1}$）、確率 $q$ で $k-1$ に行く（破産確率 $r_{k-1}$）」ことを表しています。
$p + q = 1$ を使って整理すると、
$$ p \cdot r_k + q \cdot r_k = p \cdot r_{k+1} + q \cdot r_{k-1} $$
$$ p(r_{k+1} – r_k) = q(r_k – r_{k-1}) $$
$\delta_k = r_k – r_{k-1}$ とおくと、$p \cdot \delta_{k+1} = q \cdot \delta_k$ より $\delta_{k+1} = (q/p)\delta_k$ が得られます。これは等比数列であり、
$$ \delta_k = \left(\frac{q}{p}\right)^{k-1}\delta_1 $$
$r_0 = 1$ から $r_k = 1 + \sum_{j=1}^{k}\delta_j$ を計算し、$r_N = 0$ から $\delta_1$ を決定します。
$p \neq q$ のとき: $\rho = q/p \neq 1$ とおくと、
$$ r_k = 1 + \delta_1 \sum_{j=1}^{k} \rho^{j-1} = 1 + \delta_1 \frac{1 – \rho^k}{1 – \rho} $$
$r_N = 0$ から $\delta_1 = -(1 – \rho)/(1 – \rho^N)$ を得て、
$$ r_k = \frac{\rho^k – \rho^N}{1 – \rho^N} = \frac{(q/p)^k – (q/p)^N}{1 – (q/p)^N} $$
$p = q = 1/2$ のとき: $\rho = 1$ なので $\delta_k = \delta_1$（等差数列）です。
$$ r_k = 1 + k\delta_1 $$
$r_N = 0$ から $\delta_1 = -1/N$ を得て、
$$ r_k = 1 – \frac{k}{N} $$
結果の解釈と具体例
公平なゲーム（$p = 1/2$）では、初期資産 $k = 1$, $N = 100$ のとき破産確率は $r_1 = 1 – 1/100 = 0.99$ です。つまり、99%の確率で破産します。これは「公平なゲームでも資金量の少ない方が圧倒的に不利」であることを示しています。マルチンゲール理論の観点からは、公平なゲーム（$E[X_i] = 0$）では資産は「平均的には増えも減りもしない」にもかかわらず、吸収壁の存在により小さい方の壁に到達しやすくなるのです。
不利なゲーム（$p < 1/2$）ではさらに状況は悪化します。$p = 0.49$, $k = 50$, $N = 100$ のとき、$(q/p) = 51/49 \approx 1.0408$ なので、
$$ r_{50} = \frac{1.0408^{50} – 1.0408^{100}}{1 – 1.0408^{100}} \approx 0.88 $$
わずか1%の不利が、破産確率を50%（公平なゲーム）から88%に跳ね上げます。カジノのハウスエッジが小さくても（例えばルーレットの $p \approx 0.474$）、十分長くプレイすれば客の破産は「ほぼ確実」なのです。
逆に、$p = 0.51$（わずかに有利）の場合、$r_{50} \approx 0.12$ となり、破産確率は大幅に下がります。ゲームのわずかな有利不利が、長期的な結果に劇的な影響を与えます。
勝利確率
目標達成（$N$ に到達）する確率は $w_k = 1 – r_k$ です。
$p \neq q$ のとき:
$$ w_k = \frac{1 – (q/p)^k}{1 – (q/p)^N} $$
$p = q = 1/2$ のとき:
$$ w_k = \frac{k}{N} $$
公平なゲームでの勝利確率は初期資産に比例します。これはマルチンゲール性からも直接導けます。$S_n$ はマルチンゲールなので、任意停止定理から $E[S_T] = S_0 = k$ です。$S_T$ は $0$（破産）または $N$（目標達成）の値を取るので、$E[S_T] = 0 \cdot r_k + N \cdot w_k = Nw_k = k$、したがって $w_k = k/N$ です。
ゲームの持続時間
破産するか目標達成するまでの期待ゲーム数 $D_k$ も同様のfirst-step analysisで求まります。
$$ D_k = p \cdot D_{k+1} + q \cdot D_{k-1} + 1, \quad D_0 = D_N = 0 $$
$p = q = 1/2$ のとき: 特殊解 $D_k^{(p)} = -k^2$ を使って一般解を構成すると、
$$ D_k = k(N – k) $$
$k = 50$, $N = 100$ ならば $D_{50} = 50 \times 50 = 2500$ ゲームです。中央からスタートしたときに最も長く続きます。
$p \neq q$ のとき: $\mu = p – q$ とおくと、
$$ D_k = \frac{1}{\mu}\left[\frac{N(1 – \rho^k)}{1 – \rho^N} – k\right] $$
ここで $\rho = q/p$ です。
ギャンブラーの破産問題は、ランダムウォークの到達時刻に関する基本的な結果です。次に、より一般的な初到達時刻と反射原理を見ていきましょう。
初到達時刻と反射原理
初到達時刻
対称ランダムウォークが水準 $a > 0$ に初めて到達する時刻を初到達時刻（first passage time）と呼びます。
$$ T_a = \inf\{n \geq 1 : S_n = a\} $$
再帰性から $P(T_a < \infty) = 1$（対称ランダムウォークの場合）です。しかし、$E[T_a] = \infty$ であり、到達は確実ですが「いつ到達するか」の期待値は無限大です。
$T_1$（初めて $+1$ に到達する時刻）の分布を求めましょう。$T_1$ は奇数の値のみを取ります（パリティの制約）。$P(T_1 = 1) = p = 1/2$ は最初のステップで $+1$ に行く確率です。一般に、
$$ P(T_1 = 2n – 1) = \frac{1}{2n-1}\binom{2n-2}{n-1}\left(\frac{1}{2}\right)^{2n-1} $$
この式はカタラン数 $C_n = \frac{1}{n+1}\binom{2n}{n}$ と密接に関連しています。初到達時刻の分布は $n^{-3/2}$ の重い裾を持ち、このために $E[T_1] = \infty$ となります。
一般の $T_a$（$a > 0$）の分布は、$T_a = T_1 + T_1′ + \cdots + T_1^{(a)}$（$a$ 回の独立な初到達時刻の和）として表現できます。これは、$S_n$ が $1, 2, \dots, a$ に順次到達することから従います。各 $T_1^{(i)}$ は同一分布（強マルコフ性による）なので、$E[T_a] = a \cdot E[T_1] = \infty$ です。
反射原理
反射原理（reflection principle）は、ランダムウォークの最大値や初到達時刻の分布を求めるための強力なテクニックです。
定理（反射原理）: 対称ランダムウォークで $a > 0$ とすると、
$$ P\left(\max_{0 \leq k \leq n} S_k \geq a\right) = 2P(S_n \geq a) – P(S_n = a) $$
$n$ が大きいとき（連続近似が有効な場合）、$P(S_n = a)$ は無視できるので、近似的に
$$ P\left(\max_{0 \leq k \leq n} S_k \geq a\right) \approx 2P(S_n \geq a) $$
反射原理の証明のアイデアは次の通りです。$S_k$ が水準 $a$ に初めて到達した時刻を $T_a$ とします。$T_a \leq n$ かつ $S_n < a$ となるパスを考えます。このパスを時刻 $T_a$ 以降、水準 $a$ を中心に「反射」させます。具体的には、$k > T_a$ のステップで $X_k = +1$ を $-1$ に、$-1$ を $+1$ に置き換えます。すると $S_n$ の値は $2a – S_n > a$ になります。
対称性から、反射前後のパスの確率は等しいので、
$$ P(T_a \leq n, S_n < a) = P(T_a \leq n, S_n > a) = P(S_n > a) $$
最後の等号は「$S_n > a$ ならば必ず $T_a \leq n$（途中で水準 $a$ を通過している）」から従います。したがって、
$$ P(T_a \leq n) = P(S_n \geq a) + P(S_n > a) = 2P(S_n > a) + P(S_n = a) $$
反射原理は、ブラウン運動の最大値の分布を求める際にも同様の形で使われ、金融工学のバリアオプション価格付けの基礎となっています。
投票問題
反射原理の応用として、投票問題（ballot problem）があります。
選挙で候補者Aが $a$ 票、候補者Bが $b$ 票を獲得し、$a > b$ で勝利したとします。開票過程でAが常にBより多くの票を得ていた（一度もBにリードされなかった）確率はいくらでしょうか？
定理（投票問題の定理）: Aが開票過程を通じて常にリードしている確率は
$$ P(\text{Aが常にリード}) = \frac{a – b}{a + b} $$
この結果はランダムウォークの経路計算から導かれます。$n = a + b$ ステップのランダムウォークで、$S_n = a – b$ かつ途中で $S_k \leq 0$ にならないパスの数を数える問題に帰着されます。反射原理を使って「原点に触れるパス」の数を数え、全パス数から引くことで結果が得られます。
この定理の美しさは、最終結果のみ（$a$ 票と $b$ 票）から途中経過の性質が決まる点にあります。たとえば $a = 60$, $b = 40$ のとき、Aが常にリードしている確率はわずか $20/100 = 0.2$ です。最終的に圧勝していても、開票途中で逆転が起こる確率は高いのです。
アークサイン法則
正の側にいる時間
対称1次元ランダムウォークにおいて、$2n$ ステップのうち正の側（$S_k > 0$）にいるステップ数の分布は、驚くべきことに一様分布ではなくアークサイン分布に従います。
$2n$ ステップのうち $S_k > 0$ であるステップ数を $P_{2n}$ とし、その割合を $T_{2n} = P_{2n}/(2n)$ とします。ポール・レヴィ（Paul Levy）は次の極限定理を証明しました。
$$ \lim_{n \to \infty} P\left(T_{2n} \leq x\right) = \frac{2}{\pi}\arcsin\sqrt{x}, \quad 0 \leq x \leq 1 $$
この分布の密度関数は
$$ f(x) = \frac{1}{\pi\sqrt{x(1-x)}} $$
で、$x = 0$ と $x = 1$ の近くに確率が集中するU字型です。
直感に反する結果
アークサイン法則は「ランダムウォークは時間の大部分を正の側か負の側のどちらか一方で過ごす傾向がある」ことを意味します。「長時間歩けば正負を半々に過ごすだろう」という直感に完全に反する結果です。
具体的な確率を計算しましょう。
$$ P\left(T_{2n} \leq 0.1\right) = \frac{2}{\pi}\arcsin\sqrt{0.1} \approx 0.205 $$
$$ P\left(T_{2n} \geq 0.9\right) = 1 – \frac{2}{\pi}\arcsin\sqrt{0.9} \approx 0.205 $$
つまり、時間の90%以上を正の側で過ごすか、10%以下しか正の側にいない確率がそれぞれ約20%もあります。合計で約41%の確率で「極端に偏った」結果になります。
さらに、$P(0.45 \leq T_{2n} \leq 0.55) = \frac{2}{\pi}[\arcsin\sqrt{0.55} – \arcsin\sqrt{0.45}] \approx 0.064$ であり、正の側と負の側でほぼ均等に過ごす確率はわずか6%程度です。
この結果は実用的にも重要です。コインの表裏が均等に出るはずのゲームでも、「一方が長期間リードし続ける」現象は極めて普通のことなのです。スポーツのリーグ戦での連勝・連敗、株価の長期的な上昇トレンド・下降トレンドなど、ランダムな過程に見られる「偏り」の多くはアークサイン法則で説明できます。
3つのアークサイン法則
実はアークサイン法則には3つのバージョンがあり、すべて同じアークサイン分布に従います。
- 正の側にいた時間の割合: 上で述べた $T_{2n} = P_{2n}/(2n)$
- 最後に0を通った時刻の割合: $2n$ ステップの中で最後に $S_k = 0$ となった時刻 $L_{2n}$ の $2n$ に対する割合 $L_{2n}/(2n)$
- 最大値を取った時刻の割合: $S_k$ が最大値を取った時刻 $M_{2n}$ の $2n$ に対する割合 $M_{2n}/(2n)$
3つの量がすべて同じ分布に従うという事実は、対称ランダムウォークの深い構造を反映しています。特に第2の法則は「最後に原点を通過した時刻」が端（$0$ または $2n$）の近くに集中することを意味し、「原点訪問は散発的に起こる」というランダムウォークの特徴を示しています。
ブラウン運動への収束
ドンスカーの不変原理
ランダムウォークを適切にスケーリングすると、連続極限としてブラウン運動（Brownian motion）が得られます。
$$ W_n(t) = \frac{S_{\lfloor nt \rfloor}}{\sqrt{n}} \xrightarrow{d} B(t) \quad (n \to \infty) $$
ここで $B(t)$ は標準ブラウン運動であり、$\xrightarrow{d}$ は分布収束を表します。この収束は点ごとの収束ではなく、連続関数空間 $C[0,1]$ 上の弱収束であり、ドンスカーの不変原理（Donsker’s invariance principle）または関数中心極限定理（functional central limit theorem）として知られています。
この結果は、ランダムウォークが「ブラウン運動の離散近似」であることを数学的に保証しています。
収束の直感
時間を $1/n$ 刻みにし、各ステップの大きさを $1/\sqrt{n}$ にスケーリングします。$n \to \infty$ で無限に細かい時間ステップと無限に小さな空間ステップの極限を取ると、離散的なジグザグが連続的な曲線（ブラウン運動）に収束します。
スケーリング因子 $1/\sqrt{n}$ は中心極限定理から来ています。$S_n = X_1 + \cdots + X_n$ の標準偏差が $\sqrt{n}$ なので、$S_n/\sqrt{n}$ が有限の分散を持つ分布に収束するのです。
具体的に、固定された $t$ に対して $W_n(t) = S_{\lfloor nt \rfloor}/\sqrt{n}$ の分布を考えると、中心極限定理から $S_{\lfloor nt \rfloor}/\sqrt{\lfloor nt \rfloor} \to N(0,1)$ であり、$\sqrt{\lfloor nt \rfloor}/\sqrt{n} \to \sqrt{t}$ なので、$W_n(t) \to N(0, t)$ となります。これはブラウン運動の周辺分布 $B(t) \sim N(0, t)$ と一致します。
不変原理の「不変」の意味
ドンスカーの不変原理の「不変」とは、スケーリングされたランダムウォークの極限が、ステップ分布の詳細に依存しない（$\pm 1$ でなくても任意の平均0、分散 $\sigma^2$ の分布でよい）という意味です。これは中心極限定理の関数空間版と言えます。
具体的には、$X_i$ が平均0、分散 $\sigma^2$ の任意のi.i.d.列であれば、
$$ \frac{S_{\lfloor nt \rfloor}}{\sigma\sqrt{n}} \xrightarrow{d} B(t) \quad (n \to \infty) $$
が成り立ちます。ステップの分布が正規分布でも、$\pm 1$ でも、一様分布でも、極限は同じ標準ブラウン運動になります。この普遍性がブラウン運動を数学的に特別なものにしています。
ランダムウォークからブラウン運動の性質を導く
ドンスカーの不変原理を使うと、ブラウン運動の性質をランダムウォークの離散的な性質から導くことができます。これを連続写像定理（continuous mapping theorem）と組み合わせて使います。
- 再帰性: 1次元ランダムウォークの再帰性から、1次元ブラウン運動の再帰性が従います
- アークサイン法則: ランダムウォークのアークサイン法則から、ブラウン運動の $\{t \in [0,1] : B(t) > 0\}$ のルベーグ測度がアークサイン分布に従うことが導かれます
- 反射原理: ランダムウォークの反射原理から、$P(\max_{0 \leq s \leq t} B(s) \geq a) = 2P(B(t) \geq a) = 2\Phi(-a/\sqrt{t})$ が導かれます
- 最大値の分布: $\max_{0 \leq s \leq t} B(s)$ は $|B(t)|$ と同じ分布（半正規分布）を持つことが反射原理から従います
このように、離散モデルの結果を連続極限に持ち上げることは、確率論の強力な手法です。
多次元ランダムウォーク
$d$ 次元格子上のランダムウォーク
$d$ 次元の単純ランダムウォークでは、各ステップで $2d$ 個の隣接格子点のうち1つに等確率 $1/(2d)$ で移動します。
$$ \bm{S}_n = \bm{S}_{n-1} + \bm{e}_i \quad \text{（$\pm \bm{e}_1, \pm \bm{e}_2, \dots, \pm \bm{e}_d$ から等確率で選択）} $$
ここで $\bm{e}_j$ は第 $j$ 座標方向の単位ベクトルです。各軸方向の成分は独立なランダムウォークではなく、各ステップで1つの軸方向にしか動けない点に注意が必要です。
$d$ 次元ランダムウォークの各成分 $S_n^{(j)}$ は「時刻が不均一な1次元ランダムウォーク」と見なせます。つまり、各ステップで確率 $1/d$ で第 $j$ 軸方向に動き（$\pm 1$ に等確率）、確率 $1 – 1/d$ で動きません。
基本的な性質として、$E[\bm{S}_n] = \bm{0}$ であり、各成分の分散は $\text{Var}(S_n^{(j)}) = n/d$ です（各ステップで確率 $1/d$ のみ第 $j$ 軸方向に移動するため）。原点からの平均二乗距離は
$$ E[|\bm{S}_n|^2] = \sum_{j=1}^d \text{Var}(S_n^{(j)}) = n $$
であり、次元によらず $n$ に比例します。
2次元ランダムウォーク
2次元ランダムウォークは、格子点上を上下左右の4方向に等確率 $1/4$ で動きます。ポリアの定理により再帰的であり、原点に必ず戻ります。
2次元での原点帰還確率の漸近形は先述の通り $u_{2n}^{(2)} \sim 1/(\pi n)$ です。これは1次元の $u_{2n}^{(1)} \sim 1/\sqrt{\pi n}$ よりも速く減衰しますが、級数はなお発散します。
2次元ランダムウォークの到達可能範囲は正方格子のパリティ制約を受けます。時刻 $n$ で到達可能な格子点は、$x + y + n$ が偶数であるもの（チェッカーボードパターン）に限られます。
高次元での非再帰性と帰還確率
3次元ランダムウォークが原点に戻る確率はワトソン（Watson）の三重積分
$$ p_3 = 1 – \left[\frac{3}{(2\pi)^3} \iiint_{[-\pi,\pi]^3} \frac{d\theta_1 \, d\theta_2 \, d\theta_3}{3 – \cos\theta_1 – \cos\theta_2 – \cos\theta_3}\right]^{-1} $$
で正確に計算され、$p_3 \approx 0.3405$ です。
次元が上がるにつれて帰還確率は急速に減少します。
| 次元 $d$ | 帰還確率 | $\sum u_{2n}^{(d)}$ |
|---|---|---|
| 1 | 1.000 | $\infty$ |
| 2 | 1.000 | $\infty$ |
| 3 | 0.3405 | 1.5164 |
| 4 | 0.1932 | 1.2395 |
| 5 | 0.1352 | 1.1562 |
| 6 | 0.1047 | 1.1171 |
高次元ではランダムウォークは過渡的（transient）であり、確率1で無限遠に発散します。つまり $|\bm{S}_n| \to \infty$（$n \to \infty$）が確率1で成り立ちます。
高次元での帰還確率の近似として、$d$ が大きいとき $p_d \approx 1/(2d)$ が成り立ちます。これは「各ステップで $2d$ 方向のうち1方向にしか戻れない」という直感に対応しています。
ランダムウォークの速度と拡散係数
$d$ 次元ランダムウォークの拡散係数は $D = 1/(2d)$ です。これは、各成分の分散が $\text{Var}(S_n^{(j)}) = n/d = 2Dn$ であることから定義されます。連続極限では拡散方程式 $\partial_t u = D \nabla^2 u$ に対応します。
ランダムウォーカーの典型的な変位は $|\bm{S}_n| \sim \sqrt{n}$ です。これは $d$ 次元のブラウン運動の拡散的スケーリング $\sqrt{Dt}$ の離散版です。
Pythonによるシミュレーション
import numpy as np
import matplotlib.pyplot as plt
np.random.seed(42)
fig, axes = plt.subplots(2, 2, figsize=(13, 10))
# 1次元ランダムウォーク
ax = axes[0, 0]
n_steps = 1000
for i in range(5):
steps = np.random.choice([-1, 1], size=n_steps)
walk = np.cumsum(steps)
walk = np.insert(walk, 0, 0)
ax.plot(walk, linewidth=0.8, alpha=0.7)
ax.axhline(0, color="black", linewidth=0.5)
ax.fill_between(range(n_steps + 1),
-2 * np.sqrt(np.arange(n_steps + 1)),
2 * np.sqrt(np.arange(n_steps + 1)),
alpha=0.1, color="gray", label=r"$\pm 2\sqrt{n}$")
ax.set_xlabel("Step n", fontsize=11)
ax.set_ylabel("Position $S_n$", fontsize=11)
ax.set_title("1D simple random walk", fontsize=12)
ax.legend(fontsize=9)
ax.grid(True, alpha=0.3)
# 2次元ランダムウォーク
ax = axes[0, 1]
n_steps_2d = 5000
for i in range(3):
directions = np.random.randint(0, 4, n_steps_2d)
dx = np.where(directions == 0, 1, np.where(directions == 1, -1, 0))
dy = np.where(directions == 2, 1, np.where(directions == 3, -1, 0))
x = np.cumsum(dx)
y = np.cumsum(dy)
ax.plot(x, y, linewidth=0.5, alpha=0.6)
ax.plot(0, 0, "ro", markersize=8, zorder=5, label="Origin")
ax.set_xlabel("x", fontsize=11)
ax.set_ylabel("y", fontsize=11)
ax.set_title("2D random walk (recurrent)", fontsize=12)
ax.set_aspect("equal")
ax.legend(fontsize=9)
ax.grid(True, alpha=0.3)
# ブラウン運動への収束
ax = axes[1, 0]
n_values = [10, 100, 1000, 10000]
colors = ["red", "orange", "blue", "black"]
np.random.seed(123)
for n_val, color in zip(n_values, colors):
steps = np.random.choice([-1, 1], size=n_val)
walk = np.cumsum(steps) / np.sqrt(n_val)
walk = np.insert(walk, 0, 0)
t = np.linspace(0, 1, n_val + 1)
ax.plot(t, walk, linewidth=0.8, alpha=0.7, color=color,
label=f"n={n_val}")
ax.set_xlabel("t", fontsize=11)
ax.set_ylabel(r"$S_{\lfloor nt \rfloor} / \sqrt{n}$", fontsize=11)
ax.set_title("Convergence to Brownian motion", fontsize=12)
ax.legend(fontsize=9)
ax.grid(True, alpha=0.3)
# 再帰性の検証（3次元vs1次元）
ax = axes[1, 1]
n_sim = 1000
n_steps_rec = 10000
return_1d = 0
return_3d = 0
for _ in range(n_sim):
# 1D
walk_1d = np.cumsum(np.random.choice([-1, 1], n_steps_rec))
if np.any(walk_1d == 0):
return_1d += 1
# 3D
dirs = np.random.choice([-1, 1], (n_steps_rec, 3))
walk_3d = np.cumsum(dirs, axis=0)
if np.any(np.all(walk_3d == 0, axis=1)):
return_3d += 1
dims = ["1D", "2D\n(theory)", "3D"]
probs = [return_1d / n_sim, 1.0, return_3d / n_sim]
theory = [1.0, 1.0, 0.3405]
x_pos = np.arange(3)
ax.bar(x_pos - 0.15, probs, 0.3, color="steelblue", alpha=0.7,
label="Simulation")
ax.bar(x_pos + 0.15, theory, 0.3, color="orange", alpha=0.7,
label="Theory")
ax.set_xticks(x_pos)
ax.set_xticklabels(dims)
ax.set_ylabel("Return probability", fontsize=11)
ax.set_title("Polya's theorem: recurrence by dimension", fontsize=12)
ax.legend(fontsize=10)
ax.grid(True, alpha=0.3, axis="y")
plt.tight_layout()
plt.show()
このシミュレーションから、以下の重要な性質が確認できます。
-
1次元ランダムウォーク（左上）: 複数のサンプルパスが原点を何度も横切っています。灰色の領域 $\pm 2\sqrt{n}$ が位置の典型的な範囲を示しており、$\sqrt{n}$ のスケーリングが確認できます。パスは原点から遠く離れることもありますが、常に $\pm 2\sqrt{n}$ の範囲にほぼ収まっています
-
2次元ランダムウォーク（右上）: 軌跡が原点付近を何度も訪れており、2次元での再帰性を視覚的に示しています。軌跡は自己交差が多く、探索的な動きをしていることがわかります
-
ブラウン運動への収束（左下）: $n$ を増やすとスケーリングされたランダムウォークがブラウン運動の滑らかな軌跡に近づいていく様子が見えます。$n = 10$ ではギザギザですが、$n = 10000$ のパスは連続的な曲線にほぼ見えます
-
ポリアの定理の検証（右下）: 1次元の帰還確率は1に近く、3次元は約0.34であり、理論値とよく一致しています
アークサイン法則のシミュレーション
import numpy as np
import matplotlib.pyplot as plt
np.random.seed(42)
n_sim = 50000
n_steps = 10000
# 正の側にいた割合を計算
positive_fracs = np.zeros(n_sim)
for i in range(n_sim):
steps = np.random.choice([-1, 1], size=n_steps)
walk = np.cumsum(steps)
positive_fracs[i] = np.mean(walk > 0)
fig, axes = plt.subplots(1, 2, figsize=(13, 5))
# ヒストグラム
ax = axes[0]
ax.hist(positive_fracs, bins=100, density=True, alpha=0.7,
color='steelblue', edgecolor='white', label='Simulation')
x = np.linspace(0.01, 0.99, 500)
arcsine_pdf = 1 / (np.pi * np.sqrt(x * (1 - x)))
ax.plot(x, arcsine_pdf, 'r-', linewidth=2, label='Arcsine density')
ax.set_xlabel('Fraction of time spent positive', fontsize=12)
ax.set_ylabel('Density', fontsize=12)
ax.set_title('Arcsine Law for Symmetric Random Walk', fontsize=13)
ax.legend(fontsize=11)
ax.grid(True, alpha=0.3)
# ギャンブラーの破産シミュレーション
ax = axes[1]
k_values = np.arange(1, 100)
N_val = 100
ruin_theory = 1 - k_values / N_val # p=1/2
n_sim_ruin = 5000
ruin_sim = np.zeros(len(k_values))
for idx, k_init in enumerate(k_values[::10]):
count = 0
for _ in range(n_sim_ruin):
pos = k_init
while 0 < pos < N_val:
pos += np.random.choice([-1, 1])
if pos == 0:
count += 1
ruin_sim[idx * 10] = count / n_sim_ruin
ax.plot(k_values, ruin_theory, 'b-', linewidth=2, label='Theory: $1 - k/N$')
sim_mask = ruin_sim > 0
ax.scatter(k_values[sim_mask], ruin_sim[sim_mask],
color='red', s=40, zorder=5, label='Simulation')
ax.set_xlabel('Initial wealth k', fontsize=12)
ax.set_ylabel('Ruin probability', fontsize=12)
ax.set_title(f"Gambler's ruin (p=0.5, N={N_val})", fontsize=13)
ax.legend(fontsize=11)
ax.grid(True, alpha=0.3)
plt.tight_layout()
plt.show()
左図のヒストグラムはU字型で、$x = 0$ と $x = 1$ の近くに確率が集中しています。理論的なアークサイン分布の密度関数（赤線）と非常によく一致しています。ランダムウォークは時間の大部分を片側（正または負）で過ごす傾向があり、正負を均等に行き来するという直感に反する振る舞いが数値的に確認されています。50,000回のシミュレーションで、時間の90%以上を正の側で過ごしたケースが約20%もあることが、アークサイン法則の驚くべき帰結です。
右図はギャンブラーの破産問題のシミュレーション結果を示しています。理論曲線 $r_k = 1 – k/N$（青線）とシミュレーション結果（赤点）がよく一致しており、初期資産が少ないほど破産確率が高いという理論的予測が裏付けられています。
まとめ
本記事では、ランダムウォークの理論を1次元から多次元まで解説しました。
- 1次元対称ランダムウォークは $E[S_n] = 0$, $\text{Var}(S_n) = n$ であり、位置の不確実性は $\sqrt{n}$ で広がります。$S_n$ の分布は二項分布に従い、原点帰還確率は $P(S_{2n} = 0) \sim 1/\sqrt{\pi n}$ です
- 再帰性の証明: 母関数 $U(s) = 1/\sqrt{1-s}$ と $F(s) = 1 – \sqrt{1-s}$ の関係から、$F(1) = 1$（確率1で帰還）が示されます。初帰還時刻の期待値は無限大です
- ポリアの定理: 対称ランダムウォークは1次元と2次元で再帰的、3次元以上で非再帰的です。$\sum u_{2n}^{(d)}$ の発散・収束（$u_{2n}^{(d)} \sim C_d / n^{d/2}$）がその判定基準です
- ギャンブラーの破産問題: 公平なゲームでも資金量の少ない方が圧倒的に不利であり、破産確率は $1 – k/N$ です。非対称の場合は $(q/p)^k$ に関する公式で表されます
- 反射原理: 最大値の分布 $P(\max S_k \geq a) = 2P(S_n \geq a) – P(S_n = a)$ や初到達時刻の解析に不可欠なテクニックです
- アークサイン法則: ランダムウォークは時間の大部分を片側で過ごす傾向があり、密度 $1/(\pi\sqrt{x(1-x)})$ のU字型分布に従います
- ドンスカーの不変原理: $S_{\lfloor nt \rfloor}/\sqrt{n}$ はブラウン運動に弱収束し、この収束はステップ分布に依存しません
次のステップとして、以下の記事も参考にしてください。
- ブラウン運動の性質 — ランダムウォークの連続極限
- マルチンゲール収束定理 — マルチンゲールの漸近理論
- 幾何ブラウン運動 — 株価モデリング
- マルコフ連鎖の理論 — 離散時間マルコフ連鎖