Aritalab:Lecture/NetworkBiology/Random Walk/Reflection

反射壁と吸収壁

ここでは1次元のランダムウォークで、左右対称な場合 p = q = 1/2 を考えます。 ある位置 k^* にきたら次のステップは確率 1 で k^* − 1 に移動する場合、 k^* を反射壁と呼びます。 反射壁があるときは、壁が無いとみなしてランダムウォークをしたあとに壁を折り返して一致する鏡像点の確率を足したものになります。 ウォーク後の位置を k とするとき、 k^* の k に対する鏡像点は 2 k^* − k なので、以下のようになります。

ある位置 k^* にきたら次のステップ以降は移動できなくなる場合、 k^* を吸収壁と呼びます。 吸収壁があるときは、壁がないとみなしてランダムウォークをしたあとに壁を折り返して一致する鏡像点の確率を引いたものになります。

• 壁がないとき、n ステップ後に位置 k に至る経路数は $\textstyle P(k,n) = \binom{n}{(n+k)/2} = \frac{n!}{(\frac{n - k}{2}) ! (\frac{n + k}{2}) !}$
• 反射壁があるとき、n ステップ後に位置 k に至る経路数は $P(k, n; k^*) = P(k, n) + P(2k^* - k, n) \,$
• 吸収壁があるとき、n ステップ後に位置 k に至る経路数は $P(k, n; k^*) = P(k, n) - P(2k^* - k, n) \,$

マイナスの値をとらない経路の数

マイナスの値をとらないことは、−1 の位置に吸収壁があることに相当します。たとえば 2 n ステップ後に原点に戻るウォークで 0 以上の部分だけを通る経路数は

$\textstyle \binom{2n}{n} - \binom{2n}{n-1} = \frac{1}{n+1} \binom{2n}{n}$

となり、カタラン数に一致します。

n ステップ後に初めて吸収壁 k に到達する経路の数

n ステップ後に k にいる経路の総数は $\binom{n}{\frac{n+k}{2}}$ ですが、この中には k + 1 を経由するものが含まれます。 1 ステップ前の状態を考えると、位置は k - 1 か、k + 1 です。k + 1 に至る経路の総数は $\binom{n-1}{\frac{n+k}{2}}$ で、k - 1 に至る経路のうち反射壁を通るものの総数も鏡像の原理から $\binom{n-1}{\frac{n+k}{2}}$ と等しくなります。 よって求める経路数は

$\binom{n}{\frac{n+k}{2}} - 2 \binom{n-1}{\frac{n+k}{2}} = \frac{k}{n} \binom{n}{\frac{n+k}{2}}$

となります。つまり、初めて k に初めて到達する経路数は通常のランダムウォークを k/n 倍すればよいだけです。

ギャンブラーの破産問題

コインを i 枚持つギャンブラーが確率 p で表の出るコインを投げ、表がならコインを 1 枚受け取り、裏なら 1 枚失います。コインを全て失う前に n 枚に増える確率を考えましょう。

これは確率 p − 1, p で左右にそれぞれ 1 移動し、位置 0 と n を吸収壁とみなしたランダムウォークです。位置 0 が破産、位置 n を勝ちとみなして、位置 i における勝率を考えます。

勝率が満たす漸化式は

$P(i) = p P(i-1) + (1-p) P(i+1)\,$

です。 $P(i)\,$を求めましょう。

p = 1/2 のとき

左右に公正に移動するウォークなので、漸化式を満たす$P(i)\,$として等差数列 $\,ai + b$ を仮定できます。境界条件$P(0) = 0\,$, $P(n) = 1\,$から $P(i) = i/n\,$ です。

p ≠ 1/2 のとき

左右に移動するたびに $p/(1-p)\,$倍に勝率が変わるウォークなので、漸化式から$P(i)\,$が等比数列 $\,ak^i + b$ と予測できます。これを漸化式に代入しましょう。

$\begin{align} k^i &= p k^{i-1} + (1-p)k^{i+1}\\ k &= p + (1-p) k^2 \end{align}$

これを解いて $\textstyle k = 1,\quad k = \frac{p}{1-p}$。このうち前者は p = 1/2 に対応するので除外します。境界条件$P(0) = 0\,$, $P(n) = 1\,$から $P(i) = a k^i+b\,$ の係数 a, b を求めると $\textstyle P(i) = \frac{k^i - 1}{k^n - 1}$

となります。

• p = 1/2 のとき $P(i) = i/n\,$ （勝率は開始時の所持金に正比例）
• p ≠ 1/2 のとき $\textstyle P(i) = \frac{k^i - 1}{k^n - 1}\ (k = \frac{p}{1-p})$ （勝率は k の値が 1 を少しでも上回れば 1 に大きく近づく）