Banachのマッチ箱問題

同義語：Banach's matchbox problem

概要

前提知識: 反復試行の確率, 最短経路の数え上げと鏡像原理, 二項定理と組合せの恒等式

高校での出発点：残りは何本か

左右のポケットに、マッチ棒が $N$ 本ずつ入った箱を 1 つずつ入れておく。マッチが必要になるたびに、左右のどちらかのポケットを確率 $\dfrac12$ ずつで選び、その箱から 1 本使う。何回か使ううちに、選んだ箱が空だったということが起こる。そのとき、もう一方の箱には何本残っているだろうか。
左右を同じ確率で選ぶのだから、2 つの箱はだいたい同じ速さで減り、空に気づいたときにはもう一方もほとんど空だろう、と考えたくなる。一方で、偶然の偏りで片方だけが早く減ることもある。まず $N=2$ で、すべての場合を数えてみる。

$N=2$ の場合を全部数える

選んだポケットを「左」「右」で順に並べて書く。箱には 2 本ずつ入っているので、同じポケットを 3 回目に選んだときに、その箱が空だと気づく。そのときのもう一方の箱の残りの本数を $R$ とする。
(1) $R=2$ となるのは、最初の 3 回がすべて同じポケットのときで、左左左と右右右の 2 通りである。どちらも確率 $\left(\dfrac12\right)^3=\dfrac18$ なので、$P(R=2)=\dfrac28=\dfrac14$ である。
(2) $R=1$ となるのは、4 回目に空に気づくときである。4 回目に選んだポケットを左とすると、最初の 3 回のうち左がちょうど 2 回、右が 1 回で、4 回目が左である。最初の 3 回の並べ方は $\dbinom32=3$ 通り（左左右、左右左、右左左）ある。4 回目が右の場合も 3 通りで、合わせて 6 通り、どれも確率 $\left(\dfrac12\right)^4=\dfrac1{16}$ なので、$P(R=1)=\dfrac6{16}=\dfrac38$ である。
(3) $R=0$ となるのは、5 回目に空に気づくときである。5 回目を左とすると、最初の 4 回のうち左がちょうど 2 回で、並べ方は $\dbinom42=6$ 通りある。5 回目が右の場合も 6 通りで、合わせて 12 通り、どれも確率 $\left(\dfrac12\right)^5=\dfrac1{32}$ なので、$P(R=0)=\dfrac{12}{32}=\dfrac38$ である。
(4) 確率の和は $\dfrac38+\dfrac38+\dfrac14=1$ で、期待値は
$$ E[R]=0\cdot\frac38+1\cdot\frac38+2\cdot\frac14=\frac78 $$
である。

$N=2$ では、$R=0$ と $R=1$ が同じ確率で最も起こりやすい。この記事では、一般の $N$ について次の問いに答える。

$R$ の分布は、$N$ と $r$ の式でどう書けるか。→ thm-bnm-dist
最も起こりやすい $R$ の値はいくつか。→ prop-bnm-mode
$R$ の期待値はいくつか。$N$ を大きくすると、どのくらいの速さで増えるか。→ thm-bnm-mean、cor-bnm-asymp

止め方や左右の選び方を変えると、何が変わるか。→ ex-bnm-cx-last、ex-bnm-cx-biased

高校の計算	この記事の言葉	大学の言葉
左右の選び方の並べ方を数える	反復試行の確率	独立な試行の列
格子の道の数	止まる点までの経路	ランダムウォークの到達時刻
二項係数の和が $1$	分布の確率の和	組合せの恒等式
中央の二項係数 $\binom{2N}N$ の大きさ	期待値の増え方	Stirling の公式による漸近

言葉の準備：問題の設定と格子の道

Banach のマッチ箱問題の設定

