問題
下の図のように4地点，，，が4本の道で結ばれている．
動点がを出発して，それら4地点間を次のルールで行き来するものとする．
a) が，，のいずれかにあれば，次のステップで道の本数に応じて隣の地点に移動する．例えばがにあれば，次のステップではに移動する．がにあれば，確率でに，確率でに移動する．
b) がひとたびに移動してきたら，以後にとどまり続け，他には移動しない．
ステップ後に動点が，，，にある確率をそれぞれ，，，とする．次の問に答えよ．
(1) ，，，を求めよ．
(2) が偶数のときであることを示せ．
(3) を求めよ．
方針
本文の例から，道は と の間に1本， と の間に2本， と の間に1本あると読む。まず ，， の確率を整理して から を出す。偶奇については，出発点 から にいる時刻が奇数ステップ後だけであることを帰納的に示す。最後は， に入らない確率が一定のステップ数ごとに減ることを示して と結論する。
解答
(1)
問題文の例より，移動確率は次のように読める。 である。また に入った後は にとどまる。
はじめ は にあるので，1ステップ後は必ず にある。したがって である。2ステップ後は から または へ移るので である。2ステップ後には， に確率 ， に確率 でいる。したがって3ステップ後に にいる確率は である。4ステップ後は，3ステップ後に にいた場合は または へ移り， にいた場合は にとどまるので，いずれにしても にはいない。よって である。以上より である。
(2)
から出発すると，1ステップ後に にいる。 からは次のステップで または へ移り， からは次のステップで または へ移る。ただし に入った後は にとどまり， には戻らない。
したがって， にいる可能性があるのは奇数ステップ後だけである。ゆえに が偶数のとき である。
(3)
に一度入れば以後ずっと にいるので， は とともに減らない。あとは に入らない確率が0に近づくことを示せばよい。 以外のどの地点から出発しても，3ステップ以内に に到達する確率は少なくとも である。実際， からなら の確率が である。 からなら の確率が ， からなら1ステップで に入る確率が であり，いずれも 以上である。
したがって，3ステップごとに，まだ に入っていない確率は高々 倍になる。よって を正の整数として である。右辺は で0に近づく。したがって に入らない確率は0に近づき， である。