次の様な反射壁のあるランダムウォークについて考える。このランダムウォークは原点からスタートし、コインを投げ表がでれば右へ裏がでれば左へ移動する。
ただし、原点においては裏がでた場合その場にとどまるものとする。（これを原点での反射と呼ぶ）
このとき、Ｋ回の反射があった後、時刻Ｎに状態Ｍへ到達する確率は？
この問題を解くためにまず、Ｋ回の反射があった後、時刻Ｎに状態Ｍへ到達する道の数を調べます。
原点に反射壁のあるランダムウォークにおいて、Ｋ回の反射があったという事を反射壁のないランダムウォークに置き換えると、最小値がＫであるという事
に対応します。
また、Ｋ回の反射後は、時刻Ｎでの反射壁のあるランダムウォークの状態をＰとすると時刻Ｎの反射壁のないランダムウォークの状態はＰ－Ｋです。
この反射壁のあるランダムウォークから反射壁のないランダムウォークへの置き換えは、1対1の対応であるため、
Ｋ回の反射があり時刻Ｎで状態Ｍに至る反射壁のあるランダムウォークの道の数＝最小値がＫであり時刻Ｎに状態Ｍ－Ｋに至る反射壁のないランダムウォークの道の数
となります。
このことは、反射の回数が1回の場合は明らかです。
1対1対応である事も明らかです。そこで、Ｋ回の反射後は、時刻Ｎでの反射壁のあるランダムウォークの状態をＰとすると時刻Ｎの反射壁のないランダムウォークの
状態はＰ－Ｋである事を示します。
Ｋ-1回目までこの対応関係が成り立っていたと仮定します。
時刻ＮまでにＫ回の反射があるランダムウォークが時刻Ｔ＜Ｎで原点にいてＫ回目反射によって時刻Ｔ+1＜Ｎでも原点にいるならば、
反射壁のないランダムウォークの置き換えでは、時刻Ｔ＜Ｎで－Ｋにいて時刻Ｔ+1＜Ｎで－（Ｋ+1）となりＫでも成り立ちます。
最小値がＫであり、時刻Ｎに状態Ｍ－Ｋへ至る道の数は、（－Ｋ）に触れてから時刻Ｎに状態Ｍ－Ｋへ至る道の数から（－Ｋ－1）に触れてから時刻Ｎに
状態Ｍ－Ｋへ至る道の数を引けば求まります。
したがって、この問題の答えは、
となります。ここで、コインの表のでる確率＝コインの裏のでる確率＝1/2の時、時刻2Ｎで反射壁のあるランダムウォークが原点に復帰する確率を求めます。
反射壁のあるランダムウォークが時刻2Ｎに状態Ｍにいるという事象は起こりうる反射回数の最大値をＬとするとｉ回（ｉ＝0～Ｌ）の反射があり状態Ｍ
にいるという場合ごとに分けることができます。
そしてこれに対応する反射壁のないランダムウォークとして、時刻2Ｎに状態Ｍ－ｉにいて、Ｍ－ｉに至るまでの最小値がｉ（ｉ＝0～Ｌ）という場合
に分けることができます。
したがって、コインの表のでる確率＝コインの裏のでる確率＝1/2の時、この問題では、Ｍ＝0 で、全てのｉ＝0～Ｌを足し合わせればよい事
になります。
まず、ｉ＝0の場合、これは（時刻2Ｎで原点に復帰する道の数 ）－（－1に触れてから時刻2Ｎに原点に復帰する道の数）で求まります。
さらに、ｉ＝2の場合、（時刻2Ｎで－2にいる道の数 ）－（－3に触れてから時刻2Ｎに－2にいる道の数）等となります。
状態xからスタートした反射壁のないランダムウォークがＴ時間後に状態yに至る道の総数をT.x→yとし
状態xからスタートした反射壁のないランダムウォークがＴ時間後にｕに触れてから状態yに至る道の総数をｕ/T.x→yと表しｉ＝0～Ｌを足し合わせると
（2Ｎ.0→0）－（－1/2Ｎ.0→0）＋（2Ｎ.0→－2）－（－3/2Ｎ.0→－2）＋・・・＋（2Ｎ.0→－Ｌ＋2）－（－Ｌ＋1/2Ｎ.0→－Ｌ＋2）＋（2Ｎ.0→－Ｌ）
となり（－ｉ＋1/2Ｎ.0→－ｉ＋2）＝（2Ｎ.0→－ｉ）であるから結局、初項のみが残り問題の答えが求まります。
次にコインの表のでる確率＝コインの裏のでる確率＝1/2の時、時刻2Ｎで反射壁のあるランダムウォークが状態Ｍ＝2Ｋ（Ｋ＞0）にいる確率を求めます。
（2Ｎ.0→2ｋ）－（－1/2Ｎ.0→2ｋ）＋（－2/2Ｎ.0→2ｋ-2）－（－3/2Ｎ.0→2ｋ-2）＋・・・
・・・＋（－Ｌ＋2/2Ｎ.0→2ｋ－Ｌ＋2）－（－Ｌ＋1/2Ｎ.0→2ｋ－Ｌ＋2）＋（－Ｌ/2Ｎ.0→2ｋ－Ｌ）
となり（－ｉ＋1/2Ｎ.0→2ｋ－ｉ＋2）＝（－ｉ/2Ｎ.0→2ｋ－ｉ）であるから結局、初項のみが残り問題の答えが求まります。
同様の計算によってＭ＝2Ｋ－1（Ｋ＞0）の場合も求まり、
反射壁のあるランダムウォークが時刻2Ｎで状態2Ｋにいる確率＝反射壁のあるランダムウォークが時刻2Ｎで状態2Ｋ-1にいる確率（Ｋ＝1～Ｎ）
さらに、反射壁のあるランダムウォークが時刻2Ｎ-1で状態2Ｋ-1にいる確率＝反射壁のあるランダムウォークが時刻2Ｎ-1で状態2Ｋ-2にいる確率（Ｋ＝1～Ｎ）
となります。
トップページへ