正の整数 $N$ を決める。左右のポケットに、マッチが $N$ 本ずつ入った箱が 1 つずつある。次を仮定する。
(R1) マッチが必要になるたびに、左右のポケットを確率 $\dfrac12$ ずつで選ぶ。選び方は毎回互いに独立である。
(R2) 選んだ箱にマッチがあれば 1 本使う。選んだ箱が空なら、そこで初めて空だと気づき、手順を終える。
終えたときに、もう一方の箱に残っているマッチの本数を $R$ とする。$R$ は $0,1,\ldots,N$ のどれかの値をとる。

この設定と問いは GS06 の §6.1 練習問題 34 にある。条件 (ii) の「気づく」に注意する。最後の 1 本を使った時点では、箱が空になったことにまだ気づいていない。その箱をもう一度選んで、初めて気づく。ある箱が空だと気づくのは、その箱を $N+1$ 回目に選んだときである。

空に気づくまでの回数

$N=5$ で、選んだポケットが左、右、左、左、右、右、左、右、左、左の順だったとする。左は 1, 3, 4, 7, 9, 10 回目に選ばれ、10 回目が左の 6 回目なので、そこで左の箱が空だと気づく。それまでに右は 4 回選ばれたので、右の箱の残りは $5-4=1$ 本で、$R=1$ である。空に気づいたのは $10=2\cdot5-1+1$ 回目である。

一般に、$R=r$ で左の箱が空だと気づいたとすると、左は $N+1$ 回、右は $N-r$ 回選ばれているので、空に気づいたのは $(N+1)+(N-r)=2N-r+1$ 回目である。
選び方の列は、平面の格子の道で表せる。原点から出発し、左を選ぶと右へ 1、右を選ぶと上へ 1 進む。左の箱が空だと気づくのは、道が直線 $x=N+1$ に初めて触れたとき、右の箱が空だと気づくのは、直線 $y=N+1$ に初めて触れたときである。図 1 は ex-bnm-steps の道である。止まる点が $(N+1,\,N-r)$ か $(N-r,\,N+1)$ なら、$R=r$ である。
N = 5 の選び方の列を格子の道で表した図。左を選ぶと右へ、右を選ぶと上へ進み、赤か青の線に着いたところで空に気づく。この道は (6, 4) で止まり、R = 1 になる
選び方の列の長さは、止まるまでの回数によって変わる。確率を数えやすくするため、長さをそろえる。

$2N+1$ 回で必ず止まる

def-bnm-setting の手順は、$2N+1$ 回目までに必ず終わる。

手順が $2N$ 回目までに終わらなかったとする。すると $2N$ 回のどの選択でも箱にマッチがあったので、左を選んだ回数は $N$ 以下、右を選んだ回数も $N$ 以下である。2 つの回数の和は $2N$ なので、どちらもちょうど $N$ で、両方の箱が空になっている。したがって $2N+1$ 回目にはどちらを選んでも空の箱を選び、手順が終わる。$\square$

そこで、手順が終わった後も形式的に選び続けることにして、長さ $2N+1$ の左右の列を考える。長さ $2N+1$ の列は $2^{2N+1}$ 通りあり、条件 (i) からどれも確率 $\left(\dfrac12\right)^{2N+1}$ で起こる。$R$ の値は列の前の方（手順が終わるまでの部分）だけで決まり、その後ろの部分はどう選んでも $R$ は変わらない。

主定理 1：残りの本数の分布

残りの本数の分布

def-bnm-setting の設定で、$r=0,1,\ldots,N$ について
$$ P(R=r)=\binom{2N-r}{N}\left(\frac12\right)^{2N-r} $$
である。

方針：長さ $2N+1$ の列のうち $R=r$ となるものを数え、$2^{2N+1}$ で割る。
段 1（左の箱が空だと気づく場合）。$R=r$ で左の箱が空だと気づくのは、$2N-r+1$ 回目に左を選び、それが左の $N+1$ 回目のときである。つまり

