バナッハのマッチ箱

バナッハのマッチ箱と呼ばれる有名な確率の問題とその解法を解説します。

問題

nn 本のマッチが入ったマッチ箱が2つある。ランダムに選んだ方のマッチ箱からマッチを1本取り出す操作を繰り返す。選んだマッチ箱が空になっている状況が発生したら終了する。このとき,もう片方のマッチ箱に残っているマッチの本数が KK 本である確率 pKp_K を求めよ。

注:「選んだマッチ箱が(すでに)空になっている」という状況は同じマッチ箱を n+1n+1 回選ぶと発生します。

確率 pKp_K の計算

操作の回数と残った本数の間に成り立つ関係式に注目します。

問題の解答

終了までに操作が NN 回行われるとする。このとき,片方のマッチ箱を選んだ回数が n+1n+1 回,もう片方のマッチ箱を選んだ回数が N(n+1)N-(n+1) 回である。つまり,nK=N(n+1)n-K=N-(n+1) である。これを変形すると,N=2n+1KN=2n+1-K

つまり,

残った本数が KK    \iff 操作の回数が 2n+1K2n+1-K

となる。よって,終了までに 2n+1K2n+1-K 回操作が行われる確率を求めればよい。これは

「最初の 2nK2n-K 回のうちマッチ箱 AAnn 回選び,2n+1K2n+1-K 回目で AA を選ぶ確率」と「最初の 2nK2n-K 回のうちマッチ箱 BBnn 回選び,2n+1K2n+1-K 回目で BB を選ぶ確率」の和に等しい。それらはともに反復試行の確率の考え方より,

2nKCn122nK12{}_{2n-K}\mathrm{C}_n\dfrac{1}{2^{2n-K}}\cdot\dfrac{1}{2}

である。よって,pK=2nKCn22nKp_K=\dfrac{{}_{2n-K}\mathrm{C}_n}{2^{2n-K}}

注:当然ですが,上記の議論は 0Kn0\leq K\leq n のもとで成立します。そうでないときは pK=0p_K=0 です。

期待値の計算

残っているマッチの本数 KK の期待値は,(2n+1)2nCn22n1\dfrac{(2n+1){}_{2n}\mathrm{C}_n}{2^{2n}}-1

K=1nKpK\displaystyle\sum_{K=1}^nKp_K を計算するだけですが,そのままではかなり厳しいので工夫して計算します。「漸化式を作ってそこから強引に KpKKp_K(K+1)pK+1(K+1)p_{K+1} を作り出して足し上げる」という方針です。

証明

まず,pKp_KpK+1p_{K+1} の関係式を作る。

pK+1=(2nK1)!(nK1)!n!122nK1=pK2(nK)2nKp_{K+1}\\ =\dfrac{(2n-K-1)!}{(n-K-1)!n!}\cdot\dfrac{1}{2^{2n-K-1}}\\ =p_K\cdot\dfrac{2(n-K)}{2n-K}

よって,

(2nK)pK+1=2(nK)pK(2n-K)p_{K+1}=2(n-K)p_K

変形すると,

(2n+1)pK+1(K+1)pK+1=2npK2KpK(2n+1)p_{K+1}-(K+1)p_{K+1}=2np_K-2Kp_K

これを K=0K=0 から n1n-1 まで足し上げて変形していくと,

(2n+1)(1p0)K=1nKpK=2n(1pn)2K=0n1KpK(2n+1)(1-p_0)-\displaystyle\sum_{K=1}^nKp_K=2n(1-p_n)-2\sum_{K=0}^{n-1}Kp_K

(2n+1)(1p0)K=1nKpK=2n2K=0nKpK(2n+1)(1-p_0)-\displaystyle\sum_{K=1}^nKp_K=2n-2\sum_{K=0}^{n}Kp_K

K=1nKpK=2n(2n+1)+p0(2n+1)\displaystyle\sum_{K=1}^nKp_K=2n-(2n+1)+p_0(2n+1)

これと,p0=2nCn22np_0=\dfrac{{}_{2n}\mathrm{C}_n}{2^{2n}} より目標の式を得る。

ちなみに,n=10n=10 のとき,KK の期待値は約 2.72.7 です。