確率の発展：漸化式・破産問題・ランダムウォーク・秘書問題・Buffon の針

0. この記事の要点

「サイコロを振って 6 が出るまで平均何回かかるか」「持ち金を賭けて少しずつ増やすと、目標に届く前に無一文になる確率はどれくらいか」。こうした素朴な疑問は、高校では漸化式を立てて解きます。この記事では、その立式がなぜ正しいのかを確かめ、同じ考え方で、数直線上をふらふら動く点の振る舞いや、最良の人を選ぶ戦略、針を落とす実験の確率まで読み解きます。読み終えると、「終わりのない試行」の確率を、有限回の計算の極限として扱えるようになります。

• 確率や期待値の問題には、「1 回目の結果で場合分けして、残りの問題が元の問題と同じ形になる」ものが多くあります。そこで得られる漸化式を解くと、「表が出るまでの回数の期待値は $1/p$」「連続して表が 2 回出るまでは平均 6 回」などが出ます。この記事では、無限に続く試行を、有限回で打ち切った確率空間の極限として扱い、証明を厳密にします。
• 破産問題：持ち金 $a$ 円で、1 回 1 円ずつ賭けて勝つ確率 $p$、目標 $N$ 円か破産のどちらかで終わる賭けで、目標に到達する確率を求めます。公平な賭け（$p=1/2$）では $a/N$ です。
• ランダムウォーク：数直線上を確率 $1/2$ ずつで $\pm1$ 動く点について、鏡像原理（経路の一部を折り返して数える方法）を示し、(i) 初めて原点に戻る時刻の分布（Catalan 数。数え上げによく現れる数）、(ii) 最後に原点にいた時刻の分布（離散の逆正弦法則）、(iii) 確率 $1$ で原点に戻ること（再帰性）を証明します。
• Pólya の壺（赤玉を引いた回数の分布は一様）、Banach のマッチ箱問題、記録更新の回数の期待値は調和数（$1+\frac12+\cdots+\frac1n$ のこと）、秘書問題（最適な戦略で最良の人を選べる確率は $1/e$ に近づく）を証明します。
• 二項分布の確率が最大になる回数、Penney のゲーム（先手が不利になる非推移的な勝負。A は B に、B は C に、C は A に勝つように、強さに順序がつかない勝負のこと）、幾何確率と Buffon の針（確率 $2l/(\pi d)$）も扱います。

この記事で使う事前知識

• 有限確率空間: 起こりうる結果が有限個の集合と、各結果の確率の組。→ 有限確率空間
• 直積空間（独立な試行）: 独立な試行を続けて行うときの、結果の組全体と確率の決め方。→ 直積空間
• 条件付き確率と全確率の公式: ある事象が起きたとしたときの確率と、場合分けして確率を足し合わせる公式。→ 条件付き確率
• 期待値の線形性・指示関数の方法: 和の期待値は期待値の和で、「起きれば 1、起きなければ 0」の量を足して数える方法。→ 確率
• 二項分布: 成功確率 $p$ の試行を $n$ 回行ったときの、成功回数の分布。→ 二項分布

1. 動機：確率の問題を「解く」と「証明する」の間

高校の確率の発展的な問題は、次のように解かれます。

• 「サイコロを振って 6 が出るまでの回数の期待値」：$E=1\cdot\frac16+\left(1+E\right)\cdot\frac56$ と立てて $E=6$。
• 「持ち金 $a$ で、目標 $N$ に到達する確率」：$h(a)=\frac12h(a+1)+\frac12h(a-1)$ と立てて解く。
• 「針を投げて平行線にぶつかる確率」：向きと位置の範囲の面積比。

どれも自然な方法ですが、「$E=\dots+(1+E)\cdot\frac56$」と書くとき、$E$ が有限の数であることを暗黙に仮定しています。もし $E=\infty$ なら、この方程式から何もわかりません。また、無限回続く試行の確率は、前の記事で定義した有限確率空間（標本空間が有限集合）の範囲を超えます。

この記事の方針は、$M$ 回で打ち切った有限の確率空間で答えを求め、$M\to\infty$ とすることです。打ち切りの確率の増え方が単調で上に有界なら、極限が存在します（単調有界定理。定理 2.1［級数と収束判定］）。極限を取った式が漸化式を満たすことから、答えを決めます。この「打ち切りの極限」が、高校で使っている漸化式の立式を正当化します。

使う道具は、前の記事の有限確率空間（定義 2.1［確率］）、直積空間と独立（定義 4.1［確率］）、条件付き確率と全確率の公式（定理 5.3［確率］）、期待値の線形性・指示関数の方法（定理 6.3［確率］、命題 6.4［確率］）と、場合の数の記事の組合せの数（定理 4.3［場合の数］）、最短経路の数（定理 6.2［場合の数］）です。

2. 停止するまでの回数の期待値

2.1. 期待値は「まだ続いている確率」の和

試行を繰り返し、ある条件が初めて満たされた時点でやめるとき、やめるまでの回数を $T$ とします。$T$ は 1 以上の整数値で、条件が一度も満たされなければ $T=\infty$ としますが、$N$ 回で打ち切った回数 $\min(T,N)$ は、$N$ 回の試行の有限確率空間で定義された確率変数です。

なぜ打ち切るのかというと、$T$ には「いつまでも成功しない」という無限の場合があり、そのままでは平均を考えにくいからです。たとえば $N=5$ のとき、$T=3$ なら $\min(T,5)=3$、$T=8$ なら $\min(T,5)=5$ です。次の式は、この $\min(T,N)$ を「$k=1,2,\dots,N$ について、$k$ 回目まで続いていれば 1 を足す」という数え方で書き直したものです。

$\min(T,N)$ の期待値は、「$k$ 回目まで続いている確率」の和で書けます。実際、

$$\min(T,N)=\sum_{k=1}^N\mathbf 1_{\{T\ge k\}}$$

です（$k\le\min(T,N)$ となる $k$ の個数が $\min(T,N)$ だから）。指示関数の方法（命題 6.4［確率］）から、

$$E\bigl[\min(T,N)\bigr]=\sum_{k=1}^NP(T\ge k)$$

です。この式を使うと、「期待値が有限か」「いくつか」を、確率の和の問題として扱えます。

2.2. 最初の成功までと、連続 2 回の成功まで

定理 2.1（停止までの回数の期待値）✓

1. 成功確率 $p$（$0<p\le1$）の試行を独立に繰り返し、最初の成功までの回数を $T$ とする。$E[\min(T,N)]=\dfrac{1-(1-p)^N}p$ で、これは $N\to\infty$ で $\dfrac1p$ に増加して収束する。
2. 公正なコイン（表の確率 $\frac12$）を投げ続け、表が 2 回連続で出るまでの回数を $T$ とする。$E[\min(T,N)]$ は $N$ について単調増加で、$N\to\infty$ で $6$ に収束する。また、$m$ 回投げて表が 2 回連続で出ない確率を $q_m$ とすると、$q_m\le\left(\frac34\right)^{\lfloor m/2\rfloor}$ であり、とくに $q_m\to0$（$m\to\infty$）である。

証明（定理 2.1）

