単純ランダムウォークと反射原理

反射原理を使って、ランダムウォークの到達確率や最大値の分布を数えられる

前提

到達確率と平均到達時間（大学数学確率・統計）

この技能までの道筋（64 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
順列・円順列・重複順列（数学A 場合の数と確率）
組合せ（数学A 場合の数と確率）
確率の定義と和事象・余事象（数学A 場合の数と確率）
条件付き確率と乗法定理（数学A 場合の数と確率）
四則の混じった計算の順序（算数計算と数のきまり）
等間隔にならんだ数の和（算数計算と数のきまり）
分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
等差・等比数列の和と Σ （数学B 数列）
マルコフ連鎖と推移確率（大学数学確率・統計）
期待値（数学A 場合の数と確率）
確率変数と確率分布（数学B 統計的な推測）
平均と合計（算数いろいろな文章題）
平均値・中央値・最頻値（中学数学データの活用）
代表値（平均値・中央値・最頻値）（数学I データの分析）
分散と標準偏差（数学I データの分析）
変量の変換と平均・分散（数学I データの分析）
確率変数の期待値・分散と $a X + b$ （数学B 統計的な推測）
確率変数の和と積（独立な場合）（数学B 統計的な推測）
乗法公式による展開（中学数学数と式）
因数分解（中学数学数と式）
3 次式までの展開と因数分解（数学I 数と式）
微分係数と導関数の定義（数学II 微分法と積分法）
多項式の微分（数学II 微分法と積分法）
多項式の不定積分（数学II 微分法と積分法）
数列の極限（数学III 極限）
関数の極限（数学III 極限）
積と商の微分（数学III 微分法）
合成関数の微分（数学III 微分法）
円の周の長さと面積（算数平面図形）
おうぎ形の弧の長さと面積（算数平面図形）
弧の長さからおうぎ形の中心角と面積を求める（中学数学平面図形）
三角形・四角形の面積（算数平面図形）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
三平方の定理（中学数学相似と三平方の定理）
特別な直角三角形の辺の比（中学数学相似と三平方の定理）
弧度法と単位円による三角関数（数学II 三角関数）
$sin x / x$ の極限（数学III 極限）
加法定理と 2 倍角・半角・積和の公式（数学II 三角関数）
三角関数の導関数（数学III 微分法）
根号の乗除と加減（中学数学数と式）
指数の拡張と指数関数（数学II 指数関数と対数関数）
対数の定義と性質（数学II 指数関数と対数関数）
自然対数の底 $e$ （数学III 極限）
指数関数・対数関数の導関数（数学III 微分法）
基本的な関数の不定積分（数学III 積分法）
置換積分（数学III 積分法）
部分積分（数学III 積分法）
定積分の計算（数学II 微分法と積分法）
定積分の置換・部分積分と偶関数・奇関数（数学III 積分法）
重積分と累次積分（大学数学微分積分）
同時分布・周辺分布と独立性（大学数学確率・統計）
条件付き分布と全期待値の公式（大学数学確率・統計）
到達確率と平均到達時間（大学数学確率・統計）

説明

単純ランダムウォーク $S_{0} = 0, S_{k} = X_{1} + \dots + X_{k}$ （ $X_{i}$ は独立で $P (X_{i} = 1) = P (X_{i} = - 1) = \frac{1}{2}$ ）の動きを、折れ線の「経路」として数えて確率を求める技能です。反射原理を使うと、正の整数 $a$ について「 $n$ ステップ以内に高さ $a$ に到達する確率」や、最大値 $M_{n} = max_{0 \leq k \leq n} S_{k}$ の分布を、終点 $S_{n}$ の分布だけで表せます。一段解析では時間制限のない到達確率を求めましたが、反射原理では「 $n$ 歩以内」という有限時間の到達を正確に数えられます。

なぜそうしてよいのか

