問題
図のように円周上に4点，，，がある．ある粒子はこの円周上を点を出発して，時計回りに確率でとなりの点に，反時計回りに確率でとなりの点に移動する．
% 図は省略
(1) この粒子が4回の移動までに，，すべての点を訪問する確率を求めよ．
(2) この粒子が回の移動までにを訪問しない確率を求めよ．
方針
円周上に時計回りで並ぶ点を順に 0,1,2,3 と見て、時計回りを一歩進む操作、反時計回りを一歩戻る操作として扱う。(1)は4回の移動列のうち、途中で 1,2,3 のすべてを通るものを列挙して、それぞれの確率を足す。(2)は「まだ C に着かない」ための動きを奇数回後・偶数回後に分け、2回を1組にした漸化的な確率で求める。
解答
(1)
円周上に時計回りに がこの順に並ぶとし、時計回りの移動を 、反時計回りの移動を と表す。4回までに のすべてを訪問するには、出発点 から見た位置が途中で のすべてを含めばよい。
そのような4回の移動列は である。たとえば では と進むので3点すべてを訪問する。各列の確率を足すと
である。したがって求める確率は である。
(2)
を訪問しない間、粒子は のいずれかにしかいない。まず1回目に へ行かないためには、必ず と時計回りに進む必要があるから、その確率は である。
奇数回の移動後にまだ を訪問していないとき、粒子は必ず にいる。実際、 から2回後に再び に戻り、かつ途中で を訪問しない動きは の2通りであり、それぞれの確率は である。したがって、奇数回後から次の奇数回後まで、条件を保つ確率は である。 回まで を訪問しない確率を とすると だから である。また、奇数回後に条件を満たしていればその位置は であり、次の1回は または に進むだけなので には到達しない。したがって 回まで訪問しない確率も同じである。
よって
である。