(1) $q=1-p$ とする。$T\ge k$ は「最初の $k-1$ 回がすべて失敗」で、直積空間の性質（命題 4.2［確率］）から $P(T\ge k)=q^{k-1}$ です。よって $E[\min(T,N)]=\sum_{k=1}^Nq^{k-1}=\dfrac{1-q^N}{1-q}=\dfrac{1-q^N}p$（等比数列の和）です。$q<1$ のとき $q^N\to0$（命題 3.1［数列と関数の極限］）なので、$1/p$ に収束します（$p=1$ のときは $N=1$ から $1$）。

(2) $q_m$ を「$m$ 回投げて表が連続しない確率」とする（$q_0=q_1=1$）。$T\ge k$ は「最初の $k-1$ 回で表が連続しない」ことなので、(1) と同じく $E[\min(T,N)]=\sum_{k=1}^Nq_{k-1}=\sum_{m=0}^{N-1}q_m$ で、各項が $0$ 以上なので単調増加です。

漸化式 $q_m=\dfrac12q_{m-1}+\dfrac14q_{m-2}$（$m\ge2$）を示します。表が連続しない長さ $m$ の列は、最後が裏（その前は表が連続しない長さ $m-1$ の列。確率 $\frac12q_{m-1}$）か、最後が表で、その前が裏（その前は表が連続しない長さ $m-2$ の列。確率 $\frac14q_{m-2}$）のどちらかで、両者は排反です。

有界性：長さ $2j$ の列を $j$ 個の連続する 2 回に区切ると、すべての区切りが「表表」でないことが必要で、独立なので $q_{2j}\le\left(\frac34\right)^j$ です。長さ $2j+1$ の列で表が連続しなければ、最初の $2j$ 回でも表が連続しないので $q_{2j+1}\le q_{2j}$ です。合わせて $q_m\le\left(\frac34\right)^{\lfloor m/2\rfloor}$ で、右辺は $m\to\infty$ で $0$ に収束します（命題 3.1［数列と関数の極限］）。したがって $\sum q_m$ は等比級数で抑えられ、有界で単調増加なので収束します（定理 2.1［級数と収束判定］）。和を $Q=\sum_{m\ge0}q_m$ とすると、漸化式を $m=2,3,\dots$ について足して $Q-q_0-q_1=\frac12(Q-q_0)+\frac14Q$、すなわち $Q-2=\frac34Q-\frac12$ で、$Q=6$ です。$E[\min(T,N)]=\sum_{m=0}^{N-1}q_m\to6$ です。

∎

(1) は、サイコロで 6 が出るまでの回数の期待値が 6（$p=\frac16$）であることを含みます。(2) の 6 は、「表が出るまでの 2 回」よりずっと大きい数で、連続を待つ待ち時間の長さを示しています。このように、「期待値は $E=1+(1-p)E$ と立てて解ける」という高校の方法は、打ち切りの極限で正当化されます。

3. 破産問題

3.1. 問題と答え

持ち金が $a$ 円の人が、1 回の賭けで 1 円を賭けます。確率 $p$ で 1 円増え、確率 $q=1-p$ で 1 円減ります（$0<p<1$）。目標の $N$ 円に到達するか、持ち金が $0$ になる（破産）かのどちらかが起こるまで、これを繰り返します。$0\le a\le N$ とします。

打ち切り：$M$ 回の賭けの有限確率空間（各回独立で、上の確率）で、$M$ 回以内に目標 $N$ に到達する（それ以前に破産していない）確率を $R_M(a)$ とします。$M$ とともに事象は大きくなるので、$R_M(a)$ は単調増加で $1$ 以下、したがって極限 $R(a)=\lim_{M\to\infty}R_M(a)$ が存在します。

定理 3.1（破産問題）✓

$0\le a\le N$ とし、$r=q/p$ とおく。

1. 賭けが有限回で終わる確率は $1$ である。すなわち、$M$ 回までにどちらにも到達していない確率は $M\to\infty$ で $0$ に収束する。
2. 目標に到達する確率 $R(a)$ は、$p=\frac12$ のとき $\dfrac aN$、$p\ne\frac12$ のとき $\dfrac{1-r^a}{1-r^N}$ である。破産する確率は $1-R(a)$ である。
3. $p>\frac12$ のとき、$N\to\infty$ の極限（目標が無限に遠い）で、破産する確率は $r^a$ に収束する。$p\le\frac12$ のとき、破産する確率は $1$ に収束する。

証明の流れは次のとおりです。(1) で「いつまでも決着しない」ことはないと確かめ、(2) で 1 回目の賭けの結果で場合分けして $R(a)$ の漸化式を作り、隣り合う $R(a)$ の差が等比数列になることから公式を導きます。(3) は、(2) の式で目標 $N$ を限りなく遠くしたときの様子です。

証明（定理 3.1）

(1) どの $a$ から出発しても、続けて $N$ 回勝てば（確率 $p^N$）、$N$ 回以内に目標に到達します。したがって $M$ 回までに決着していない確率 $D_M(a)$ について $D_N(a)\le1-p^N$ です。$d_M=\max_aD_M(a)$ とおく。最初の $N$ 回の結果で場合分けして（全確率の公式。定理 5.3［確率］）、$N$ 回目に位置 $a'$ にいて決着していない確率に、残りの $M$ 回で決着しない確率 $D_M(a')\le d_M$ を掛けて足すと $D_{M+N}(a)\le d_M\cdot D_N(a)\le(1-p^N)d_M$ です。よって $d_{kN}\le(1-p^N)^k\to0$ で、$d_M$ は $M$ について単調減少なので $d_M\to0$ です。

(2) $R_M$ は、1 回目の賭けの結果で場合分けすると（全確率の公式と、残りの賭けが独立な同じ形であること）

$$R_M(a)=p\,R_{M-1}(a+1)+q\,R_{M-1}(a-1)\quad(0<a<N,\ M\ge1),\qquad R_M(0)=0,\ R_M(N)=1$$

です。$M\to\infty$ とすると、極限 $R$ も同じ漸化式 $R(a)=pR(a+1)+qR(a-1)$ と $R(0)=0$、$R(N)=1$ を満たします。$p+q=1$ を使うと $p\bigl(R(a+1)-R(a)\bigr)=q\bigl(R(a)-R(a-1)\bigr)$ なので、階差 $d_a=R(a+1)-R(a)$ は $d_a=r\,d_{a-1}$、すなわち $d_a=r^ad_0$ です。したがって $R(a)=d_0\sum_{j=0}^{a-1}r^j$ で、$R(N)=1$ から $d_0=\left(\sum_{j=0}^{N-1}r^j\right)^{-1}$、すなわち $R(a)=\dfrac{\sum_{j<a}r^j}{\sum_{j<N}r^j}$ です。$r=1$（$p=\frac12$）なら $\dfrac aN$、$r\ne1$ なら等比数列の和で $\dfrac{1-r^a}{1-r^N}$ です。(1) より、目標に到達する確率と破産する確率の和（$M\to\infty$）は $1$ なので、破産確率は $1-R(a)$ です。

(3) $p>\frac12$ ならば $r<1$ で、破産確率は $1-\dfrac{1-r^a}{1-r^N}=\dfrac{r^a-r^N}{1-r^N}\to r^a$（$N\to\infty$。命題 3.1［数列と関数の極限］）です。$p<\frac12$ ならば $r>1$ で、$R(a)=\dfrac{r^a-1}{r^N-1}\to0$（分母 $\to\infty$）、$p=\frac12$ では $\dfrac aN\to0$ なので、破産確率は $1$ に収束します。

