ランダムウォークで正側x≧0を歩いている時間の式の証明
前々項で保留にした、t=0からt=2nまでの間に正側x≧0を歩いている時間が2kである確率が
であることを証明する。
証明のあらすじは、
ちょうどt=2nに原点x=0にいる確率をu2n、t=2nに初めて原点に戻る確率をf2nとおくと
(1) t=0からt=2n-2までの間ずっと正側x≧0を歩いてt=2n-1で初めてx=-1にいる確率はf2nに等しい
(2) t=0からt=2nまでの間ずっと正側x≧0を歩く確率はu2nに等しい
(3) t=0からt=2nまでの間に正側x≧0を歩いている時間が2kである確率p2k,2nはu2k u2n-2kに等しいことを数学的帰納法で示す
◇
(1) t=0からt=2n-2までの間ずっと正側x≧0を歩いてt=2n-1で初めてx=-1にいる確率はf2nに等しい
なぜならば
(1-1) 点(t=0,x=0)から点(t=2n,x=0)まで正側x＞0または負側x＜0のいずれかだけを歩く経路はf2n*22n個
(1-2) 点(t=0,x=0)から点(t=2n,x=0)まで正側x＞0だけを歩く経路は(1-1)の半分だからf2n*22n-1個
(1-3) 点(t=1,x=1)から点(t=2n-1,x=1)までx≧1だけを歩く経路は(1-2)と同数だからf2n*22n-1個
(1-4) 点(t=0,x=0)から点(t=2n-2,x=0)までx≧0だけを歩く経路は(1-3)と同数だからf2n*22n-1個
(1-5) 点(t=0,x=0)から点(t=2n-2,x=0)までx≧0だけを歩き、最後に点(t=2n-1,x=-1)に至る経路は(1-4)と同数だからf2n*22n-1個
(1-6) (1-5)を全経路の数22n-1個で割れば求める値になるから f2nに等しいことが示せた
◇◇
(2) t=0からt=2nまでの間ずっと正側x≧0を歩く確率はu2nに等しい
この事象は、t=1からt=2n-1までのいずれかの時間にx=-1に至ることの排反事象である。t=2m-1(m=1,...n)でx=-1に至る確率は上記(1)からf2mであるから、求める確率は
ここで前項で導いた次の恒等式
を使うと
とu2nに等しいことが示せた。
◇◇◇
(3) t=0からt=2nまでの間に正側x≧0を歩いている時間が2kである確率p2k,2nがu2ku2n-2kに等しいことを数学的帰納法で示す
(i) k=nのとき
上記(2)よりt=0からt=2nまでの間ずっと正側x≧0を歩く確率はu2nで、またu0=1だから
が成り立っている。
(ii) k=0のとき
t=0からt=2nまでの間ずっと負側x≦0にいる確率はずっと正側x≧0を歩く確率と同じu2nで、またu0=1だから
が成り立っている。
(iii) 1≦k≦n-1のとき
このときは必ずx=0をまたぐときがあるので、初めてx=0に戻って来た時間をt=2rとおき、ここを節目にして次の2つの場合に分けて考える。
第1は、t=0からt=2rまではずっと正側x≧0を歩き、t=2rからt=2nまでのうち残りの時間(2k-2r)だけ正側x≧0を歩く場合である。この場合の経路の数は
なぜならば、t=0からt=2rまでの時間(2r)ずっと正側x≧0にいる経路はf2r*22r個の半分、t=2rからt=2nまでの時間(2n-2r)のうち時間(2k-2r)だけ正側x≧0にいる経路はp2k-2r,2n-2r*22n-2r個。
第2は、t=0からt=2rまではずっと負側x≦0を歩き、t=2rからt=2nまでのうち時間(2k)だけ正側x≧0を歩く場合である。この場合の経路の数は
なぜならば、t=0からt=2rまでの時間(2r)ずっと負側x≦0を歩く経路はf2r*22r個の半分、t=2rからt=2nまでの時間(2n-2r)のうち時間(2k)だけ正側x≧0を歩く経路はp2k,2n-2r*22n-2r個。
これら2つの場合の経路数の和を全経路数22nで割ったものは確率p2k,2nに等しいから、次の漸化式が得られる。
この漸化式を使って、数学的帰納法で次式が成り立つことを示す。
n=1のとき、k=0,1だから上記(i)(ii)によりこの式は成り立つ。
1からn-1までこの式が成り立つと仮定すると漸化式より
ここで、fとuのたたみ込みは次式のように簡単になる。
なぜならば、t=2nに原点x=0にいる確率は、t=2rに初めて原点に戻り、残りの時間(2n-2r)後に原点にいるケースに分割できるからである。（→補足- n回目に初めて事象が起きる確率)
したがって
とnのときも成り立つことが示せた。
◇◇◇◇
結局、t=0からt=2nまでの間に正側にいる時間が2kである確率p2k,2nは
であることが示せた。