問題
6人が円陣を作ってすわり，次のゲームをする；
(i) 最初，交互に赤と白の帽子をかぶり，隣り合う2人ずつの3つの組を作る．各組でジャンケンをし，負けた人は勝った人と同色の帽子をかぶる．
(ii) 6人が同色の帽子にならない場合，隣り合う異なる色の帽子をかぶった2人ずつが組を作り，各組でジャンケンをし，負けた人は勝った人と同色の帽子をかぶる．(両隣りが自分と同色の帽子の人はジャンケンをしない．)
(iii) ゲームは，6人の帽子が同色になれば終了とし，それまで何回か(ii)を繰り返す．
このとき，回までにゲームが終了する確率を求めよ．ただし，ジャンケンでは一方が勝つ確率はで勝負がつくものとする．
方針
6人を個人ごとに追うのではなく、同色が連続するブロックで状態を圧縮する。初回後は3つの2人組の色だけを見ればよく、終了しなければ必ず 人連続と 人連続の状態になる。この状態から次の回で終了する確率が常に で、終了しなければ同じ型に戻ることを示す。
解答
最初の回では、あらかじめ作った3つの隣接ペアがそれぞれジャンケンをする。各ペアは、勝った人の色にそろうので、回の後には各ペアが赤または白の同色2人組になる。各ペアが赤になる確率、白になる確率はいずれも であり、3組について独立に考えられる。
3組がすべて赤、またはすべて白になれば、6人全員が同色となって終了する。その確率は である。逆に1回で終了しないとき、3つの2人組の色は全て同じではない。2色しかないので、ある色の2人組が1つ、もう一方の色の2人組が2つである。円周上では後者の2組がつながって見えるため、帽子の並びは という型になる。
この型の状態を考える。異なる色が隣り合う境目は2か所だけなので、次の回に行われるジャンケンはその2か所である。2人連続の色の側にいる2人が、どちらの境目でも負けると、その2人が相手の色に変わり、6人全員が同色になって終了する。この確率は である。それ以外の場合は、2人連続の色が残るか、または反対の色が2人連続として残るだけで、やはり の型に戻る。したがって、まだ終了していない状態から次の1回で終了しない確率は常に である。
初回についても、終了しない確率は である。よって 回までに終了しない確率は である。したがって、求める確率は である。
別解。
状態を :「未終了で、2人連続と4人連続の型」とおく。初回後に終了する確率は 、状態 に入る確率は である。また からは、1回ごとに確率 で終了し、確率 で再び に戻る。したがって未終了確率は各回ごとに 倍されるので、 回後の未終了確率は であり、同じ答えを得る。