∎

例 3.2（公平な賭けと、不利な賭け）

公平な賭け（$p=\frac12$）：持ち金 $10$ 円、目標 $100$ 円なら、目標に到達する確率は $10/100=0.1$ です。目標を $1000$ 円にすると $0.01$ です。「持ち金に比例した確率でしか勝てない」ことを意味します。

ルーレットの赤黒（ダブルゼロのある米国式では、赤に賭けて当たる確率は $\frac{18}{38}$）：$p=\frac{18}{38}$、$r=\frac{20}{18}=\frac{10}9$、$a=100$、$N=200$ では $R(100)=\dfrac{1-r^{100}}{1-r^{200}}=\dfrac1{1+r^{100}}$（$1-r^{200}=(1-r^{100})(1+r^{100})$）で、$r^{100}=(10/9)^{100}\approx3.8\times10^4$ なので、$R(100)\approx2.7\times10^{-5}$ です。1 回あたりの不利が小さくても、「倍にして帰る」確率は極めて小さくなります。

4. 単純ランダムウォーク

4.1. 設定と経路の数

数直線上の点が、原点から出発し、1 歩ごとに確率 $\frac12$ ずつで $+1$ か $-1$ だけ動くとします。これを単純ランダムウォークといいます。$n$ 歩の結果は $\varepsilon=(\varepsilon_1,\dots,\varepsilon_n)\in\{+1,-1\}^n$（$2^n$ 通りで、同様に確からしい。命題 2.2［確率］）で、$k$ 歩後の位置は $S_k=\varepsilon_1+\cdots+\varepsilon_k$（$S_0=0$）です。以後、$2n$ 歩で原点に戻る確率を

$$u_{2n}=P(S_{2n}=0)=\frac{\binom{2n}n}{4^n}$$

と書きます（$n$ 回上がり $n$ 回下がる列の個数が $\binom{2n}n$。定理 4.3［場合の数］）。$u_0=1$、$u_{2n}=\prod_{k=1}^n\frac{2k-1}{2k}$ です（$\dfrac{u_{2n}}{u_{2n-2}}=\dfrac{(2n)(2n-1)}{4n^2}=\dfrac{2n-1}{2n}$）。

補題 4.1（経路の個数）✓

整数 $a,b$ と $m\ge0$ について、高さ $a$ から出発して $m$ 歩（各歩 $\pm1$）で高さ $b$ に到達する経路の個数を $N_m(a\to b)$ と書く。$m+b-a$ が偶数で $|b-a|\le m$ ならば $N_m(a\to b)=\dbinom m{(m+b-a)/2}$、そうでなければ $0$ である。

証明（補題 4.1）

上がる歩を $k$ 回とすると、下がる歩は $m-k$ 回で、$a+k-(m-k)=b$、すなわち $k=\frac{m+b-a}2$ です。上がる歩の位置を選ぶ選び方が $\binom mk$ 通りです（定理 4.3［場合の数］）。

∎

4.2. 鏡像原理

定理 4.2（鏡像原理）✓

$a,b$ を正の整数とし、$m\ge0$ とする。高さ $a$ から出発して $m$ 歩で高さ $b$ に到達する経路のうち、途中で高さ $0$ に（$0\le k\le m$ のいずれかの時刻に）触れるものの個数は、$N_m(-a\to b)$ に等しい。したがって、高さ $0$ に触れない経路の個数は $N_m(a\to b)-N_m(-a\to b)$ である。

ねらいは、「0 に触れる経路」を数えにくいまま数える代わりに、始点を $-a$ に取り替えた経路と一対一に対応させることです。$a$ から出発した経路が初めて 0 に着いたところまでを、0 を軸に折り返す（図の点線）と、始点が $-a$ の経路になります。

証明（定理 4.2）

$\mathcal A$ を「$a$ から $b$ へ行き、0 に触れる経路」の集合、$\mathcal B$ を「$-a$ から $b$ へ行く経路」の集合とします。$\mathcal A$ の経路 $h=(h_0,\dots,h_m)$（$h_0=a$、$h_m=b$）に対し、$h$ が最初に高さ $0$ に着く時刻を $\tau$ とし、$h'_k=-h_k$（$k\le\tau$）、$h'_k=h_k$（$k\ge\tau$）と定めます。$h'_0=-a$、$h'_\tau=0$、$h'_m=b$ で、各歩は $\pm1$ なので $h'\in\mathcal B$ です。逆に $\mathcal B$ の経路は、始点 $-a<0$ から終点 $b>0$ まで、各歩 $\pm1$ で進むので、途中で必ず高さ $0$ を通ります（途中で符号が変わるときは $0$ を飛び越えられない）。その最初の時刻 $\tau$ で $\tau$ までを反転すれば $\mathcal A$ の経路が得られます。この 2 つの操作は互いに逆なので全単射で、$|\mathcal A|=|\mathcal B|=N_m(-a\to b)$ です。

∎

鏡像原理。0 に初めて触れる時刻までを反転すると、a から b への経路と、−a から b への経路が一対一に対応する（点線が反転した部分）

4.3. 原点に戻らない確率

補題 4.3（原点に戻らない経路の個数）✓

$n\ge1$ とする。$2n$ 歩の経路のうち、$S_1\ne0,\dots,S_{2n}\ne0$ を満たすものの個数は $\binom{2n}n$ で、その確率は $u_{2n}$ である。すなわち

$$P(S_1\ne0,\ \dots,\ S_{2n}\ne0)=P(S_{2n}=0)=u_{2n}.$$

この補題は、「一度も 0 に戻らない経路」の個数が、「$2n$ 歩目に 0 にいる経路」の個数と同じになる、という意外な事実を述べています。証明では、すべて正の経路を鏡像原理で数えます。和の各項の後半が次の項の前半と打ち消し合うので、最初の前半と最後の後半だけが残ります。

証明（補題 4.3）

$S_k\ne0$（$1\le k\le2n$）を満たす経路は、$S_1=\pm1$ から符号が変わることなく進む（$\pm1$ ずつ動くので、符号を変えるには $0$ を通る必要がある）ので、すべて正（$S_k>0$）か、すべて負です。対称性から、両者の個数は等しいので、すべて正の経路の個数 $U$ を求めればよいです。

すべて正の経路は $S_1=1$ で、残りの $2n-1$ 歩は高さ $1$ から出発して高さ $0$ に触れずに進みます。終点の高さ $r$ は、$2n-1$ 歩の偶奇から偶数 $r=2j$（$1\le j\le n$）です。鏡像原理（定理 4.2）から、高さ $1$ から $2j$ へ $0$ に触れずに行く経路の個数は $N_{2n-1}(1\to2j)-N_{2n-1}(-1\to2j)=\binom{2n-1}{n+j-1}-\binom{2n-1}{n+j}$ です（補題 4.1）。したがって

$$U=\sum_{j=1}^n\left[\binom{2n-1}{n+j-1}-\binom{2n-1}{n+j}\right]=\binom{2n-1}n-\binom{2n-1}{2n}=\binom{2n-1}n$$