最初の $2N-r$ 回のうち、左がちょうど $N$ 回（右は $N-r$ 回）、
$2N-r+1$ 回目が左
のときである。このとき、最初の $2N-r$ 回では左が $N$ 回以下、右が $N-r$ 回以下しか選ばれていないので、途中で空の箱を選ぶことはなく、手順は $2N-r+1$ 回目に初めて終わる。最初の $2N-r$ 回のうち左を選ぶ $N$ 回の位置の選び方は $\dbinom{2N-r}N$ 通りで、$2N-r+1$ 回目は左の 1 通り、残りの $(2N+1)-(2N-r+1)=r$ 回は何でもよいので $2^r$ 通りである。よって、このような列は
$$ \binom{2N-r}N\cdot2^r $$
通りある。
段 2（右の箱が空だと気づく場合）。左と右を入れ替えれば同じ数え方ができ、同じく $\dbinom{2N-r}N\cdot2^r$ 通りある。段 1 の列と段 2 の列は、$2N-r+1$ 回目が左か右かで異なるので重ならない。
段 3（確率）。$R=r$ となる列は合わせて $2\dbinom{2N-r}N2^r$ 通りで、どの列も確率 $\left(\dfrac12\right)^{2N+1}$ なので
$$ P(R=r)=\frac{2\binom{2N-r}N2^r}{2^{2N+1}}=\binom{2N-r}N\frac{2^{r+1}}{2^{2N+1}}=\binom{2N-r}N\left(\frac12\right)^{2N-r} $$
である。$\square$

段 1 は、反復試行の確率の「$n$ 回のうち $k$ 回起こる確率」と同じ数え方に、「最後の 1 回が決まっている」という条件を加えたものである。格子の道で言えば、$(0,0)$ から $(N,\,N-r)$ までの道（$\dbinom{2N-r}N$ 通り。最短経路の数え上げと鏡像原理）を進んでから、右へ 1 歩出て直線 $x=N+1$ に触れる道である。

$N=2$ と $N=5$

$N=2$ では
$$ P(R=0)=\binom42\frac1{2^4}=\frac6{16}=\frac38,\quad P(R=1)=\binom32\frac1{2^3}=\frac38,\quad P(R=2)=\binom22\frac1{2^2}=\frac14 $$
で、ex-bnm-start の数え上げと一致する。

$N=5$ では、$r=0,1,\ldots,5$ について $\dbinom{10-r}5\left(\dfrac12\right)^{10-r}$ を計算して、次の表になる（図 2）。

$r$	$0$	$1$	$2$	$3$	$4$	$5$
$\binom{10-r}5$	$252$	$126$	$56$	$21$	$6$	$1$
$2^{10-r}$	$1024$	$512$	$256$	$128$	$64$	$32$
$P(R=r)$	$\frac{63}{256}$	$\frac{63}{256}$	$\frac7{32}$	$\frac{21}{128}$	$\frac3{32}$	$\frac1{32}$
小数	$0.246$	$0.246$	$0.219$	$0.164$	$0.094$	$0.031$

N = 5 のときの残りの本数 R の分布。R = 0 と R = 1 が同じ確率で最も大きく、r が増えると確率は減る。赤の破線は期待値
分布の確率を足すと $1$ になる。これを式で書くと、組合せの恒等式が 1 つ得られる。

二項係数の恒等式

$$ \sum_{r=0}^{N}\binom{2N-r}N2^r=4^N $$
である。

lem-bnm-length より手順は必ず終わり、$R$ は $0,1,\ldots,N$ のどれか 1 つの値をとる。事象 $R=0$、$R=1$、…、$R=N$ は互いに重ならず、合わせるとすべての場合になるので、確率の和は $1$ である。thm-bnm-dist を代入して
$$ \sum_{r=0}^N\binom{2N-r}N\left(\frac12\right)^{2N-r}=1 $$
両辺に $2^{2N}=4^N$ を掛けると、$\left(\dfrac12\right)^{2N-r}\cdot2^{2N}=2^r$ なので結論を得る。$\square$

