立ち止まるランダムウォーク

投稿者: | 2017年6月22日

概要

  • 静止を含むランダムウォークを考える
  • n 回の試行である位置 x にいる確率を求める

静止を含むランダムウォーク

通常のランダムウォークは右か左のどちらかに確率的に進みますが、 ここでは、右、左に加えてその場に静止する場合も含めたランダムウォークを考えます。

右に進む確率を \(p\)、左に進む確率を \(q\) として、 静止する確率は \(1-p-q\) となります。

次のような確率変数 \(X_i\) を用いて、 \[
X_i = \begin{cases}
-1 & {\rm with\ \ } q \\
0 & {\rm with\ \ } 1-p-q \\
1 & {\rm with\ \ } p
\end{cases}
\]
\(n\) 回の試行で到達した位置は \[
S_n = \sum_{i=1}^{n} X_i
\]
で表されます。

特定の位置に移る確率

それでは、\(n\) 回目の試行で位置 \(x\) に移る確率 \(P(S_n = x)\) を求めてみましょう。 当然、通常のランダムウォークと似ているので、通常のランダムウォークの結果を上手く利用する方法が良さそうです。 そのために、どこが違っているのかを明確にして、 どうすれば通常のランダムウォークと同じ部分を見つけられるかを考える必要があるので、 そのような方針に則って計算を進めていきます。

○通常のランダムウォークとの違い

右に進んだ回数を \(n_R\)、左に進んだ回数を \(n_L\)、静止した回数を \(n_S\) とすると、 回数の総和から、 \[
n = n_R + n_L + n_S \tag{1}\label{num}
\]
が成り立ちます。

また、位置 \(x\) は、進んだ歩数から戻った歩数を引けばよいので、 \[
s = n_R – n_L \tag{2}\label{pos}
\]
も成り立ちます。

もし、\(n_S=0\) であれば、式 \(\eqref{num},\eqref{pos}\) から \[
n_R = \frac{n+x}{2} \\
n_L = \frac{n-x}{2} \tag{3} \label{Nrl}
\]
であることが直ちに分かります。 これは、普通のランダムウォークと同じです。

この式が表しているのは、例えば、5 歩進んで、3 の位置にいるなら、 右に 4 歩、左に 1 歩進んだと分かるということです。

ところが、静止が入ってくる場合、右に 3 歩進んで、2 回は静止したとしても、 最終的に 3 の位置にいます

つまり、\(n,x\) が決まっても、 \(n_R, n_L, n_S\) が一意に定まらないことに注意しなければいけません。

○通常のランダムウォークへの帰着

\(n_R, n_L, n_S\) が定まらないのは、静止が入ったせいなので、 静止した回数を固定してしまえば残りの \(n_R,n_L\) が決まるはずです。

例えば、\(n_S=0\) は通常の \(n\) 歩進むランダムウォークで、 \(n_S = 1\) は右か左に \(n-1\) 歩進むランダムウォークになります。 同様に、\(n_S = i\)\(n-i\) 歩進むランダムウォークと同じです。

このことから、静止のない通常のランダムウォークが、 \(n\) 歩で到達する位置を \(S’_n\) とすると、 \(S_n = x\) であるのは、“\(n_S = 0\) かつ \(S’_n = x\)” または、“\(n_S = 1\) かつ \(S’_{n-1} = x\)” または、・・・。 のように、通常のランダムウォークを使って表現できます。 従って、\(S_n=x\)である確率は、 \[
P(S_n=x) = \sum_i P(n_S=i \wedge S’_{n-i}=x) \tag{4} \label{main}
\]
と求めることができます。

通常のランダムウォークで \(n\) 歩進んで位置 \(x\) にいる時の、 左右に進んだ数は式 \(\eqref{Nrl}\) で表されるので、 \(n_R, n_L, n_S\) の数に注目すれば、 \[
P(S_n = x) = \sum_i P(n_S = i \wedge n_R = \frac{n-i+x}{2} \wedge n_L = \frac{n-i-x}{2}) \tag{5} \label{main_n}
\]
と表せます。

