バナッハのマッチ箱

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

つまり，

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

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

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

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

である。よって，$p_K=\dfrac{{}_{2n-K}\mathrm{C}_n}{2^{2n-K}}$

まず，$p_K$ と $p_{K+1}$ の関係式を作る。

$p_{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}$

よって，

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

変形すると，

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

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

$(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)(1-p_0)-\displaystyle\sum_{K=1}^nKp_K=2n-2\sum_{K=0}^{n}Kp_K$

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

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