恒等式を確かめる

$N=2$ では $\dbinom42\cdot1+\dbinom32\cdot2+\dbinom22\cdot4=6+6+4=16=4^2$ である。$N=3$ では $\dbinom63+\dbinom53\cdot2+\dbinom43\cdot4+\dbinom33\cdot8=20+20+16+8=64=4^3$ である。

ex-bnm-values の表で、$R=0$ と $R=1$ の確率が等しく、その後は減っていくことに気づく。これは一般の $N$ で成り立つ。

最も起こりやすい値

$p_r=P(R=r)$ と書くと、$r=0,1,\ldots,N-1$ について
$$ \frac{p_{r+1}}{p_r}=\frac{2(N-r)}{2N-r} $$
である。したがって $p_0=p_1$ で、$r\ge1$ では $p_r>p_{r+1}$ である。$R$ が最も起こりやすい値は $0$ と $1$ である（$N=1$ では $p_0=p_1=\frac12$）。

thm-bnm-dist と $\dbinom nk=\dfrac{n!}{k!\,(n-k)!}$ から
$$ \frac{p_{r+1}}{p_r}=\frac{\binom{2N-r-1}N}{\binom{2N-r}N}\cdot\frac{2^{2N-r}}{2^{2N-r-1}}=\frac{(2N-r-1)!\;N!\,(N-r)!}{N!\,(N-r-1)!\;(2N-r)!}\cdot2=\frac{2(N-r)}{2N-r} $$
である（$(N-r)!=(N-r)\cdot(N-r-1)!$、$(2N-r)!=(2N-r)\cdot(2N-r-1)!$ で約分した）。$r=0$ では $\dfrac{2N}{2N}=1$ なので $p_1=p_0$ である。$r\ge1$ では $2(N-r)=2N-2r<2N-r$ なので比は $1$ より小さく、$p_{r+1}< p_r$ である。$\square$

$R=0$ が最も起こりやすい値の 1 つであることは、次のように直接も分かる。

$R=0$ となる確率

$R=0$ となるのは、最初の $2N$ 回で左右がちょうど $N$ 回ずつ選ばれるときである。実際、そのとき両方の箱が空で、$2N+1$ 回目にどちらを選んでも空に気づき、もう一方も $0$ 本である。逆に $R=0$ なら、空に気づいた $2N+1$ 回目までに、もう一方の箱も $N$ 回選ばれている。よって
$$ P(R=0)=\binom{2N}N\left(\frac12\right)^{2N} $$
で、これは公平な硬貨を $2N$ 回投げて表がちょうど $N$ 回出る確率と同じである。$N=5$ では $\dfrac{252}{1024}=\dfrac{63}{256}$ である。

主定理 2：残りの本数の期待値

残りの本数の期待値

def-bnm-setting の設定で
$$ E[R]=\frac{(2N+1)\binom{2N}N}{4^N}-1 $$
である。