（隣り合う項が打ち消し合う和）です。Pascal の漸化式と対称性（命題 7.2［数え上げと母関数］）から $\binom{2n}n=\binom{2n-1}{n-1}+\binom{2n-1}n=2\binom{2n-1}n$ なので、条件を満たす経路の個数は $2U=\binom{2n}n$ です。確率は $\dfrac{\binom{2n}n}{2^{2n}}=u_{2n}$ です。

∎

4.4. 初めて原点に戻る時刻

定理 4.4（初めて原点に戻る時刻の分布）✓

$n\ge1$ とする。ウォークが時刻 $2n$ に初めて原点に戻る確率 $f_{2n}=P(S_1\ne0,\dots,S_{2n-1}\ne0,\ S_{2n}=0)$ は

$$f_{2n}=u_{2n-2}-u_{2n}=\frac{u_{2n}}{2n-1}=\frac{C_{n-1}}{2^{2n-1}}$$

である。ここで $C_m=\dfrac1{m+1}\dbinom{2m}m$ は Catalan 数である。

証明（定理 4.4）

$E_m$ を「$S_1,\dots,S_{2m}$ がすべて $0$ でない」事象とする（$E_0$ は全体）。奇数時刻は $S_k$ が奇数で $0$ にならないので、$E_m=E_{m-1}\cap\{S_{2m}\ne0\}$ です。したがって「時刻 $2n$ に初めて戻る」事象は $E_{n-1}\cap\{S_{2n}=0\}=E_{n-1}\setminus E_n$ で、$E_n\subseteq E_{n-1}$ なので $f_{2n}=P(E_{n-1})-P(E_n)=u_{2n-2}-u_{2n}$（補題 4.3。$n=1$ では $u_0=1$）です。$\dfrac{u_{2n}}{u_{2n-2}}=\dfrac{2n-1}{2n}$ から $u_{2n-2}-u_{2n}=u_{2n-2}\cdot\dfrac1{2n}=\dfrac{u_{2n}}{2n-1}$ です。最後の等号は $\dbinom{2n}n=\dfrac{(2n)(2n-1)}{n^2}\dbinom{2n-2}{n-1}$ から $\dfrac{u_{2n}}{2n-1}=\dfrac{2}{n\cdot4^n}\dbinom{2n-2}{n-1}=\dfrac{2C_{n-1}}{4^n}$ です。

∎

例 4.5（初めて戻る時刻の確率の値）

$f_2=\frac12$、$f_4=\frac18$、$f_6=\frac1{16}$、$f_8=\frac5{128}$ です（$C_0=1,C_1=1,C_2=2,C_3=5$）。最も起こりやすいのは「最初の 2 歩で戻る」で、時刻が遅いほど確率は小さくなりますが、$f_{2n}$ は（Stirling の公式から $u_{2n}\sim\frac1{\sqrt{\pi n}}$ なので）$\dfrac1{2\sqrt\pi\,n^{3/2}}$ とほぼ同じ大きさでゆっくり減るので、「戻るのにすごく時間がかかる」ことも起こりえます。

4.5. 最後に原点にいた時刻

$2n$ 歩のうち、最後に原点にいた時刻（$S_{2k}=0$ となる最大の $2k\le2n$）を $L_{2n}$ とします。

定理 4.6（最後に原点にいた時刻の分布（離散の逆正弦法則））✓

$0\le k\le n$ について

$$P(L_{2n}=2k)=u_{2k}\,u_{2n-2k}$$

である。とくに $\displaystyle\sum_{k=0}^nu_{2k}u_{2n-2k}=1$。

証明（定理 4.6）

$L_{2n}=2k$ は、$S_{2k}=0$ かつ $S_j\ne0$（$2k<j\le2n$）という事象です。$2n$ 歩を、最初の $2k$ 歩と残りの $2n-2k$ 歩に分けると、$\Omega_{2n}$ は 2 つの有限確率空間の直積で、$j>2k$ では $S_j$ は残りの歩の部分和（$S_{2k}=0$ なので）です。したがって事象は「最初の $2k$ 歩で $S_{2k}=0$」と「残りの $2n-2k$ 歩で、部分和が一度も $0$ にならない」の積事象で、独立なので確率は $u_{2k}\cdot u_{2n-2k}$ です（後者は 補題 4.3。$2n-2k=0$ のときは $u_0=1$）。事象 $\{L_{2n}=2k\}$（$k=0,\dots,n$）は互いに排反で全体を覆うので、確率の和は $1$ です。

∎

例 4.7（10 歩のウォークの最後の原点）

$u_0=1$、$u_2=\frac12$、$u_4=\frac38$、$u_6=\frac5{16}$、$u_8=\frac{35}{128}$、$u_{10}=\frac{63}{256}$ です。$2n=10$ のとき $P(L_{10}=2k)=u_{2k}u_{10-2k}$ は次のとおりです。

$2k$	$0$	$2$	$4$	$6$	$8$	$10$
確率	$\frac{63}{256}\approx0.246$	$\frac{35}{256}\approx0.137$	$\frac{30}{256}\approx0.117$	$\frac{30}{256}\approx0.117$	$\frac{35}{256}\approx0.137$	$\frac{63}{256}\approx0.246$

最後の原点は、真ん中ではなく、両端（ほとんど最初か、ほとんど最後）に集まります。「ずっと勝っている人（あるいはずっと負けている人）がいる」ことは、直観よりはるかによく起きます。

4.6. ウォークは原点に戻るか

定理 4.8（1 次元ランダムウォークの再帰性）✓

$n\ge1$ について次が成り立つ。

1. $\dfrac1{2\sqrt n}\le u_{2n}\le\dfrac1{\sqrt{2n+1}}$。
2. 時刻 $2n$ までに原点に戻る確率は $1-u_{2n}$ で、$n\to\infty$ のとき $1$ に収束する。
3. 時刻 $2N$ までに原点にいる回数の期待値 $\sum_{n=1}^Nu_{2n}$ は、$N\to\infty$ で $\infty$ に発散する。

証明（定理 4.8）

(1) $u_{2n}=\prod_{k=1}^n\frac{2k-1}{2k}$ で、$\dfrac{2k-1}{2k}\le\dfrac{2k}{2k+1}$ なので $u_{2n}^2\le\prod_{k=1}^n\dfrac{2k-1}{2k}\cdot\dfrac{2k}{2k+1}=\dfrac1{2n+1}$ です。下からは、$\dfrac{2k-1}{2k}\ge\dfrac{2k-2}{2k-1}$（$k\ge2$）なので $u_{2n}^2\ge\left(\dfrac12\right)^2\prod_{k=2}^n\dfrac{2k-2}{2k-1}\cdot\dfrac{2k-1}{2k}=\dfrac14\cdot\dfrac1n$ です。

(2) 時刻 $2n$ までに一度も戻らない確率は $u_{2n}$（補題 4.3）で、(1) から $u_{2n}\le\dfrac1{\sqrt{2n+1}}\to0$ です。

(3) 時刻 $2n$ に原点にいる事象の指示関数の和の期待値は、指示関数の方法（命題 6.4［確率］）から $\sum_{n=1}^Nu_{2n}$ です。(1) と、単調減少関数 $f(x)=\frac1{2\sqrt x}$ についての和と積分の比較（定理 8.1［積分法］）から $\sum_{n=1}^N u_{2n}\ge\sum_{n=1}^N\frac1{2\sqrt n}\ge\int_1^{N+1}\frac{dx}{2\sqrt x}=\sqrt{N+1}-1\to\infty$ です。