○確率の計算

\(\eqref{main_n}\) の第 \(i\) 項は、確率 \(p,q,1-p-q\) で生じる3つの事象の生じた回数についての分布なので三項分布に従います。 従って、 \[
P(S_n = x) = \sum_i \frac{n!}{i!(\frac{n-i+x}{2})!(\frac{n-i-x}{2})!} (1-p-q)^ip^\frac{n-i+x}{2}q^\frac{n-i-x}{2} \tag{6} \label{pos_p}
\]
となります。 ただし、和は \(i,\frac{n-i+x}{2},\frac{n-i-x}{2}\) が 0 以上の整数、すなわち、回数としてちゃんと定義出来る場合に制限されるものとします。

グラフ

○計算結果の妥当性

確率が式\(\eqref{pos_p}\) で表されることがわかったので、 実際に静止を含むランダムウォークをシミュレーションで動かしてみて計算結果と一致するかを確かめてみます。

下に、\(p=0.3, q=0.1, n=10\) の時のシミュレーションと計算結果をグラフに表示します。

グラフの横軸は位置を表しており、\(n=10\) 回進んだ後に位置 \(x\) に到達する確率を縦軸に示しています。 赤の線が式\(\eqref{pos_p}\) の具体的な数値で、青丸は 100,000 通りのランダムウォークの結果を表しています。 きれいに一致しているところから、計算式はどうやら正しそうです。

○静止のないランダムウォークとの比較

\(\eqref{pos_p}\) は、\(p+q=1\) の時には静止を含まない普通のランダムウォークの結果を表します。 そこで、静止を含む場合と含まない場合で、どのように位置の分布が変わってくるのかを見てみたいと思います。

静止を含むランダムウォークを先程と同様に \(p=0.3,q=0.1, n=10\) とします。 静止を含まないランダムウォークのパラメータ\(p’,q’,n’\) はどのように設定すればうまく比較できるでしょうか。

今、\(p = 3q\) なので、右の方に三倍進みやすい状況にあります。 これを保つように、静止を含まないランダムウォーク \(p’+q’=1\) にするには、\(p’=0.75,q’=0.25\) に設定すれば良いことが分かります。 また、\(n=10\) のうち右か左に動くのは、\(p+q = 0.4\) より、4 回程度なので、\(n’=4\) に設定すれば良さそうです。

上のグラフに、静止を含まない通常のランダムウォ―ク(RL)と静止を含んだランダムウォーク(SRL)の結果を示します。

一番の違いは、通常のランダムウォークは分布がぎざぎざしているということです。 これは、毎ステップで右か左のどちらかに必ず進まなければならないためです。 この場合、偶数ステップの時には奇数の位置には到達できず、奇数ステップの時には偶数の位置に到達できません。 その結果、\(n’=4\) のグラフでは、奇数の位置の確率が 0 になっています。 逆に、静止を含む場合は、\(n\) が偶数であっても、静止を挟むことで、奇数の位置に到達することができます。

○歩数と分布の広がり

最後に、歩数を増やしていった時の位置の分布の広がりを見てみましょう。 下では、左右への進みやすさが対称な \(p=q=0.1\) として、歩数を 1~20 に変えた時の位置の分布をグラフで示しています。

歩数を増やしていくにつれて、徐々にピークが丸まり、ベル型の分布、 正規分布に近づいていっている様子が分かります。 静止した回を無視すれば、通常のランダムウォークと同じなので、 対称なランダムウォークが正規分布に近づいていくのと同じように理解できます。 ただし、通常のランダムウォークだと分布はいつまでもギザギザなので、 むしろ、こちらの静止を含んだ方が正規分布に近づく様子がきれいに見えます。

関数定義


 

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です