方針：prop-bnm-mode の比の式を分母を払った形で書き、$r$ について足し合わせる。確率の和が $1$ であることと、期待値の定義 $E[R]=\sum_r r\,p_r$ を使うと、$E[R]$ についての 1 次方程式が得られる。
段 1（分母を払う）。prop-bnm-mode の式の分母を払うと、$r=0,1,\ldots,N-1$ について
$$ (2N-r)\,p_{r+1}=2(N-r)\,p_r $$
である。$p_{N+1}=0$ と決めておくと、$r=N$ でも両辺が $0$ になって成り立つ。
段 2（足し合わせる）。段 1 の式を $r=0,1,\ldots,N$ について足す。右辺の和は、確率の和 $\sum_{r=0}^Np_r=1$ と $\sum_{r=0}^Nr\,p_r=E[R]$ から
$$ \sum_{r=0}^N2(N-r)\,p_r=2N\sum_{r=0}^Np_r-2\sum_{r=0}^Nr\,p_r=2N-2E[R] $$
である。左辺の和は、$s=r+1$ とおくと $2N-r=2N+1-s$ で、$s$ は $1$ から $N+1$ まで動く。$p_{N+1}=0$ なので
$$ \sum_{r=0}^N(2N-r)\,p_{r+1}=\sum_{s=1}^{N}(2N+1-s)\,p_s=(2N+1)\sum_{s=1}^Np_s-\sum_{s=1}^Ns\,p_s=(2N+1)(1-p_0)-E[R] $$
である（$\sum_{s=1}^Np_s=1-p_0$、$\sum_{s=1}^Ns\,p_s=\sum_{s=0}^Ns\,p_s=E[R]$）。
段 3（解く）。段 2 の 2 つの和は等しいので
$$ (2N+1)(1-p_0)-E[R]=2N-2E[R] $$
である。$E[R]$ について解くと
$$ E[R]=2N-(2N+1)(1-p_0)=(2N+1)p_0-1 $$
である。ex-bnm-zero より $p_0=\dbinom{2N}N\Big/4^N$ なので、結論を得る。$\square$

段 1 の式を $(N-r)p_r=\dfrac12(2N+1)p_{r+1}-\dfrac12(r+1)p_{r+1}$ と書き直して期待値を求める筋道は、GS06 の §6.1 練習問題 34 の小問にもなっている。

公式に数を入れる

$N=1$：$\dfrac{3\cdot2}{4}-1=\dfrac12$。$R$ は $0$ と $1$ を確率 $\dfrac12$ ずつでとるので、直接計算しても $\dfrac12$ である。
$N=2$：$\dfrac{5\cdot6}{16}-1=\dfrac{30}{16}-1=\dfrac78$ で、ex-bnm-start の $\dfrac78$ と一致する。
$N=5$：$\dfrac{11\cdot252}{1024}-1=\dfrac{2772}{1024}-1=\dfrac{437}{256}\approx1.707$ である。ex-bnm-values の表から直接計算すると
$$ 0\cdot\frac{63}{256}+1\cdot\frac{63}{256}+2\cdot\frac{56}{256}+3\cdot\frac{42}{256}+4\cdot\frac{24}{256}+5\cdot\frac8{256}=\frac{63+112+126+96+40}{256}=\frac{437}{256} $$
で一致する。

$N$ を大きくしたときの期待値の増え方は、中央の二項係数 $\dbinom{2N}N$ の大きさで決まる。Wallisの公式（高校数学）の系「Wallis の積と中央の二項係数」は
$$ \lim_{N\to\infty}\frac{\binom{2N}N}{4^N}\sqrt{\pi N}=1 $$
を示している（記号で $\dbinom{2N}N\sim\dfrac{4^N}{\sqrt{\pi N}}$ と書く）。

期待値の増え方

$$ \lim_{N\to\infty}\frac{E[R]+1}{2\sqrt{N/\pi}}=1 $$
である。つまり $N$ が大きいとき、$E[R]$ はおよそ $2\sqrt{N/\pi}-1$ で、$\sqrt N$ に比例する程度の速さで増える。特に $\dfrac{E[R]}N\to0$ である。

thm-bnm-mean より $E[R]+1=(2N+1)\dfrac{\binom{2N}N}{4^N}$ なので
$$ \frac{E[R]+1}{2\sqrt{N/\pi}}=\frac{2N+1}{2\sqrt{N/\pi}\cdot\sqrt{\pi N}}\cdot\frac{\binom{2N}N}{4^N}\sqrt{\pi N}=\frac{2N+1}{2N}\cdot\frac{\binom{2N}N}{4^N}\sqrt{\pi N} $$
である（$\sqrt{N/\pi}\cdot\sqrt{\pi N}=N$）。$N\to\infty$ で $\dfrac{2N+1}{2N}=1+\dfrac1{2N}\to1$、後ろの因子は上の極限により $1$ に近づくので、積は $1$ に近づく。
最後の主張：$\dfrac{E[R]+1}{2\sqrt{N/\pi}}$ は $1$ に近づくので、$N$ が十分大きければ $2$ 以下であり、そのとき $0\le\dfrac{E[R]}N\le\dfrac{E[R]+1}N\le\dfrac{4\sqrt{N/\pi}}N=\dfrac4{\sqrt{\pi N}}$ である。右辺は $0$ に近づくので、はさみうちの原理により $\dfrac{E[R]}N\to0$ である。$\square$

