方針
とおく。初めてに戻るまでは,との間だけを往復する必要があるため,最初にへ行く場合とへ行く場合に分けて確率を掛ける。(3)ではのときとなることを使い,最初の戻り時刻と二度目の戻り時刻の間隔を足し合わせる。
解答
(1)
とおく。回目に初めてに戻るのはの場合であるからである。回目に初めてに戻るのはの場合であるからである。
(2)
最初にへ移動した場合,へ戻らないためには,戻る直前までと移動するしかない。最初にへ移動した場合も同様である。
回目に初めて戻る場合は,最初にへ行く経路の確率が,最初にへ行く経路の確率もである。よってである。
回目に初めて戻る場合は,最初にへ行く経路の確率が,最初にへ行く経路の確率がである。よってである。
(3)
のとき,(1),(2)よりすべてのについてである。二度目にへ戻る時刻がであるとする。最初に戻る時刻をとすると,であり,二度目までの間隔はである。したがってである。各項はであり,項数は個であるからである。
別解
解法2
方針
Aへの初帰還を更新過程として扱い,帰還間隔の分布を経路の交互性から求める。(3)は2つの独立な帰還間隔の畳み込みで数える。
解答
とする。
(1)(2) 初帰還まではB,Cを交互に通る。長さ の2経路は各 ,長さ の2経路はそれぞれ 。よって(3) では 。2度目の帰還時刻が となる確率は
総評
難度7,計算量6。想定時間は22分程度。初めて戻る条件を,との強制的な往復として捉えることが核心である。(3)は一度に戻ると同じ状況から再開するため,戻り時刻の分割和にできる。偶奇による経路の終点を取り違えないように整理したい。