∎

(2) は、「ランダムウォークは確率 $1$ で原点に戻る」ことの、有限回での言い方です（戻らない確率の上限が $0$ に近づく）。(3) は、戻ってくる回数の期待値が無限であることを言っています。Stirling の公式（定理 7.1［広義積分・パラメータ積分とガンマ関数］）を使うと、$u_{2n}\sim\dfrac1{\sqrt{\pi n}}$ という精密な評価が得られます。

5. 壺とマッチ箱

5.1. Pólya の壺

壺に赤玉 1 個と青玉 1 個が入っています。次の操作を $n$ 回繰り返します。壺から玉を 1 個無作為に取り出し、色を見て、その玉と同じ色の玉をもう 1 個足して戻す（壺の玉が 1 個増える）。「赤い玉を取り出した回数」が $k$ になる確率を求めます。

$n$ 回の結果の列（赤 R、青 B の列）の確率は、条件付き確率の積（乗法定理。定理 5.3［確率］）で決まります。$j$ 回目の取り出しの前には壺に $j+1$ 個の玉があります。

定理 5.1（Pólya の壺）✓

赤 1 個、青 1 個から始めて $n$ 回繰り返したとき、赤い玉を取り出した回数がちょうど $k$ である確率は、すべての $k=0,1,\dots,n$ について $\dfrac1{n+1}$ である（一様分布）。

証明（定理 5.1）

$k$ 個の R と $n-k$ 個の B を並べた 1 つの列の確率を求めます。R を取り出すとき、壺の赤玉の個数は、そこまでに取り出した R の個数 $+1$ なので、$i$ 回目の R（$i=1,\dots,k$）の取り出しで赤玉は $i$ 個です。同様に、$i$ 回目の B の取り出しで青玉は $i$ 個です。壺の全体の個数は $j$ 回目の取り出しの前で $j+1$ なので、列の確率は、順序によらず、分子が $1\cdot2\cdots k\cdot1\cdot2\cdots(n-k)=k!\,(n-k)!$、分母が $2\cdot3\cdots(n+1)=(n+1)!$ で

$$\frac{k!\,(n-k)!}{(n+1)!}$$

です。このような列は $\binom nk$ 通りあり（定理 4.3［場合の数］）、互いに排反なので、$P(\text{赤を }k\text{ 回})=\binom nk\dfrac{k!(n-k)!}{(n+1)!}=\dfrac{n!}{(n+1)!}=\dfrac1{n+1}$ です。

∎

$n$ 回の後、壺に入っている赤玉の割合は $\dfrac{k+1}{n+2}$ で、$k$ は一様に分布するので、割合は $\left\{\dfrac1{n+2},\dots,\dfrac{n+1}{n+2}\right\}$ の上に一様に分布します。$n$ を大きくしたとき、割合が $x$ 以下である確率は、$\dfrac{\lfloor x(n+2)\rfloor}{n+1}$ で（$0\le x<1$）、この $x$ に対して $\left|\dfrac{\lfloor x(n+2)\rfloor}{n+1}-x\right|\le\dfrac1{n+1}$ です。すなわち赤玉の割合は、区間 $[0,1]$ の一様分布に近づきます。壺の中身の「最初の揺らぎ」が、永久に偏りを決めてしまう、という現象です。

5.2. Banach のマッチ箱問題

マッチ箱を 2 つ持っている人が、マッチが要るたびに、無作為に左右どちらかの箱（確率 $\frac12$ ずつ）から 1 本取り出します。両方の箱に最初 $N$ 本ずつ入っていて、あるとき空の箱を選んでしまった（空だと気づいた）とします。そのときもう一方の箱に残っている本数を $K$ とします。

定理 5.2（Banach のマッチ箱問題）✓

$k=0,1,\dots,N$ について、

$$P(K=k)=\binom{2N-k}N\frac1{2^{2N-k}}$$

である。とくに $\displaystyle\sum_{k=0}^N\binom{2N-k}N2^{-(2N-k)}=1$。

証明（定理 5.2）

「左の箱が空と気づき、右の箱に $k$ 本残っている」事象を $A_k$ とします。$A_k$ が起こるのは、選ぶ列の最初の $2N-k$ 回のうち、左を $N$ 回、右を $N-k$ 回選び、続く $(2N-k+1)$ 回目に左を選ぶ（$N+1$ 回目の左で空に気づく）ときです。最初の $2N-k$ 回の選び方は $\binom{2N-k}N$ 通りで、各列の確率は $2^{-(2N-k+1)}$ なので、$P(A_k)=\binom{2N-k}N2^{-(2N-k+1)}$ です（選択は独立。命題 4.2［確率］）。右の箱が空と気づく事象も対称で同じ確率なので、$P(K=k)=2P(A_k)=\binom{2N-k}N2^{-(2N-k)}$ です。最後の等式は、どちらかの箱が必ず（選択を $2N+1$ 回行うまでに）空に気づかれるので、$K\in\{0,\dots,N\}$ の確率の和が $1$ であることから従います。

∎

例 5.3（N = 3 のとき）

$N=3$：$P(K=0)=\binom63\frac1{2^6}=\frac{20}{64}$、$P(K=1)=\binom53\frac1{2^5}=\frac{10}{32}=\frac{20}{64}$、$P(K=2)=\binom43\frac1{2^4}=\frac4{16}=\frac{16}{64}$、$P(K=3)=\binom33\frac1{2^3}=\frac18=\frac8{64}$ で、和は $\frac{20+20+16+8}{64}=1$ です。最も起こりやすいのは「相手が 0 本または 1 本残っている」ときです。

6. 順番と最適な選択

6.1. 記録の更新

$n$ 人の相異なる値（大きさの順位は $1,\dots,n$）を、無作為な順序で 1 人ずつ見ていきます（$n!$ 通りの並び順が同様に確からしい）。$i$ 番目の人が、それまでの全員より大きいとき、$i$ 番目で記録が更新されたといいます。$X_i$ を記録更新の指示関数（更新なら $1$）とします。

定理 6.1（記録の更新回数の期待値）✓

1. $P(X_i=1)=\dfrac1i$（$i=1,\dots,n$）。
2. 記録更新の回数 $X=X_1+\cdots+X_n$ の期待値は、調和数 $H_n=\displaystyle\sum_{i=1}^n\frac1i$ である。
3. $\log(n+1)\le H_n\le1+\log n$ である。

証明（定理 6.1）

(1) 最初の $i$ 個の位置に入る値の集合の選び方は $\binom ni$ 通り、その $i$ 個のうち最大のものを $i$ 番目に置く並べ方は残り $i-1$ 個の並べ替えで $(i-1)!$ 通り、最後の $n-i$ 個の並べ方は $(n-i)!$ 通りです。記録更新となる並べ方の総数は $\binom ni(i-1)!\,(n-i)!=\dfrac{n!}i$ で、確率は $\dfrac1i$ です。

(2) 指示関数の方法と期待値の線形性（命題 6.4［確率］）から $E[X]=\sum_iP(X_i=1)=H_n$ です。