期待値と近似値の表

$N$	$E[R]$	$2\sqrt{N/\pi}-1$	$E[R]/N$
$5$	$1.707$	$1.523$	$0.341$
$10$	$2.700$	$2.568$	$0.270$
$50$	$7.039$	$6.979$	$0.141$
$100$	$10.326$	$10.284$	$0.103$
$200$	$14.988$	$14.958$	$0.075$

$N=100$ なら、空に気づいたときにもう一方の箱に残っている本数は平均で約 $10$ 本である。$N$ を $4$ 倍にしても、期待値は約 $2$ 倍にしかならない（図 3）。

箱の最初の本数 N と残りの本数の期待値。青が正確な値、赤の破線が 2√(N/π) − 1 で、2 つはほぼ重なる。灰色の点線 N/10 と比べると、期待値の増え方は √N の程度で、N に比例するより遅い
「左右を同じ確率で選ぶので、空に気づいたときにはもう一方もほとんど空」という直感は、期待値が $N$ に比べて小さい（$\dfrac{E[R]}N\to0$）という意味では正しい。しかし、残りの本数そのものは $N$ とともに $\sqrt N$ の程度で増えていき、$0$ に近いままではない。また、最も起こりやすい値は $0$ と $1$ で、分布は $0$ の近くに偏りながら長く裾を引く（図 2）。

例と反例：設定を変えると何が変わるか

thm-bnm-dist の式は、def-bnm-setting の 2 つの条件に合わせて数えた結果である。条件を変えると式も変わる。

変える条件	例	変わること
条件 (ii) の止め方：最後の 1 本を使ったときに止める	ex-bnm-cx-last	$R$ は $1$ 以上になり、分布は（$N\ge2$ なら）$N-1$ の場合を $1$ だけずらしたものになる
条件 (i) の確率：左を確率 $p\ne\frac12$ で選ぶ	ex-bnm-cx-biased	式が $\binom{2N-r}N\left(p^{N+1}q^{N-r}+q^{N+1}p^{N-r}\right)$ に変わり、$R=0$ が最も起こりやすいとは限らない
「残りは $N$ に比例する」と考える	ex-bnm-table	$\frac{E[R]}N\to0$ で、比例しない

反例：最後の 1 本を使ったときに止める

