ランダムウォークで正側x0を歩いている時間の式の証明

[] [] []


前々項で保留にした、t=0からt=2nまでの間に正側x0を歩いている時間が2kである確率

であることを証明する。

証明のあらすじは、

ちょうどt=2nに原点x=0にいる確率をu2nt=2nに初めて原点に戻る確率をf2nとおくと

(1) t=0からt=2n-2までの間ずっと正側x0を歩いてt=2n-1で初めてx=-1にいる確率はf2nに等しい

(2) t=0からt=2nまでの間ずっと正側x0を歩く確率はu2nに等しい

(3) t=0からt=2nまでの間に正側x0を歩いている時間が2kである確率p2k,2nu2k u2n-2kに等しいことを数学的帰納法で示す

(1) t=0からt=2n-2までの間ずっと正側x0を歩いてt=2n-1で初めてx=-1にいる確率はf2nに等しい

なぜならば

(1-1) (t=0,x=0)から点(t=2n,x=0)まで正側x0または負側x0のいずれかだけを歩く経路はf2n*22n

(1-2) (t=0,x=0)から点(t=2n,x=0)まで正側x0だけを歩く経路は(1-1)の半分だからf2n*22n-1

(1-3) (t=1,x=1)から点(t=2n-1,x=1)までx1だけを歩く経路は(1-2)と同数だからf2n*22n-1

(1-4) (t=0,x=0)から点(t=2n-2,x=0)までx0だけを歩く経路は(1-3)と同数だからf2n*22n-1

(1-5) (t=0,x=0)から点(t=2n-2,x=0)までx0だけを歩き、最後に点(t=2n-1,x=-1)に至る経路は(1-4)と同数だからf2n*22n-1

(1-6) (1-5)を全経路の数22n-1個で割れば求める値になるから f2nに等しいことが示せた

◇◇

(2) t=0からt=2nまでの間ずっと正側x0を歩く確率はu2nに等しい

この事象は、t=1からt=2n-1までのいずれかの時間にx=-1に至ることの排反事象である。t=2m-1(m=1,...n)x=-1に至る確率は上記(1)からf2mであるから、求める確率は

ここで前項で導いた次の恒等式

を使うと

u2nに等しいことが示せた。

◇◇◇

(3) t=0からt=2nまでの間に正側x0を歩いている時間が2kである確率p2k,2nu2ku2n-2kに等しいことを数学的帰納法で示す

(i) k=nのとき

上記(2)よりt=0からt=2nまでの間ずっと正側x0を歩く確率はu2nで、またu0=1から

が成り立っている。

(ii) k=0のとき

t=0からt=2nまでの間ずっと負側x0にいる確率はずっと正側x0を歩く確率と同じu2nで、またu0=1から

が成り立っている。

(iii) 1kn-1のとき

このときは必ずx=0をまたぐときがあるので、初めてx=0に戻って来た時間をt=2rとおき、ここを節目にして次の2つの場合に分けて考える。

1は、t=0からt=2rまではずっと正側x0を歩き、t=2rからt=2nまでのうち残りの時間(2k-2r)だけ正側x0を歩く場合である。この場合の経路の数は

なぜならば、t=0からt=2rまでの時間(2r)ずっと正側x0にいる経路はf2r*22r個の半分、t=2rからt=2nまでの時間(2n-2r)のうち時間(2k-2r)だけ正側x0にいる経路はp2k-2r,2n-2r*22n-2r個。

2は、t=0からt=2rまではずっと負側x0を歩き、t=2rからt=2nまでのうち時間(2k)だけ正側x0を歩く場合である。この場合の経路の数は

なぜならば、t=0からt=2rまでの時間(2r)ずっと負側x0を歩く経路はf2r*22r個の半分、t=2rからt=2nまでの時間(2n-2r)のうち時間(2k)だけ正側x0を歩く経路p2k,2n-2r*22n-2r個。

これら2つの場合の経路数の和を全経路数22nで割ったものは確率p2k,2nに等しいから、次の漸化式が得られる。

この漸化式を使って、数学的帰納法で次式が成り立つことを示す。

n=1のとき、k=0,1だから上記(i)(ii)によりこの式は成り立つ。

1からn-1までこの式が成り立つと仮定すると漸化式より

ここでfuのたたみ込みは次式のように簡単になる。

なぜならばt=2nに原点x=0にいる確率は、t=2rに初めて原点に戻り、残りの時間(2n-2r)後に原点にいるケースに分割できるからである。(→補足- n回目に初めて事象が起きる確率)

したがって

nのときも成り立つことが示せた。

◇◇◇◇

結局t=0からt=2nまでの間に正側にいる時間が2kである確率p2k,2n

であることが示せた。


[] [] []