(3) $n=1$ のとき $\log2\le H_1=1\le1+\log1$ は直接わかるので（$\log2\le1$ は $2\le e$ から）、$n\ge2$ とします。$f(x)=\frac1x$ は単調減少なので、和と積分の比較（定理 8.1［積分法］）から $H_n-1=\sum_{k=2}^nf(k)\le\int_1^nf=\log n$、$H_n=\sum_{k=1}^nf(k)\ge\int_1^{n+1}f=\log(n+1)$ です（$\int_1^x\frac{dt}t=\log x$。命題 2.1［積分法］）。

∎

100 人を無作為な順序で見て、「それまでで最高」を更新する回数の期待値は $H_{100}\approx5.19$ です。記録更新は、思ったよりずっと少ない回数でしか起こりません。

6.2. 秘書問題

$n$ 人の応募者に、無作為な順序で 1 人ずつ面接します。面接のたびに、それまでの人との相対的な順位はわかりますが、その場で採用か不採用かを決めなければならず、一度不採用にした人は後から採用できません。最良の 1 人を選びたいとします。次の戦略を考えます。

最初の $r$ 人（$0\le r\le n-1$）は無条件で不採用にし、$r+1$ 人目以降で、それまでの全員より良い人が初めて現れたときに採用する。（そのような人が現れなければ最後の人を採用する。）

この戦略で最良の人を採用できる確率を $p_n(r)$ とします。

定理 6.2（秘書問題）✓

1. $p_n(0)=\dfrac1n$、$1\le r\le n-1$ のとき $p_n(r)=\dfrac rn\displaystyle\sum_{i=r}^{n-1}\frac1i$ である。
2. 最適な $r$ を選んだときの成功確率 $\displaystyle\max_rp_n(r)$ は、$n\to\infty$ で $\dfrac1e$ に収束する。

証明の流れは、(1) で最良の人が $i$ 番目にいる場合ごとに成功する確率を足して $p_n(r)$ の式を得て、(2) でその式を積分ではさんで評価し、下からも上からも $\frac1e$ に近づくことを示す、というものです。

証明（定理 6.2）

(1) $r=0$ は最初の 1 人を採用するので、その人が最良である確率 $\frac1n$ です。$r\ge1$ とする。最良の人が $i$ 番目にいる（確率 $\frac1n$）とします。この戦略がその人を採用するのは、「最初の $i-1$ 人の中の最良の人が、最初の $r$ 人の中にいる」ときです（そうでなければ、$r+1$ 人目から $i-1$ 人目の間で、それまでの最高を更新した人を採用してしまうから）。$i\le r$ のときはそもそも採用されません。$i>r$ のとき、最初の $i-1$ 人の位置は互いに対等なので、その中の最良の人が最初の $r$ 人の中にいる確率は $\frac r{i-1}$ です。$i$ の値ごとの事象は排反なので

$$p_n(r)=\sum_{i=r+1}^n\frac1n\cdot\frac r{i-1}=\frac rn\sum_{i=r}^{n-1}\frac1i$$

です。

(2) 下からの評価。 $f(x)=\frac1x$ は単調減少なので、和と積分の比較（定理 8.1［積分法］）から $\sum_{i=r}^{n-1}\frac1i\ge\int_r^n\frac{dx}x=\log\frac nr$、すなわち $p_n(r)\ge\dfrac rn\log\dfrac nr$ です。$g(x)=x\log\frac1x$ は $(0,1]$ で連続で、$r_n=\lceil n/e\rceil$ に対し $x_n=r_n/n\in\left[\frac1e,\frac1e+\frac1n\right]$ なので $x_n\to\frac1e$、したがって $g(x_n)\to g\left(\frac1e\right)=\frac1e$（連続性。命題 5.5［数列と関数の極限］）です。よって $\max_rp_n(r)\ge p_n(r_n)\ge g(x_n)\to\frac1e$ です。

上からの評価。 $r\ge2$ のとき、同じ比較から $\sum_{i=r}^{n-1}\frac1i\le\int_{r-1}^{n-1}\frac{dx}x=\log\frac{n-1}{r-1}$ です。$y=\frac{r-1}{n-1}\in\left[\frac1{n-1},1\right)$ とおくと、$\frac rn-y=\frac{n-r}{n(n-1)}\le\frac1{n-1}$ なので

$$p_n(r)\le\left(y+\frac1{n-1}\right)\log\frac1y\le y\log\frac1y+\frac{\log(n-1)}{n-1}$$

です。ここで $y\log\frac1y\le\frac1e$（補題 10.1［微分法とその応用］ を $t=\frac1y$ に使う）なので $p_n(r)\le\frac1e+\frac{\log(n-1)}{n-1}$ です。$r=1$ では $p_n(1)=\frac1n\sum_{i=1}^{n-1}\frac1i\le\frac{1+\log n}n$（定理 6.1 (3) より $H_{n-1}\le H_n\le1+\log n$）、$r=0$ では $\frac1n$ です。$\frac{\log m}m\to0$（命題 5.1［微分法とその応用］ (2)）なので、$\max_rp_n(r)\le\frac1e+\varepsilon_n$（$\varepsilon_n\to0$）です。下からの評価とあわせて $\frac1e$ に収束します（はさみうち）。

∎

証明の下からの評価では $r\approx n/e$（約 37%）と取っており、「最初の約 37% は見送り、その後に出る最高を更新した人を採用する」戦略が、この形の戦略の中で（$n\to\infty$ で）最良の成功確率 $\frac1e$ を実現します。他の形の戦略を含めても最良であることは、この記事では扱いません。$n=4$ では $p_4(1)=\frac1{4}\left(1+\frac12+\frac13\right)=\frac{11}{24}\approx0.458$ が最大で、$n$ が大きくなると成功確率は $0.368\cdots=\frac1e$ に近づきます。

7. 二項分布の確率が最大になる回数

命題 7.1（二項分布の最頻値）✓

$0<p<1$、$q=1-p$ とし、$b_k=\binom nkp^kq^{n-k}$（$0\le k\le n$）とする（二項分布。定義 3.1［確率分布と統計的な推測］）。$1\le k\le n$ について

$$\frac{b_k}{b_{k-1}}=\frac{(n-k+1)\,p}{k\,q}$$

で、$b_k>b_{k-1}$ であることは $k<(n+1)p$ と同値、$b_k=b_{k-1}$ であることは $k=(n+1)p$ と同値である。したがって $b_k$ が最大になるのは $k=\lfloor(n+1)p\rfloor$ のとき（$(n+1)p$ が整数のときは、それと $(n+1)p-1$ の 2 つ）である。

証明（命題 7.1）

$\binom nk=\binom n{k-1}\dfrac{n-k+1}k$ から比の式が従います。$b_k\ge b_{k-1}$ は $(n-k+1)p\ge kq$ と同値で、$(n-k+1)p-kq=(n+1)p-k(p+q)=(n+1)p-k$ なので、$k\le(n+1)p$ と同値です（等号は等号と、不等号は不等号と対応する）。したがって $k$ を $0$ から増やしていくと、$k<(n+1)p$ の間 $b_k$ は増加し、$k>(n+1)p$ の間は減少するので、最大値は $k=\lfloor(n+1)p\rfloor$ で取ります。

∎

例 7.2（コインとサイコロ）