条件 (ii) を変えて、どちらかの箱の最後の 1 本を使った時点（箱が空になった時点）で止め、そのときのもう一方の残りを $R'$ とする。
(1) 左の箱の最後の 1 本を使うのは、左を $N$ 回目に選んだときである。そのとき右の残りが $r$ 本なら、右は $N-r$ 回選ばれていて、$r\ge1$ である（右も $N$ 回選ばれていたら、右の箱はそれより前に空になっていて、そこで止まっている）。最初の $2N-r-1$ 回のうち左が $N-1$ 回、$2N-r$ 回目が左、という列の数え方は thm-bnm-dist の段 1 と同じで、左右を合わせて
$$ P(R'=r)=2\binom{2N-r-1}{N-1}\left(\frac12\right)^{2N-r}\qquad(r=1,2,\ldots,N) $$
である。
(2) 右辺を書き直すと $\dbinom{2(N-1)-(r-1)}{N-1}\left(\dfrac12\right)^{2(N-1)-(r-1)}$ で、thm-bnm-dist の $N$ を $N-1$ に、$r$ を $r-1$ に替えたものに等しい（$2\cdot\left(\frac12\right)^{2N-r}=\left(\frac12\right)^{2N-r-1}$）。つまり $N\ge2$ のとき、$R'-1$ は、箱が $N-1$ 本ずつの問題の $R$ と同じ分布をもつ（$N=1$ では $R'=1$ である）。
(3) (2) の理由は次のように見える。どちらの手順も「どちらかのポケットを $N$ 回目に選んだ時点」で止まる。箱が $N-1$ 本ずつの問題では、それが空に気づく時点で、もう一方の残りは $(N-1)-(\text{もう一方を選んだ回数})$ である。箱が $N$ 本ずつで最後の 1 本を使ったときに止める問題では、もう一方の残りは $N-(\text{もう一方を選んだ回数})$ で、ちょうど $1$ 多い。同じ選び方の列に対して、$R'$ は $N-1$ 本の問題の $R$ に $1$ を足したものになる。$N=5$ では $P(R'=1)=P(R'=2)=\dfrac{35}{128}$、$P(R'=3)=\dfrac{15}{64}$、$P(R'=4)=\dfrac5{32}$、$P(R'=5)=\dfrac1{16}$ で（図 4）、期待値は $N=4$ の場合の $E[R]=\dfrac{187}{128}$ に $1$ を足した $\dfrac{315}{128}\approx2.461$ である。空に気づく版の $\dfrac{437}{256}\approx1.707$ とは違う。どちらの止め方で数えるかで答えが変わるので、問題文の「気づく」を読み落とさないことが大事である。

N = 5 で、空に気づいたときに止める場合（左）と、最後の 1 本を使ったときに止める場合（右）の残りの本数の分布。右は、空に気づいたときに止める場合の N = 4 の分布を 1 だけ右にずらした形

反例：左右を選ぶ確率が偏っている

条件 (i) を変えて、左を確率 $p$、右を確率 $q=1-p$ で選ぶとする（$0< p<1$）。thm-bnm-dist の段 1 の列（最初の $2N-r$ 回に左が $N$ 回・右が $N-r$ 回、$2N-r+1$ 回目が左）は、どれも確率 $p^{N+1}q^{N-r}$ で起こる。段 2（右の箱が空）の列は $q^{N+1}p^{N-r}$ である。よって
$$ P(R=r)=\binom{2N-r}N\left(p^{N+1}q^{N-r}+q^{N+1}p^{N-r}\right) $$
である。$p=q=\dfrac12$ なら $2\cdot\left(\dfrac12\right)^{2N-r+1}=\left(\dfrac12\right)^{2N-r}$ となり、thm-bnm-dist にもどる。
$N=2$、$p=\dfrac23$ では
$$ P(R=0)=6\left(\frac8{27}\cdot\frac19+\frac1{27}\cdot\frac49\right)=\frac8{27},\quad P(R=1)=3\left(\frac8{27}\cdot\frac13+\frac1{27}\cdot\frac23\right)=\frac{10}{27},\quad P(R=2)=\frac8{27}+\frac1{27}=\frac13 $$
で、和は $\dfrac{8+10+9}{27}=1$ である。最も起こりやすい値は $R=1$ で、$p=\dfrac12$ のときの「$R=0$ と $R=1$ が最大」は成り立たない。偏りがあると、よく選ばれる方の箱が先に空になり、もう一方に多く残りやすい。

大学数学で見る：ランダムウォークとしての見方

格子の道（図 1）を、左を選ぶと $+1$、右を選ぶと $-1$ 進む数直線の上の歩みに読み替えると、左右を選んだ回数の差 $S_n$（$n$ 回目までの左の回数から右の回数を引いたもの）は、確率 $\dfrac12$ ずつで $\pm1$ 動く 単純ランダムウォーク になる。ex-bnm-zero の $P(R=0)=\dbinom{2N}N\Big/4^N$ は、このウォークが $2N$ 歩後に出発点にもどっている確率 $P(S_{2N}=0)$ にほかならない。

