問題
図のように，平面上に点およびが並んでいる．点はから出発し，次の規則に従いこれらの点の上を移動する．
がにいるときには1秒後にまたはに，一方にいるときにはまたはに移動する．ただし，前にいた点には戻らない．また，が移動しうる点が複数あるときには，それぞれの点へ等確率で移動する．がへ到る行き方が通り，へ到る行き方が通りあるとする．
(1) ，を求めよ．
(2) ，を求めよ．
(3) 一方，点はからと同時に出発し，1秒ごとに順次と移動し，その後はにとどまる．とが出会う確率を求めよ．
方針
行き方の数では、 に入る直前が である場合と、 と進む場合に分ける。戻れない条件により、 の直前は必ず になる。同様に についても漸化式が立つ。出会う確率は時刻 に が にいることから、可能な時刻が だけに絞られる。時刻4は一直線に進む1通り、時刻5は戻れない条件で確率の異なる6通りを列挙して合計する。
解答
(1)
まず行き方の数を調べる。 に到る最後の部分は、次の2種類に分けられる。
1つは と進む場合である。もう1つは と進む場合であるが、直前の点に戻ることはできないので、この直前は ではなく でなければならない。したがってこの場合の最後の部分は である。よって である。同様に である。
初めに にいるので への行き方は1通りである。また へは の1通りで到るから である。したがって である。よって である。
(2)
上の漸化式で、 である。もし なら である。よって数学的帰納法により である。
(3)
点 は時刻 に にいる。ただし とする。点 は1秒で添字を高々1だけ増やすので、 と が出会うには が必要である。また が にいるには、時刻 までの横方向の移動回数が であり、残りの縦方向の移動回数は である。 側に戻っているためには縦移動回数は偶数である。これらを合わせると、実際に出会える時刻は だけである。
時刻4で出会うには と進むしかない。各時刻で2通りの選択があるので、その確率は である。
時刻5で出会うには にいる必要がある。可能な経路とその確率は次の通りである。
である。確率が になる経路があるのは、途中で直前の点へ戻れず、次の移動が強制される箇所があるためである。したがって時刻5で出会う確率は である。
時刻4と時刻5の出会いは同時には起こらない。よって求める確率は である。