公正なコイン $p=\frac12$ を 10 回投げて表が出る回数の最頻値は $\lfloor11\cdot\frac12\rfloor=5$ で、サイコロを 12 回投げて 6 が出る回数（$p=\frac16$）は $\lfloor13/6\rfloor=2$ です。$n=11$、$p=\frac12$ では $(n+1)p=6$ が整数で、$k=5,6$ が同時に最大です（$b_5=b_6=\binom{11}5/2^{11}$）。

8. Penney のゲーム

公正なコインを投げ続け、2 人のプレイヤーが、それぞれ 3 回連続の並び（表 H・裏 T の列）を 1 つずつ選びます。投げ続けて、先に自分の並びが現れたほうが勝ちです。たとえば、あなたが HHT、相手が THH を選ぶと、相手のほうが勝ちやすいのです。

命題 8.1（Penney のゲーム）✓

次の勝つ確率が成り立つ。

1. THH と HHT の勝負：THH が先に現れる確率は $\dfrac34$ である。
2. TTH と THH の勝負：TTH が先に現れる確率は $\dfrac23$ である。
3. HTT と TTH の勝負で HTT が勝つ確率は $\dfrac34$、HHT と HTT の勝負で HHT が勝つ確率は $\dfrac23$ である。

したがって、THH は HHT に、TTH は THH に、HTT は TTH に、HHT は HTT にそれぞれ勝ちやすく、4 つの列は循環しており、「最強の列」は存在しない。

証明（命題 8.1）

決着がつかない確率を押さえます。連続 $2$ 回が「表表」でない確率は、$m$ 回投げて「表表」が現れない確率 $q_m\le(3/4)^{\lfloor m/2\rfloor}\to0$（定理 2.1 (2)）です。以下、無限に続く試行の確率は、有限回で打ち切った確率の $N\to\infty$ の極限で定めます。

(1) 最初の 2 回が HH のとき、最初の T が出る時刻 $j$（$j\ge3$）で HHT が完成するので、HHT が先に現れます（THH は T を含むので、$j$ より前には完成せず、$j$ の T から始まるとしても $j+2$ 以降）。最初の 2 回が HH でないとき、最初に HH が現れる位置を $(j,j+1)$ とすると、$j\ge2$ で、$j-1$ 回目は T です（H なら $j-1,j$ で先に HH が現れる）。よって THH が $j+1$ 回目で完成します。HHT は、HH が $(k,k+1)$（$k\ge j$）にあり、$k+2\ge j+2$ で完成するので、THH のほうが先です。したがって、$N$ 回で打ち切った THH が先に現れる確率は、$\{$最初の 2 回が HH でない$\}$（確率 $\frac34$）に含まれ、決着がついている限りそれに一致します。決着がつかない確率は $N\to\infty$ で $0$（HH が一度も現れないか、最初が HH で後に T が現れない確率が $0$ に収束する）なので、THH が先に現れる確率は $\frac34$ です。

(2) まだ決着していない列の終わり方を 4 つの状態に分けます。S：まだ T が出ていない（投げる前を含む）。A：末尾が T で、その前は T でない。B：末尾が TT。C：末尾が TH。T を含み決着していない列が HH で終わることはない（最後の T の直後に HH が続けば THH が完成している）ので、決着していない列はこの 4 つのどれかに当たります。それぞれの状態から先に $m$ 回投げる間に、TTH が THH より先に現れる確率を $s_m,a_m,b_m,c_m$ とします（$m=0$ はすべて $0$）。次の 1 回で場合分けすると（全確率の公式。定理 5.3［確率］）、$m\ge1$ で

$$s_m=\tfrac12s_{m-1}+\tfrac12a_{m-1},\quad a_m=\tfrac12b_{m-1}+\tfrac12c_{m-1},\quad b_m=\tfrac12b_{m-1}+\tfrac12,\quad c_m=\tfrac12a_{m-1}$$

です。理由：S で H なら S のまま、T なら A。A で T なら B、H なら C。B で H なら TTH が完成して TTH の勝ち（値 $1$）、T なら B のまま。C で H なら THH が完成して THH の勝ち（値 $0$）、T なら A（末尾の T の前は H）です。事象は $m$ とともに大きくなるので、各数列は単調増加で $1$ 以下で、極限 $s,a,b,c$ が存在します（定理 2.1［級数と収束判定］）。漸化式で $m\to\infty$ とすると、$b=\frac12b+\frac12$ から $b=1$、$c=\frac12a$、$a=\frac12b+\frac12c=\frac12+\frac14a$ から $a=\frac23$、$s=\frac12s+\frac12a$ から $s=a=\frac23$ です。投げ始めは状態 S なので、TTH が先に現れる確率は $s=\frac23$ です。決着がつかない確率は、列を 3 回ずつの組に区切ると、どの組も TTH でも THH でもない確率が $\frac34$ なので $\left(\frac34\right)^{\lfloor N/3\rfloor}\to0$ で、THH が先に現れる確率は $1-\frac23=\frac13$ です。

(3) 表と裏を入れ替える対称性により、HTT と TTH の勝負は THH と HHT の勝負（HTT$\leftrightarrow$THH、TTH$\leftrightarrow$HHT）に、HHT と HTT の勝負は TTH と THH の勝負（HHT$\leftrightarrow$TTH、HTT$\leftrightarrow$THH）に対応します。よって (1)(2) の確率がそれぞれ当てはまります。

∎

先に選んだ側は、相手の選んだ列に応じて後から有利な列を選ばれてしまいます。「勝ちやすい」が推移しない（強さに順序がつかない）勝負は、サイコロでも作れます。

例 8.2（非推移的なサイコロ）

3 つのサイコロ A、B、C の目を、A$=\{2,2,4,4,9,9\}$、B$=\{1,1,6,6,8,8\}$、C$=\{3,3,5,5,7,7\}$ とします。A と B を振って A の目が大きい確率は、A の目の値 $2,4,9$ と B の目の値 $1,6,8$ の 9 通りの組（各確率 $\frac19$）のうち、$2>1$、$4>1$、$9>1$、$9>6$、$9>8$ の 5 つなので $\frac59$ です。同様に B が C に勝つ確率（$6>3,6>5,8>3,8>5,8>7$）が $\frac59$、C が A に勝つ確率（$3>2,5>2,5>4,7>2,7>4$）が $\frac59$ です。A は B に、B は C に、C は A にそれぞれ $\frac59$ の確率で勝つので、3 つのサイコロの強さは循環しています。

9. 幾何確率と Buffon の針

9.1. 面積による確率

有限確率空間では、結果が有限個なので「同様に確からしい」確率は個数の比でした。結果が連続的に変化する場合（針の位置・角度、待ち合わせの時刻）では、その代わりに面積の比を使います。

定義 9.1（幾何確率）↗

平面の有界な領域 $\Omega$ が面積確定で $|\Omega|>0$ とする。$\Omega$ の中から無作為に（一様に）点を選ぶとき、面積確定な部分集合 $A\subseteq\Omega$ に点が入る確率を $P(A)=\dfrac{|A|}{|\Omega|}$ と定める。ここで $|\cdot|$ は面積（定義 5.1［重積分と累次積分］）である。

面積は、互いに交わらない図形について加法的で、$|\Omega|$ で割ると全体が $1$ になるので、有限確率空間と同じ形の性質（加法定理・余事象の確率）を持ちます。

例 9.2（待ち合わせ）