$\sqrt N$ の程度で増える理由と、関連する話題を開く

$2N$ 歩のウォークの位置 $S_{2N}$ は、平均 $0$、分散 $2N$ の分布に従う（1 歩の分散が $1$ で、独立な歩みの分散は足し合わされる。確率変数の期待値と分散）。標準偏差は $\sqrt{2N}$ で、ウォークが出発点から離れる距離は典型的に $\sqrt N$ の程度である。空に気づいた時点では、空の箱のポケットが $N+1$ 回、もう一方が $N-R$ 回選ばれているので、差の絶対値はちょうど $R+1$ である。空に気づくのは $N+1$ 回目から $2N+1$ 回目の間なので、cor-bnm-asymp の $\sqrt N$ の程度の増え方はこのことと整合する（ここでは目安として述べ、証明はしない）。二項分布を $\sqrt N$ の目盛りで見ると正規分布に近づくことは二項分布から正規分布へで扱う。$R/\sqrt N$ の分布の $N\to\infty$ での極限の形については、この記事では扱わない。

中央の二項係数の大きさ $\dbinom{2N}N\sim\dfrac{4^N}{\sqrt{\pi N}}$ は、Stirlingの公式からも導ける。この記事では Wallisの公式（高校数学）の結果を使った。

演習

$N=3$ の分布と期待値

$N=3$ のとき、$R$ の分布を求め、期待値を直接計算して thm-bnm-mean の式の値と比べよ。

解答を開く

thm-bnm-dist より $P(R=0)=\dbinom63\dfrac1{2^6}=\dfrac{20}{64}=\dfrac5{16}$、$P(R=1)=\dbinom53\dfrac1{2^5}=\dfrac{10}{32}=\dfrac5{16}$、$P(R=2)=\dbinom43\dfrac1{2^4}=\dfrac4{16}=\dfrac14$、$P(R=3)=\dbinom33\dfrac1{2^3}=\dfrac18$。和は $\dfrac{5+5+4+2}{16}=1$。期待値は $0+\dfrac5{16}+2\cdot\dfrac4{16}+3\cdot\dfrac2{16}=\dfrac{5+8+6}{16}=\dfrac{19}{16}$。式では $\dfrac{7\cdot20}{64}-1=\dfrac{140}{64}-1=\dfrac{76}{64}=\dfrac{19}{16}$ で一致する。

平均で 10 本残るのは何本入りの箱か

cor-bnm-asymp の近似 $E[R]\approx2\sqrt{N/\pi}-1$ を使って、$E[R]$ がおよそ $10$ になる $N$ を見積もれ。

解答を開く

$2\sqrt{N/\pi}-1=10$ を解くと $\sqrt{N/\pi}=\dfrac{11}2$、$N=\dfrac{121}4\pi\approx95.0$。$N=95$ で thm-bnm-mean の式を計算すると $E[R]\approx10.04$ で、確かに約 $10$ である（$N=94$ では約 $9.98$）。

さらに先へ

反復試行で「$n$ 回目にちょうど $k$ 回目の成功が起こる確率」は $\dbinom{n-1}{k-1}p^kq^{n-k}$ で、thm-bnm-dist の段 1 はこの形の数え方である（反復試行の確率）。
格子の道が初めて直線に触れる点を数える問題は、最短経路の数え上げと鏡像原理の道具で扱える。
歩みが決まった線に着いたところで止まる問題としては、ギャンブラーの破産と比べられる。ギャンブラーの破産では所持金（差）が両側の壁に着いたところで止まるが、この問題では左右それぞれの回数が $N+1$ に着いたところで止まる。
左右の選び方の列から状態を作って確率を求める方法は、Penneyのゲームでも使った。