ランダムウォーク - あやめだが

数直線上にpy(仮名)が0秒の時点で $x=5$ に立っていたとします。

pyさんは1秒経つ毎に、-1か+1進みます。酔っているのか、この移動は確率的に行われるものとします。また、秒数や位置には寄らず独立に行われるとします。

x=0には、警察署があり、ここに到着すると捕まり、終了します。

x=10には、自宅があり、ここに到着すると終了します。

py氏がいずれ家に到着する確率を求めましょう。

シミュレーション

p=0.6で10回

f:id:ayamedaga:20160930030834p:plain

p=0.8

f:id:ayamedaga:20160930030951p:plain

というわけで、p=0.6で9割、p=0.8で10割で帰宅できています。

これは有名なランダムウォークの一番初歩的な問題です。

計算

$p_x$ を $x$ のときに帰宅できる確率としましょう。

条件から以下のような漸化式を得ます。

$p_x=p p_{x+1}+(1-p) p_{x-1}, x=2,\ldots,8$

これは $x=1,9$ でも成立することが分かります。上式から、

$(1-p)(p_x-p_{x-1})=p(p_{x+1}-p_{x})$

を得ます。ここから、漸化式を解いて、

$p_{x}=p_1 \frac{p}{2p-1}\{1-((1-p)/p)^x\}$

です。あとは $p_1$ を求めましょう。これは $p_{10}=1$ を用います。

$p_1=\frac{2p-1}{p}\frac{1}{1-\frac{1-p}{p}^{10}}$

あとは代入して、

$p_5=\frac{1-\frac{1-p}{p}^5}{1-\frac{1-p}{p}^{10}}$

これで、問題は解けました。

グラフにすると、

f:id:ayamedaga:20160930034645p:plain

というわけで、理論値ではp=0.6で0.883636、p=0.9で0.999983ということで結構妥当なシミュレーション結果だったことが分かりました。