長さ $n$ の経路（各ステップが $+ 1$ か $- 1$ の列）は全部で $2^{n}$ 本あり、どれも確率 $2^{- n}$ で等しく起こります。したがって確率の計算は経路の本数を数えることに帰着します。終点が $b$ の経路は、上りの歩数 $u$ と下りの歩数 $d$ が $u + d = n, u - d = b$ を満たすので $u = \frac{n + b}{2}$ となり、本数は $N_{n} (b) = (( n + b ) /2 n)$ です（ $b$ が整数で $n + b$ が偶数かつ $∣ b ∣ \leq n$ のとき。それ以外は $0$ ）。

正の整数 $a$ を固定し、 $τ = min {k : S_{k} = a}$ （最初に $a$ に着く時刻）とします。 $τ \leq n$ かつ終点 $S_{n} = b < a$ である経路に対し、時刻 $τ$ より後のステップの符号をすべて反転させた経路を作ります。すると時刻 $τ$ 以降の位置は $S_{k} \mapsto 2 a - S_{k}$ と直線 $y = a$ に関して折り返され、終点は $2 a - b > a$ になります。逆に、終点が整数 $c > a$ の経路は、位置が常に整数で $\pm 1$ ずつしか動かず $0 < a < c$ なので、整数 $a$ を飛び越せず必ず途中で $a$ に止まります（ $τ \leq n$ ）。同じ操作をもう一度施すと元に戻り、折り返しの前後で最初に $a$ に着く時刻 $τ$ は変わらないので、この操作は 1 対 1 の対応です。よって
$# {τ \leq n, S_{n} = b} = N_{n} (2 a - b) (b < a)$
が成り立ちます。

一方、終点が $b \geq a$ の経路も同じ理由ですべて $a$ を通るので、そのまま全部数えます。 $a$ が整数なので $M_{n} \geq a$ と $τ \leq n$ は同じ事象であり、合わせて
$P (M_{n} \geq a) = P (S_{n} \geq a) + P (S_{n} > a) = 2 P (S_{n} > a) + P (S_{n} = a) (a は正の整数)$
が得られます。第1項は「終点が $a$ 以上」の経路、第2項は「終点が $a$ 未満で $a$ に触れた」経路を反射して数えたものです。 $a$ が整数でないと位置 $a$ に「止まる」ことがなく、この議論も公式も成り立ちません（例： $n = 1, a = \frac{1}{2}$ では $P (M_{1} \geq \frac{1}{2}) = \frac{1}{2}$ だが右辺は $1$ ）。

手順

経路として数える準備をする：全経路は $2^{n}$ 本で等確率。終点 $b$ の経路数は $N_{n} (b) = (( n + b ) /2 n)$ （ $n + b$ が奇数や $∣ b ∣ > n$ なら $0$ ）。
高さ $a$ が正の整数であることを確認する（整数でなければ $M_{n} \geq a ⟺ M_{n} \geq ⌈ a ⌉$ と整数に直す）。求める事象を「整数 $a > 0$ に $n$ 歩以内で触れる」 $⟺ M_{n} \geq a$ と言い換え、終点 $b$ で場合分けする。
終点 $b \geq a$ の経路は必ず $a$ を通るので、 $N_{n} (b)$ をそのまま数える。
終点 $b < a$ で $a$ に触れた経路は、最初に $a$ に着いた後を折り返して、終点 $2 a - b$ の経路と 1 対 1 に対応させ、 $N_{n} (2 a - b)$ 本と数える。
合計して $2^{n}$ で割る。まとめると、正の整数 $a$ に対して $P (M_{n} \geq a) = 2 P (S_{n} > a) + P (S_{n} = a)$ 。

例題

単純対称ランダムウォーク $S_{0} = 0, S_{k} = X_{1} + \dots + X_{k}$ （ $X_{i}$ は独立で $P (X_{i} = \pm 1) = \frac{1}{2}$ ）について、 $M_{6} = max_{0 \leq k \leq 6} S_{k}$ とする。 $P (M_{6} \geq 2)$ を求めよ。

例題の解答

