# 確率の発展：漸化式・破産問題・ランダムウォーク・秘書問題・Buffon の針 > 停止までの回数の期待値と破産問題を漸化式で解き、ランダムウォークの鏡像原理・初回帰時刻・離散逆正弦法則を証明する。Pólya の壺・マッチ箱・記録・秘書問題・Penney のゲーム・Buffon の針も扱う。 > https://rikai.mugen-giken.com/mathematics/hs-probability/probability-topics ## 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. 動機：確率の問題を「解く」と「証明する」の間 高校の確率の発展的な問題は、次のように解かれます。 - 「サイコロを振って 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$ なら、この方程式から何もわかりません。また、無限回続く試行の確率は、前の記事で定義した[**有限確率空間**](/mathematics/hs-probability/finite-probability#def-finite-probability-space)（標本空間が有限集合）の範囲を超えます。 この記事の方針は、**$M$ 回で打ち切った有限の確率空間で答えを求め、$M\to\infty$ とする**ことです。打ち切りの確率の増え方が単調で上に有界なら、極限が存在します（単調有界定理。）。極限を取った式が漸化式を満たすことから、答えを決めます。この「打ち切りの極限」が、高校で使っている漸化式の立式を正当化します。 使う道具は、前の記事の有限確率空間（）、直積空間と独立（）、条件付き確率と全確率の公式（）、期待値の線形性・指示関数の方法（、）と、場合の数の記事の組合せの数（）、最短経路の数（）です。 ## 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)$ だから）。指示関数の方法（）から、 $$ E\bigl[\min(T,N)\bigr]=\sum_{k=1}^NP(T\ge k) $$ です。この式を使うと、「期待値が有限か」「いくつか」を、確率の和の問題として扱えます。 ### 2.2. 最初の成功までと、連続 2 回の成功まで 1. 成功確率 $p$（$0 **(1)** $q=1-p$ とする。$T\ge k$ は「最初の $k-1$ 回がすべて失敗」で、直積空間の性質（）から $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$（）なので、$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$ に収束します（）。したがって $\sum q_m$ は等比級数で抑えられ、有界で単調増加なので収束します（）。和を $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 $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$ を限りなく遠くしたときの様子です。 **(1)** どの $a$ から出発しても、続けて $N$ 回勝てば（確率 $p^N$）、$N$ 回以内に目標に到達します。したがって $M$ 回までに決着していない確率 $D_M(a)$ について $D_N(a)\le1-p^N$ です。$d_M=\max_aD_M(a)$ とおく。最初の $N$ 回の結果で場合分けして（全確率の公式。）、$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\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$。）です。$p<\frac12$ ならば $r>1$ で、$R(a)=\dfrac{r^a-1}{r^N-1}\to0$（分母 $\to\infty$）、$p=\frac12$ では $\dfrac aN\to0$ なので、破産確率は $1$ に収束します。 **公平な賭け**（$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$ 通りで、同様に確からしい。）で、$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$。）。$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}$）。 整数 $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$ である。 上がる歩を $k$ 回とすると、下がる歩は $m-k$ 回で、$a+k-(m-k)=b$、すなわち $k=\frac{m+b-a}2$ です。上がる歩の位置を選ぶ選び方が $\binom mk$ 通りです（）。 ### 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$ の経路になります。 $\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)$ です。
a −a b τ 時刻
### 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 にいる経路」の個数と同じになる、という意外な事実を述べています。証明では、すべて正の経路を鏡像原理で数えます。和の各項の後半が次の項の前半と打ち消し合うので、最初の前半と最後の後半だけが残ります。 $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$）です。鏡像原理（）から、高さ $1$ から $2j$ へ $0$ に触れずに行く経路の個数は $N_{2n-1}(1\to2j)-N_{2n-1}(-1\to2j)=\binom{2n-1}{n+j-1}-\binom{2n-1}{n+j}$ です（）。したがって $$ 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 の漸化式と対称性（）から $\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. 初めて原点に戻る時刻 $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 数である。 $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}$（。$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}$ です。 $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}$ とします。 $0\le k\le n$ について $$ P(L_{2n}=2k)=u_{2k}\,u_{2n-2k} $$ である。とくに $\displaystyle\sum_{k=0}^nu_{2k}u_{2n-2k}=1$。 $L_{2n}=2k$ は、$S_{2k}=0$ かつ $S_j\ne0$（$2k2k$ では $S_j$ は残りの歩の部分和（$S_{2k}=0$ なので）です。したがって事象は「最初の $2k$ 歩で $S_{2k}=0$」と「残りの $2n-2k$ 歩で、部分和が一度も $0$ にならない」の積事象で、独立なので確率は $u_{2k}\cdot u_{2n-2k}$ です（後者は 。$2n-2k=0$ のときは $u_0=1$）。事象 $\{L_{2n}=2k\}$（$k=0,\dots,n$）は互いに排反で全体を覆うので、確率の和は $1$ です。 $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. ウォークは原点に戻るか $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$ に発散する。 **(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}$（）で、(1) から $u_{2n}\le\dfrac1{\sqrt{2n+1}}\to0$ です。 **(3)** 時刻 $2n$ に原点にいる事象の指示関数の和の期待値は、指示関数の方法（）から $\sum_{n=1}^Nu_{2n}$ です。(1) と、単調減少関数 $f(x)=\frac1{2\sqrt x}$ についての和と積分の比較（）から $\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 の公式（）を使うと、$u_{2n}\sim\dfrac1{\sqrt{\pi n}}$ という精密な評価が得られます。 ## 5. 壺とマッチ箱 ### 5.1. Pólya の壺 壺に赤玉 1 個と青玉 1 個が入っています。次の操作を $n$ 回繰り返します。壺から玉を 1 個無作為に取り出し、色を見て、その玉と**同じ色の玉をもう 1 個**足して戻す（壺の玉が 1 個増える）。「赤い玉を取り出した回数」が $k$ になる確率を求めます。 $n$ 回の結果の列（赤 R、青 B の列）の確率は、条件付き確率の積（乗法定理。）で決まります。$j$ 回目の取り出しの前には壺に $j+1$ 個の玉があります。 赤 1 個、青 1 個から始めて $n$ 回繰り返したとき、赤い玉を取り出した回数がちょうど $k$ である確率は、すべての $k=0,1,\dots,n$ について $\dfrac1{n+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$ 通りあり（）、互いに排反なので、$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$ とします。 $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$。 「左の箱が空と気づき、右の箱に $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)}$ です（選択は独立。）。右の箱が空と気づく事象も対称で同じ確率なので、$P(K=k)=2P(A_k)=\binom{2N-k}N2^{-(2N-k)}$ です。最後の等式は、どちらかの箱が必ず（選択を $2N+1$ 回行うまでに）空に気づかれるので、$K\in\{0,\dots,N\}$ の確率の和が $1$ であることから従います。 $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$）とします。 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$ である。 **(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)** 指示関数の方法と期待値の線形性（）から $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$ は単調減少なので、和と積分の比較（）から $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$。）。 100 人を無作為な順序で見て、「それまでで最高」を更新する回数の期待値は $H_{100}\approx5.19$ です。記録更新は、思ったよりずっと少ない回数でしか起こりません。 ### 6.2. 秘書問題 $n$ 人の応募者に、無作為な順序で 1 人ずつ面接します。面接のたびに、それまでの人との**相対的な順位**はわかりますが、その場で採用か不採用かを決めなければならず、一度不採用にした人は後から採用できません。最良の 1 人を選びたいとします。次の戦略を考えます。 > 最初の $r$ 人（$0\le r\le n-1$）は無条件で不採用にし、$r+1$ 人目以降で、**それまでの全員より良い人が初めて現れたときに採用する**。（そのような人が現れなければ最後の人を採用する。） この戦略で最良の人を採用できる確率を $p_n(r)$ とします。 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$ に近づくことを示す、というものです。 **(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$ は単調減少なので、和と積分の比較（）から $\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$（連続性。）です。よって $\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$（ を $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$（ (3) より $H_{n-1}\le H_n\le1+\log n$）、$r=0$ では $\frac1n$ です。$\frac{\log m}m\to0$（ (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. 二項分布の確率が最大になる回数 $0）。$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 つ）である。 $\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$ で取ります。 公正なコイン $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 を選ぶと、相手のほうが勝ちやすいのです。 次の勝つ確率が成り立つ。 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 つの列は**循環**しており、「最強の列」は存在しない。 決着がつかない確率を押さえます。連続 $2$ 回が「表表」でない確率は、$m$ 回投げて「表表」が現れない確率 $q_m\le(3/4)^{\lfloor m/2\rfloor}\to0$（ (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 回で場合分けすると（全確率の公式。）、$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$ が存在します（）。漸化式で $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) の確率がそれぞれ当てはまります。 先に選んだ側は、相手の選んだ列に応じて**後から**有利な列を選ばれてしまいます。「勝ちやすい」が推移しない（強さに順序がつかない）勝負は、サイコロでも作れます。 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. 面積による確率 有限確率空間では、結果が有限個なので「同様に確からしい」確率は個数の比でした。結果が連続的に変化する場合（針の位置・角度、待ち合わせの時刻）では、その代わりに**面積の比**を使います。 平面の有界な領域 $\Omega$ が面積確定で $|\Omega|>0$ とする。$\Omega$ の中から無作為に（一様に）点を選ぶとき、面積確定な部分集合 $A\subseteq\Omega$ に点が入る確率を $P(A)=\dfrac{|A|}{|\Omega|}$ と定める。ここで $|\cdot|$ は面積（）である。 面積は、互いに交わらない図形について加法的で、$|\Omega|$ で割ると全体が $1$ になるので、有限確率空間と同じ形の性質（加法定理・余事象の確率）を持ちます。 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]$ の中から一様に選ばれる、ということです（対称性により、中心の位置と向きの全体を、この長方形に帰着できる）。 $l\le d$ とする。針が直線と交わる確率は $$ \frac{2l}{\pi d} $$ である。 針の中心から直線への距離が $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$ に挟まれた図形です。 から面積は $\displaystyle|A|=\int_0^{\pi/2}\frac l2\sin\theta\,d\theta=\frac l2\bigl[-\cos\theta\bigr]_0^{\pi/2}=\frac l2$（）です。全体の面積は $|\Omega|=\frac\pi2\cdot\frac d2=\frac{\pi d}4$ なので、 から $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$ を使わずに）います。 ```python 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. 大学ではどこへ続くか - **マルコフ連鎖。** 破産問題やランダムウォークは、状態が遷移確率で動く**マルコフ連鎖**の最も簡単な例です。停止時刻・再帰性・到達確率は [マルコフ連鎖とポアソン過程](/mathematics/probability/markov-chains-poisson) で一般論になります。 - **マルチンゲールと停止時刻。** 公平な賭けの持ち金は**マルチンゲール**で、破産問題の答え $a/N$ は「停止時刻でも期待値が保たれる」ことの帰結です。 - **Brown 運動。** ランダムウォークの歩幅と時間間隔を小さくした極限が Brown 運動で、最後に原点にいた時刻の分布（離散の逆正弦法則）は、連続の**逆正弦法則**に変わります。 - **確率空間と測度。** 無限回の試行を扱う確率空間（Kolmogorov の公理）は [確率空間](/mathematics/probability/probability-spaces) で、この記事の「打ち切りの極限」は、測度の連続性として一般に定式化されます。 - **組合せ論・母関数。** Catalan 数・鏡像原理は [母関数による数え上げ](/mathematics/combinatorics/enumeration-generating-functions) の対象です。この記事の漸化式（$q_m=\frac12q_{m-1}+\frac14q_{m-2}$）は、[漸化式と母関数](/mathematics/hs-algebra/recurrences-generating-functions) の特性方程式でも解けます。 ## 11. 演習 公正なコインを投げ続け、裏が 3 回連続して出るまでの回数を $T$ とする。$E[\min(T,N)]$ の $N\to\infty$ の極限を、 (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$ である。 $f_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$ である。 $n=4$ の秘書問題で、$p_4(r)$（$r=0,1,2,3$）を求めて最適な $r$ を答えよ。 (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 のゲームの出題。