ランダムウォークと再帰性

🎓 レベル：標準　|　重要度：A（王道の具体例） 📎 前提：状態の分類、定常性と独立増分

要点（BLUF）

単純ランダムウォーク：各ステップで隣の格子点へ等確率に動く、独立増分を持つマルコフ連鎖。確率過程の最も基本的な例です。
ポリアの定理：対称単純ランダムウォークは1次元・2次元では再帰（確率1で原点に戻る）、3次元以上では過渡（戻らない確率が正）。
「酔っぱらいは家に帰れるが、酔った鳥は帰れない」 — 次元が上がると逃げ道が増え、再帰性が壊れます。

概念

ランダムウォークは、独立な小さな変位を足し続ける過程です（定常性と独立増分の独立増分の典型）。マルコフ連鎖としては「今の位置だけで次が決まる」連鎖。その最も劇的な性質が、戻ってこられるかどうかが空間の次元で切り替わることです。低次元では動ける方向が限られ必ず原点を踏み直しますが、高次元では広大な空間に拡散して二度と戻らなくなります。

数式による定式化

$\mathbb{Z}^d$ 上の対称単純ランダムウォーク： $X_n = \sum_{k=1}^n \xi_k$ 、各 $\xi_k$ は $2d$ 個の単位方向ベクトルを等確率 $1/(2d)$ でとる。原点回帰確率 $f=P(\exists n\ge 1: X_n=0)$ とし、回帰のしやすさは

\sum_{n=0}^{\infty} P(X_n = 0) \quad \begin{cases} = \infty & \Rightarrow \text{再帰}\ (f=1) \\ < \infty & \Rightarrow \text{過渡}\ (f<1) \end{cases}

で判定します（状態の分類の再帰判定そのもの）。局所中心極限定理より $P(X_{2n}=0)\sim C\, n^{-d/2}$ なので、

\sum_n n^{-d/2}\ \begin{cases} \text{発散} & d\le 2 \quad(\text{再帰}) \\ \text{収束} & d\ge 3 \quad(\text{過渡}) \end{cases}

これがポリアの定理です。 $d=3$ の回帰確率は $f\approx 0.3405$ （ポリアの定数）。

直観

要するに「次元が上がると逃げ道が増える」。1次元では左右しかなく、拡散の幅 $\sqrt{n}$ に対し原点近傍にいる確率が $n^{-1/2}$ と大きいので、足し合わせると無限回原点を踏みます。3次元では位置が $\sqrt{n}$ のオーダーで広がる空間（体積 $n^{3/2}$ ）に薄く散らばり、原点にいる確率 $n^{-3/2}$ が速く減るため、総訪問回数が有限で済んでしまう。発散と収束の境目がちょうど $d=2$ にあります。

具体例

1〜3次元で「ある歩数以内に原点へ回帰した割合」を測り、歩数を倍にしたときの挙動を見ます。再帰（ $d=1,2$ ）は1へ向かって増え続け、過渡（ $d=3$ ）はポリア定数付近で頭打ちになるはずです。

import numpy as np
def return_frac(d, n_steps, n_walks=40000, seed=9):
    rng = np.random.default_rng(seed)
    pos = np.zeros((n_walks, d), dtype=np.int32)
    returned = np.zeros(n_walks, dtype=bool)
    idx = np.arange(n_walks)
    for _ in range(n_steps):
        ax = rng.integers(0, d, size=n_walks)        # 動かす軸
        sign = rng.integers(0, 2, size=n_walks) * 2 - 1
        pos[idx, ax] += sign
        returned |= ~pos.any(axis=1)                 # 原点に戻ったか
    return returned.mean()
for d in [1, 2, 3]:
    print(f"d={d}: 2000歩={return_frac(d, 2000):.3f}  8000歩={return_frac(d, 8000):.3f}")
# d=1: 2000歩=0.982  8000歩=0.991
# d=2: 2000歩=0.701  8000歩=0.735
# d=3: 2000歩=0.334  8000歩=0.338

$d=1$ はほぼ1、 $d=2$ は歩数を増やすとさらに1へ近づく（再帰だが対数的に遅い）。 $d=3$ は歩数を4倍にしても 0.334→0.338 とほぼ動かず、ポリア定数 $\approx 0.34$ で飽和します — これが過渡の証拠です。

他過程との関係

ランダムウォークのスケール極限がブラウン運動の定義と性質（ドンスカーの定理）。離散の足し算が連続の拡散になります。
中心化されたランダムウォークはマルチンゲールの定義と例の最も基本的なマルチンゲールで、その停止問題が停止時刻と任意停止定理のギャンブラーの破産に直結します。

数式の直観的意味

ポリアの定理の本質は「 $\sum n^{-d/2}$ の収束・発散」、つまり拡散の速さ（幅 $\sqrt{n}$ ）と空間の広さ（次元 $d$ ）の競争です。2次元は拡散が空間をちょうど埋め尽くす臨界次元で、再帰ではあるが平均回帰時間は無限（零再帰）。だから定常分布と収束の定常分布は存在しません（正再帰ではないため）。

⚠️ よくある誤解

2次元は再帰だが「すぐ戻る」わけではない。零再帰なので平均回帰時間は無限。シミュレーションで $d=2$ の回帰割合が1から遠いのはこのためで、過渡だからではありません。
「過渡＝戻らない」ではなく「戻らない確率が正」。 $d=3$ でも約34%は戻ります。ただし戻る回数の期待値が有限。
有限グラフ上のランダムウォークは常に再帰。ポリアの定理は無限格子 $\mathbb{Z}^d$ の話です。
非対称（ドリフトあり）なら1次元でも過渡。対称性が再帰の鍵です。

対応シミュレーション

本文コードの n_steps をさらに増やすと、 $d=2$ の回帰割合がゆっくり1へ近づき、 $d=3$ が 0.34 付近で動かない対比が一層はっきりします。stochastic-processes-study/simulations/ に格子ウォークの可視化を置きます。