2 人が 12 時から 13 時までの間の無作為な時刻 $s,t$（分、$0\le s,t\le60$）に着き、$15$ 分以上待たずに帰るとします。会える条件は $|s-t|\le15$ で、会えない領域は 2 つの直角二等辺三角形（脚の長さ $45$）です。面積は $2\cdot\frac12\cdot45^2=2025$ で、全体の面積 $60^2=3600$ との比から、会える確率は $1-\dfrac{2025}{3600}=\dfrac7{16}$ です。

9.2. Buffon の針

平行な直線が間隔 $d$ で引かれた平面に、長さ $l$（$l\le d$）の針を無作為に落とします。針が直線のどれかと交わる確率を求めます。

針の位置は、針の中心から最も近い直線までの距離 $x\in\left[0,\frac d2\right]$ と、針が直線となす鋭角 $\theta\in\left[0,\frac\pi2\right]$ で決まります。針を落とす（中心の位置と向きを無作為に決める）とは、組 $(\theta,x)$ が長方形 $\Omega=\left[0,\frac\pi2\right]\times\left[0,\frac d2\right]$ の中から一様に選ばれる、ということです（対称性により、中心の位置と向きの全体を、この長方形に帰着できる）。

定理 9.3（Buffon の針）✓

$l\le d$ とする。針が直線と交わる確率は

$$\frac{2l}{\pi d}$$

である。

証明（定理 9.3）

針の中心から直線への距離が $x$、角が $\theta$ のとき、針の端の直線への垂直方向の距離の最大は $\frac l2\sin\theta$ で、針が直線と交わるのは $x\le\frac l2\sin\theta$ のときです。事象 $A=\left\{(\theta,x):0\le\theta\le\frac\pi2,\ 0\le x\le\frac l2\sin\theta\right\}$ は、$\frac l2\sin\theta\le\frac l2\le\frac d2$ なので $\Omega$ に含まれ、$\theta$ を独立変数としたとき、連続関数 $0$ と $\frac l2\sin\theta$ に挟まれた図形です。定理 2.2［積分の応用］ から面積は $\displaystyle|A|=\int_0^{\pi/2}\frac l2\sin\theta\,d\theta=\frac l2\bigl[-\cos\theta\bigr]_0^{\pi/2}=\frac l2$（命題 2.1［積分法］）です。全体の面積は $|\Omega|=\frac\pi2\cdot\frac d2=\frac{\pi d}4$ なので、定義 9.1 から $P(A)=\dfrac{l/2}{\pi d/4}=\dfrac{2l}{\pi d}$ です。

∎

$l=d$ なら確率は $\frac2\pi=0.6366\cdots$ で、$n$ 回投げて $k$ 回直線と交わったなら、$\pi\approx\dfrac{2ln}{dk}$ と見積もれます。コンピュータで実験すると次のようになります。針の向きは、単位円板の中の一様な点から決めて（$\pi$ を使わずに）います。

import math
import random

def buffon(n, l=1.0, d=1.0):
    hits = 0
    for _ in range(n):
        x = random.uniform(0, d / 2)          # 針の中心から最も近い線までの距離
        while True:                            # 単位円板内の一様な点で針の向きを決める
            u, v = random.uniform(-1, 1), random.uniform(-1, 1)
            r2 = u * u + v * v
            if 0 < r2 <= 1:
                break
        s = abs(v) / math.sqrt(r2)             # 針が線となす角の正弦 sin(theta)
        if x <= (l / 2) * s:
            hits += 1
    return 2 * l * n / (d * hits)

print(buffon(10**6))   # 3.14 付近の値（乱数なので実行ごとに変わる）

10. 大学ではどこへ続くか

• マルコフ連鎖。 破産問題やランダムウォークは、状態が遷移確率で動くマルコフ連鎖の最も簡単な例です。停止時刻・再帰性・到達確率は マルコフ連鎖とポアソン過程 で一般論になります。
• マルチンゲールと停止時刻。 公平な賭けの持ち金はマルチンゲールで、破産問題の答え $a/N$ は「停止時刻でも期待値が保たれる」ことの帰結です。
• Brown 運動。 ランダムウォークの歩幅と時間間隔を小さくした極限が Brown 運動で、最後に原点にいた時刻の分布（離散の逆正弦法則）は、連続の逆正弦法則に変わります。
• 確率空間と測度。 無限回の試行を扱う確率空間（Kolmogorov の公理）は 確率空間 で、この記事の「打ち切りの極限」は、測度の連続性として一般に定式化されます。
• 組合せ論・母関数。 Catalan 数・鏡像原理は 母関数による数え上げ の対象です。この記事の漸化式（$q_m=\frac12q_{m-1}+\frac14q_{m-2}$）は、漸化式と母関数 の特性方程式でも解けます。

11. 演習

演習 11.1標準

公正なコインを投げ続け、裏が 3 回連続して出るまでの回数を $T$ とする。$E[\min(T,N)]$ の $N\to\infty$ の極限を、定理 2.1 (2) と同様にして求めよ。

解答

$q_m$ を「$m$ 回投げて裏が 3 回連続しない確率」とする（$q_0=q_1=q_2=1$）。最後の連続する裏の個数で場合分けして $q_m=\frac12q_{m-1}+\frac14q_{m-2}+\frac18q_{m-3}$（$m\ge3$）である。$E[\min(T,N)]=\sum_{m=0}^{N-1}q_m$ で、各項は $0$ 以上、$q_{3j}\le\left(\frac78\right)^j$ で抑えられるので収束する。和を $Q$ とし、漸化式を $m\ge3$ で足すと $Q-3=\frac12(Q-2)+\frac14(Q-1)+\frac18Q$ で、$\frac18Q=\frac74$、$Q=14$ である。

演習 11.2易

$f_4$ を 定理 4.4 で求め、4 歩の経路を数え上げて確かめよ。

解答

$f_4=\dfrac{C_1}{2^3}=\dfrac18$。4 歩の経路 $2^4=16$ 通りのうち、$S_4=0$ かつ $S_1,S_2,S_3\ne0$ となるのは $++--$ と $--++$ の 2 通り（$+-\dots$ は $S_2=0$）なので $\frac2{16}=\frac18$ である。

演習 11.3標準

$n=4$ の秘書問題で、$p_4(r)$（$r=0,1,2,3$）を求めて最適な $r$ を答えよ。

解答

定理 6.2 (1) から $p_4(0)=\frac14$、$p_4(1)=\frac14\left(1+\frac12+\frac13\right)=\frac{11}{24}$、$p_4(2)=\frac24\left(\frac12+\frac13\right)=\frac5{12}=\frac{10}{24}$、$p_4(3)=\frac34\cdot\frac13=\frac14$ である。最大は $r=1$ のときの $\frac{11}{24}\approx0.458$ である。

参考文献

• W. Feller, An Introduction to Probability Theory and Its Applications, Vol. I, 3rd ed., Wiley, 1968 — ランダムウォーク・破産問題・Banach のマッチ箱問題の章。
• 小針晛宏『確率・統計入門』岩波書店、1973 — 確率の基本。
• T. S. Ferguson, “Who solved the secretary problem?”, Statistical Science 4 (1989), 282–289 — 秘書問題の歴史と解。
• W. Penney, “Problem 95: Penney-ante”, Journal of Recreational Mathematics 7 (1974), 321 — Penney のゲームの出題。