手順1：全経路は $2^{6} = 64$ 本。 $n = 6$ なので終点 $b$ は偶数で、 $N_{6} (b) = (( 6 + b ) /2 6)$ 。具体的には $N_{6} (0) = 20, N_{6} (\pm 2) = 15, N_{6} (\pm 4) = 6, N_{6} (\pm 6) = 1$ 。
手順2： $a = 2$ は正の整数。 $M_{6} \geq 2$ は「6 歩以内に高さ $2$ に触れる」こと。終点 $b$ で場合分けする。
手順3：終点 $b \geq 2$ （ $b = 2, 4, 6$ ）の経路はすべて $2$ を通るので $15 + 6 + 1 = 22$ 本。
手順4：終点 $b < 2$ で $2$ に触れた経路は、終点 $2 a - b = 4 - b$ の経路と対応する。 $b = 0 \to 4$ で $6$ 本、 $b = - 2 \to 6$ で $1$ 本、 $b = - 4 \to 8, b = - 6 \to 10$ は $∣4 - b ∣ > 6$ なので $0$ 本。合計 $7$ 本。
手順5： $22 + 7 = 29$ 本なので $P (M_{6} \geq 2) = \frac{29}{64}$ 。公式 $2 P (S_{6} > 2) + P (S_{6} = 2) = 2 \cdot \frac{7}{64} + \frac{15}{64} = \frac{29}{64}$ とも一致する。（検算：余事象は $P (S_{6} < 2) - P (S_{6} > 2) = \frac{42}{64} - \frac{7}{64} = \frac{35}{64}$ で、 $29 + 35 = 64$ 。）

答え: $\frac{29}{64}$

よくある誤り

$P (M_{n} \geq a) = 2 P (S_{n} \geq a)$ としてしまう誤り。終点がちょうど $a$ の経路は反射しても終点が $a$ のままで、反射の相手は $a$ より大きい終点だけです。正しくは $P (M_{n} \geq a) = 2 P (S_{n} > a) + P (S_{n} = a)$ 。例題では $2 \cdot \frac{22}{64} = \frac{44}{64}$ ではなく $\frac{29}{64}$ 。
最初に $a$ に着いた時刻 $τ$ ではなく、経路全体や最後に $a$ にいた時刻以降などを折り返してしまう誤り。全体を折り返すと始点が $0$ から $2 a$ に移り、別の時刻で折り返すと 1 対 1 にならないことがあります。正しくは $k \geq τ$ の部分だけを $S_{k} \mapsto 2 a - S_{k}$ と折り返し、反射後の終点は $2 a - b$ 。
整数でない高さ $a$ にそのまま公式を使う誤り。ウォークは整数の位置にしか止まらないので、たとえば $n = 1, a = \frac{1}{2}$ で $2 P (S_{1} > \frac{1}{2}) + P (S_{1} = \frac{1}{2}) = 1$ としてしまいますが、正しくは $P (M_{1} \geq \frac{1}{2}) = P (M_{1} \geq 1) = \frac{1}{2}$ 。整数でない $a$ は $⌈ a ⌉$ に直してから使います。あわせて偶奇にも注意し、 $n + b$ が奇数なら $N_{n} (b) = 0$ （ $(2.5 6)$ のような式は無意味）、 $∣2 a - b ∣ > n$ なら反射先も $0$ 本です。
非対称なウォーク（ $P (X_{i} = 1) = p \neq = \frac{1}{2}$ ）にも $P (M_{n} \geq a) = 2 P (S_{n} > a) + P (S_{n} = a)$ を使ってしまう誤り。経路の本数の対応はそのまま成り立ちますが、終点 $b$ の経路 1 本の確率は $p^{(n + b) /2} (1 - p)^{(n - b) /2}$ で終点ごとに異なり、反射で確率が変わります。経路の本数を数えてから、終点 $b$ ごとにこの重みを掛けて足す必要があります。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

この技能の次に学べること

ブラウン運動（大学院数学確率論）