問題
を3以上の整数とする．個の球と個の空（から）の箱がある．以下のように，の順番に，球を箱に1つずつ入れていく．
まず，球を箱のどれか1つに無作為に入れる．次に，球を，箱が空ならば箱に入れ，箱が空でなければ残りの個の空の箱のどれか1つに無作為に入れる．
一般に，について，球を，箱が空ならば箱に入れ，箱が空でなければ残りの個の空の箱のどれか1つに無作為に入れる．
(1) が入（はい）る箱はまたはである．これを証明せよ．
(2) がに入る確率を求めよ．
方針
これは「自分の箱がすでに埋まっていた球」が出たときだけ無作為選択が続く連鎖である。連鎖の候補に常に と、まだ処理していない番号の箱が含まれることを追うと、最後の は または にしか入らない。(2)では、 の時点までに重要なのは のうちどれが最初に連鎖で選ばれるかであり、無作為選択の順序の対称性から3つは同確率になる。
解答
(1)
が入る時点で が空なら、 は必ず に入る。したがって問題が起こるのは、ある の時点で がすでに埋まっている場合だけである。このとき、残っている空箱から1つを無作為に選び、その選ばれた箱の番号によって連鎖が続く。
まず が に入った場合、その後は各 が自分の箱 に入るので、 は に入る。 が に入った場合、 はそれぞれ自分の箱に入り、最後に空いている に が入る。 が に入った場合を考える。このとき は自分の箱に入るが、 の時点で はすでに埋まっている。そこで は残っている空箱から1つを無作為に選ぶ。
ここで が を選べば、その後は が自分の箱に入り、 は に入る。 が を選べば、最後に残るのは なので、 は に入る。 が別の を選べば、同じ状況が の時点で繰り返される。
この連鎖は、途中で または が選ばれた時点で終わる。どちらの場合でも、最終的に が入る箱は または である。よって(1)が示された。
(2)
が に入るかどうかを決めるには、上の連鎖の中で のどれが最初に選ばれるかを見ればよい。
連鎖中に無作為選択が起こるたび、まだ選ばれていない空箱の中から等確率で1つが選ばれる。したがって、連鎖で選ばれていく箱の順序は、候補となる箱を無作為な順序に並べたものと同じである。よって、 の3つのうち、最初に現れる箱は対称であり、それぞれ確率 である。
もし がこの3つの中で最初に選ばれたなら、 の時点では はすでに埋まっているので、 は に入らない。
一方、 または が先に選ばれたなら、連鎖はそこで実質的に終わり、 は の時点まで空のままである。したがって は に入る。
よって求める確率は である。
別解。 だけに注目し、それ以外の箱が連鎖中に選ばれても無視する。無視された箱は、単に連鎖を次の番号へ進めるだけで、3つの箱の相対的な順序には影響しない。したがって、この3箱が連鎖中に現れる順番は全て同様に確からしい。 が に入らないのは、3箱の中で が最初に現れる場合だけなので、その確率は 。したがって入る確率は である。