乱択アルゴリズム徹底解説：計算量を劇的に改善する「ランダム性」の力

Quick Select アルゴリズムの平均計算量が \(O(N)\) であることを、再帰的な期待実行時間の漸化式を用いて厳密に証明します。

配列のサイズを \(N\) とします。目標は、この配列の \(K\) 番目に小さい要素を見つけることです。

Quick Select のステップは以下の通りです。
1. 配列の中から要素を一つ、ランダムに選び、これをピボットとします。
2. ピボットを使って配列を分割 (partition) します。ピボットより小さい要素をピボットの左に、ピボットより大きい要素をピボットの右に集めます。ピボット自身は正しい位置に置かれます。この分割操作にかかる時間は配列のサイズに比例し、\(O(N)\) です。
3. ピボットが全体で \(k\) 番目に小さい要素であると分かったとします（ピボットの順位が \(k\))。
4. もし \(K = k\) なら、ピボットが求めていた要素です。アルゴリズムは終了します。
5. もし \(K < k\) なら、求めている \(K\) 番目の要素はピボットより小さい要素のグループ（サイズ \(k-1\)) の中にあります。このグループに対して再帰的に Quick Select を呼び出し、\(K\) 番目に小さい要素を探します。
6. もし \(K > k\) なら、求めている \(K\) 番目の要素はピボットより大きい要素のグループ（サイズ \(N-k\)) の中にあります。このグループに対して再帰的に Quick Select を呼び出し、そのグループの中で \((K-k)\) 番目に小さい要素を探します。

Quick Select の計算量は、主に分割操作にかかる時間です。各再帰呼び出しで、新しい（より小さい）配列に対して分割を行います。全体の計算量は、これらの分割操作にかかる時間の合計です。

\(T(N)\) を、サイズ \(N\) の配列に対して Quick Select が必要とする期待実行時間とします。
ステップ1とステップ2にかかる時間は \(O(N)\) です。これはある定数 \(c\) を用いて \(cN\) 以下で抑えられるとします。
ステップ3以降は、ピボットの順位 \(k\) に依存する再帰呼び出しです。ピボットは配列からランダムに選ばれるので、その順位 \(k\) は 1 から \(N\) までのいずれかを取り得ます。ピボットが \(N\) 個の要素の中からランダムに選ばれる場合、各要素がピボットになる確率は \(1/N\) です。そして、もし特定の要素がピボットに選ばれた場合、その要素の順位は配列をソートしたときの順位と一致します。したがって、ピボットの順位が \(k\) である確率も \(1/N\) です（\(k=1, 2, \ldots, N\))。

ピボットの順位が \(k\) である場合の、再帰呼び出しの期待コストは、その次に解くべき部分問題のサイズに依存します。
- ピボットの順位が \(k\)，かつ \(K = k\) の場合：終了。再帰なし。コスト \(O(1)\)。
- ピボットの順位が \(k\)，かつ \(K < k\) の場合：サイズ \(k-1\) の部分問題に対して Quick Select を解く。期待コスト \(T(k-1)\)。
- ピボットの順位が \(k\)，かつ \(K > k\) の場合：サイズ \(N-k\) の部分問題に対して Quick Select を解く。期待コスト \(T(N-k)\)。

\(T(N)\) に関する漸化式は、ピボットの順位 \(k\) の全ての可能性に対する期待値を平均して求められます。
$$T(N) = O(N) + \sum_{k=1}^{N} \frac{1}{N} \times \begin{cases} O(1) & \text{if } K = k \\ T(k-1) & \text{if } K < k \\ T(N-k) & \text{if } K > k \end{cases}$$
簡単のため、\(O(N)\) 項を \(cN\) とし、\(O(1)\) 項は \(cN\) に吸収されるほど小さいと見なせます。また、\(K\) は固定された値ですが、漸化式を単純化するために、最悪の場合の再帰サイズを考えます。ピボットの順位が \(k\) のとき、次に解く部分問題のサイズは \(\max(k-1, N-k)\) 以下です。この最大サイズに対する期待時間を上界として考えます。
$$T(N) \le cN + \sum_{k=1}^{N} \frac{1}{N} T(\max(k-1, N-k))$$
ここで、\(T(0)\) はベースケースであり、\(O(1)\) です（例えば \(T(0)=c_0\) とします）。

和の項を評価します。\(k\) が 1 から \(N\) まで変化するとき、\(\max(k-1, N-k)\) は \(N-1, N-2, \ldots, \max(\lfloor N/2 \rfloor-1, N-\lfloor N/2 \rfloor), \ldots, N-2, N-1\) という値をとります。
具体的には、\(\max(k-1, N-k) = j\) となるのは、\(k-1=j\) か \(N-k=j\) の場合です。
\(k = j+1\) のとき、\(N-k = N-(j+1) = N-j-1\) です。このとき \(\max(j, N-j-1)\) となります。
\(N-k = j\) のとき、\(k = N-j\) です。このとき \(\max(N-j-1, j)\) となります。
したがって、サイズ \(j\) の部分問題が発生する可能性があるのは、ピボットの順位 \(k-1\) が \(j\) になるか、ピボットの順位 \(N-k\) が \(j\) になる場合です。

より単純に、\(\max(k-1, N-k)\) の値 \(j\) は、\(k\) が \(1\) や \(N\) に近いときは \(N-1\) に近く、\(k\) が \(N/2\) に近いときは \(N/2\) に近くなります。
和 \(\sum_{k=1}^{N} T(\max(k-1, N-k))\) は、\(\max(k-1, N-k)\) の値が小さい項から並べ替えると、大体 \(2 \sum_{j=\lfloor N/2 \rfloor}^{N-1} T(j)\) となります（\(j \ge \lfloor N/2 \rfloor\) となる各サイズ \(j\) は、おおよそ2つの \(k\) の値に対応するため）。

したがって、漸化式は次のように近似できます。
$$T(N) \le cN + \frac{2}{N} \sum_{j=\lfloor N/2 \rfloor}^{N-1} T(j)$$
ここで、この漸化式が \(T(N) \le aN\) という線形な解を持つことを、代入法（または帰納法）で示します。ある定数 \(a\) が存在して、全ての \(j < N\) に対して \(T(j) \le aj\) が成り立つと仮定します。この仮定が \(T(N)\) でも成り立つような \(a\) を見つけます。
$$T(N) \le cN + \frac{2}{N} \sum_{j=\lfloor N/2 \rfloor}^{N-1} aj$$
$$T(N) \le cN + \frac{2a}{N} \sum_{j=\lfloor N/2 \rfloor}^{N-1} j$$
和 \(\sum_{j=\lfloor N/2 \rfloor}^{N-1} j\) を評価します。これは、約 \(N/2\) 個の項を持つ等差数列の和であり、項の値は \(\lfloor N/2 \rfloor\) から \(N-1\) までです。
この和は、積分 \(\int_{N/2}^{N} x \, dx\) で上から近似できます。
$$ \sum_{j=\lfloor N/2 \rfloor}^{N-1} j \le \int_{\lfloor N/2 \rfloor}^{N} x \, dx \le \int_{N/2}^{N} x \, dx = \left[ \frac{x^2}{2} \right]_{N/2}^{N} = \frac{N^2}{2} - \frac{(N/2)^2}{2} = \frac{N^2}{2} - \frac{N^2}{8} = \frac{3N^2}{8} $$
（厳密には、和と積分の関係でもう少し正確な評価が必要ですが、ここではオーダーを示すための簡略化としてこれを用います。）
したがって、
$$T(N) \le cN + \frac{2a}{N} \left( \frac{3N^2}{8} \right) = cN + \frac{3aN}{4}$$
我々は \(T(N) \le aN\) となるような \(a\) を見つけたいので、
$$aN \ge cN + \frac{3aN}{4}$$
$$aN - \frac{3aN}{4} \ge cN$$
$$\frac{aN}{4} \ge cN$$
$$a \ge 4c$$
\(a\) を \(4c\) 以上の任意の定数として選べば（例えば \(a = 4c\))、帰納法の仮定が \(N\) に対しても成り立ちます。ベースケース \(T(0)=c_0\) や \(T(1)\) などに対して \(T(N) \le aN\) が成り立つように、十分に大きな \(a\) を選んでおく必要があります（例えば \(a = \max(4c, T(1)/1, T(0)/0 \text{ if N>0})\) のように）。

この証明により、Quick Select の期待計算時間は \(O(N)\) であることが厳密に示されました。これは、ランダムなピボット選択によって、最悪ケースになりうるピボットが選ばれる確率が低く、平均的には問題のサイズが十分に小さくなるためです。特に、漸化式における和の項が \(1/N\) 倍されることが重要であり、これにより線形な結合で抑えられます。

「平均して定数倍に縮小する」という表現は、厳密には「次に再帰呼び出しされる部分問題のサイズの期待値が、元のサイズの定数倍以下になる」という意味ではありません。実際、\(E[\max(k-1, N-k)]\) は \(N\) に近い値になります。しかし、全ての可能な再帰サイズの期待値の和が、\(N\) に対して線形になることが、この \(O(N)\) の期待計算時間を保証するのです。□

ここまでで、配列を一様ランダム順列にする手続き RANDOMLY-PERMUTE を紹介しました。これは swap A[i] with A[RANDOM(i, n)] という交換を i を 1 から n まで繰り返すものでした。この手続きが一様ランダム順列を生成することは、ループ不変式を使って証明しました。

ここでは、似ているけれども一様ランダム順列を生成できない失敗する手続きを見て、なぜ RANDOMLY-PERMUTEの設計が重要なのかをさらに深く理解します。

この手続きが、一様ランダム順列を生成しないことを示しましょう。考えられる全ての \(n!\) 通りの順列が、どれも等しい確率 \(1 / n!\) で生成されるならば、一様ランダム順列です。しかし、PERMUTE－ WITH－ALL ではそうなりません。

n=3 の場合で検証

要素が 3 つの配列 \(A=[1,2,3]\) を考えます。考えられる順列は \(3!=6\) 通りです：\([1,2,3]\) ，\([1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]\) 。一様ランダムであれば、それぞれの順列が生成される確率は \(1 / 6\) になるはずです。

PERMUTE－WITH－ALL を実行すると、i が \(1,2,3\) と変化します。各ステップで RANDOM（1，3）が呼 ばれ、これは \(1,2,3\) のいずれかを確率 \(1 / 3\) で返します。全部で 3 ステップあり、各ステップが独立なので、考えられるランダムな選択のシーケンス（例えば「ステップ1でRANDOMが1、ステッ プ2でRANDOMが2、ステップ3でRANDOMが1」のような組み合わせ）は \(3 \times 3 \times 3=27\) 通りあり ます。これらの 27 通りのシーケンスは、それぞれが等しい確率 \(1 / 27\) で発生します。

各ランダムな選択のシーケンスが、最終的にどの順列を生成するかを追跡してみましょう。元の配列を \([1,2,3]\) とします。

上記の追跡（または正確な計算）によると、各最終順列が生成される確率は以下のようになります。

$$
\begin{aligned}
& {[1,2,3]: 5 \text { 回 }\left(k_1=1, k_2=2, k_3=3 ; k_1=1, k_2=3, k_3=2 ; k_1=2, k_2=1, k_3=3 ;\right.} \\
& \left.k_1=2, k_2=3, k_3=1 ; k_1=3, k_2=1, k_3=2 ; k_1=3, k_2=2, k_3=1\right) \\
& [1,3,2]: 4 \text { 回 } \\
& [2,1,3]: 4 \text { 回 } \\
& [2,3,1]: 4 \text { 回 } \\
& [3,1,2]: 5 \text { 回 } \\
& [3,2,1]: 5 \text { 回 }
\end{aligned}
$$

したがって、各順列が生成される確率は以下の通りです（合計 27）：

$$
\begin{aligned}
& \Pr\{[1,2,3]\}=5 / 27 \\
& Pr\{[1,3,2]\}=4 / 27 \\
&Pr\{[2,1,3]\}=4 / 27 \\
& Pr\{[2,3,1]\}=4 / 27 \\
& Pr\{[3,1,2]\}=5 / 27 \\
& Pr\{[3,2,1]\}=5 / 27
\end{aligned}
$$

これらの確率は全て等しいわけではありません（例えば \(5 / 27 \neq 1 / 6\) ）。したがって、PERMUTE－ WITH－ALL は一様ランダム順列を生成しません。□

指示確率変数と期待値の定義によれば、確率変数 \(X_A\) が取りうる値は1（事象 \(A\) が発生する場合）と0（事象 \(A\) が発生しない場合）の2つだけです。事象 \(A\) が発生する確率は \(\operatorname{Pr}\{A\}\) 、発生しない確率（余事象 \(\bar{A}\) が発生する確率）は \(\operatorname{Pr}\{\bar{A}\}=1-\operatorname{Pr}\{A\}\) です。期待値の定義（確率変数が取りうる値とそ の確率の積の総和）より、

$$
E\left[X_A\right]=1 \cdot \operatorname{Pr}\{A\}+0 \cdot \operatorname{Pr}\{\bar{A}\}=\operatorname{Pr}\{A\}+0=\operatorname{Pr}\{A\}
$$

したがって、 \(E\left[X_A\right]=\operatorname{Pr}\{A\}\) です。□

自然数 \(n\) に対する**調和級数 (Harmonic Series)** \(H_n\) は、以下のように定義されます。
\[
H_n = \sum_{i=1}^n \frac{1}{i} = 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}
\] この調和級数は、\(n \to \infty\) のときに発散します。そして、その増加の度合いは自然対数 \(\ln n\) と密接に関係しており、差が定数に収束することが知られています。その関係式は以下の通りです。
\[
\sum_{i=1}^n \frac{1}{i} = \ln n + O(1)
\] ここで \(O(1)\) は、\(n \to \infty\) のときに有界となる項を表します。つまり、調和級数と \(\ln n\) の差 \(\sum_{i=1}^n \frac{1}{i} - \ln n\) は、\(n \to \infty\) のときに何らかの定数（オイラー・マスケローニ定数 \(\gamma \approx 0.57721\)）に収束します。

この関係を厳密に証明するために、積分の考え方を用います。関数 \(f(x) = 1/x\) を考えます。この関数は \(x > 0\) で正、単調減少です。

シグマ \(\sum_{i=1}^n \frac{1}{i}\) は、長方形の面積の合計と見なすことができます。区間 \([i, i+1]\) 上で高さ \(1/i\) の長方形（左端での関数の値を取る）を考えると、その面積は \(1/i \times (i+1 - i) = 1/i\) です。これを \(i=1\) から \(n\) まで合計すると、\(\sum_{i=1}^n \frac{1}{i}\) となります。これは、関数 \(f(x) = 1/x\) のグラフよりも**上**に位置する長方形の面積の合計です。

一方、\(i=1\) から \(n\) までの定積分 \(\int_1^n \frac{1}{x} dx\) は、関数 \(f(x) = 1/x\) のグラフの下の面積を表します。
\[
\int_1^n \frac{1}{x} dx = [\ln |x|]_1^n = \ln n - \ln 1 = \ln n
\]

さて、\(f(x) = 1/x\) が単調減少関数であることを利用すると、以下の不等式が成り立ちます。

区間 \([i, i+1]\) において、
- 左端の高さ \(1/i\) を持つ長方形の面積は \(1/i\) です。これは、この区間での積分の値 \(\int_i^{i+1} \frac{1}{x} dx\) よりも**大きい**です（関数が減少しているため）。
\[
\frac{1}{i} \ge \int_i^{i+1} \frac{1}{x} dx \quad \text{for } i \ge 1
\] - 右端の高さ \(1/(i+1)\) を持つ長方形の面積は \(1/(i+1)\) です。これは、この区間での積分の値 \(\int_i^{i+1} \frac{1}{x} dx\) よりも**小さい**です（関数が減少しているため）。
\[
\frac{1}{i+1} \le \int_i^{i+1} \frac{1}{x} dx \quad \text{for } i \ge 1
\]

これらの不等式を \(i=1\) から \(n-1\) まで（または \(n\) まで）合計してみましょう。

まず、\(1/i \ge \int_i^{i+1} \frac{1}{x} dx\) の不等式を \(i=1\) から \(n-1\) まで合計します。
\[
\sum_{i=1}^{n-1} \frac{1}{i} \ge \sum_{i=1}^{n-1} \int_i^{i+1} \frac{1}{x} dx
\] 和記号と積分記号は交換できます（積分の線形性）。また、連続する区間での積分の合計は、大きな区間での積分になります。
\[
\sum_{i=1}^{n-1} \int_i^{i+1} \frac{1}{x} dx = \int_1^2 \frac{1}{x} dx + \int_2^3 \frac{1}{x} dx + \cdots + \int_{n-1}^n \frac{1}{x} dx = \int_1^n \frac{1}{x} dx = \ln n
\] したがって、
\[
\sum_{i=1}^{n-1} \frac{1}{i} \ge \ln n
\] この和に最後の項 \(1/n\) を加えると、
\[
\sum_{i=1}^n \frac{1}{i} = \left( \sum_{i=1}^{n-1} \frac{1}{i} \right) + \frac{1}{n} \ge \ln n + \frac{1}{n}
\] これは、\(\sum_{i=1}^n \frac{1}{i}\) が \(\ln n\) より大きいこと（そして \(\ln n + 1/n\) より大きいこと）を示しています。

次に、\(1/(i+1) \le \int_i^{i+1} \frac{1}{x} dx\) の不等式を \(i=1\) から \(n-1\) まで合計します。
\[
\sum_{i=1}^{n-1} \frac{1}{i+1} \le \sum_{i=1}^{n-1} \int_i^{i+1} \frac{1}{x} dx = \int_1^n \frac{1}{x} dx = \ln n
\] 和 \(\sum_{i=1}^{n-1} \frac{1}{i+1}\) は、\(i\) を \(j-1\) に置き換えると \(\sum_{j=2}^n \frac{1}{j}\) となります。これは調和級数 \(H_n\) から最初の項 \(1/1=1\) を除いたものです。
\[
\sum_{i=1}^{n-1} \frac{1}{i+1} = \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} = \left( \sum_{i=1}^n \frac{1}{i} \right) - 1 = H_n - 1
\] したがって、
\[
H_n - 1 \le \ln n
\] \[
H_n \le \ln n + 1
\] これは、\(\sum_{i=1}^n \frac{1}{i}\) が \(\ln n + 1\) 以下であることを示しています。

これまでの結果をまとめると、以下の不等式が得られました。
\[
\ln n + \frac{1}{n} \le \sum_{i=1}^n \frac{1}{i} \le \ln n + 1
\] \[
\frac{1}{n} \le \sum_{i=1}^n \frac{1}{i} - \ln n \le 1
\] この不等式は、差 \(\sum_{i=1}^n \frac{1}{i} - \ln n\) が、\(n \ge 1\) のとき常に 0 より大きく 1 以下であることを示しています。つまり、この差は \(n \to \infty\) のときに**有界である**ことが分かりました。

さらに進んで、差 \(\sum_{i=1}^n \frac{1}{i} - \ln n\) が収束すること、すなわち \(O(1)\) の項が定数に収束することを示すこともできます。これには、各区間 \([i, i+1]\) における長方形の面積と積分の差を考えます。

\(i \ge 1\) に対して、長方形の面積 \(1/i\) と積分 \(\int_i^{i+1} \frac{1}{x} dx\) の差を \(d_i\) とします。
\[
d_i = \frac{1}{i} - \int_i^{i+1} \frac{1}{x} dx
\] \(f(x)=1/x\) は凸関数でもあるため、\(d_i > 0\) です。
調和級数と積分の差を考えると、
\[
\sum_{i=1}^n \frac{1}{i} - \int_1^n \frac{1}{x} dx = \left( \sum_{i=1}^{n-1} \frac{1}{i} - \int_1^n \frac{1}{x} dx \right) + \frac{1}{n}
\] \[
= \sum_{i=1}^{n-1} \frac{1}{i} - \sum_{i=1}^{n-1} \int_i^{i+1} \frac{1}{x} dx + \frac{1}{n} = \sum_{i=1}^{n-1} \left( \frac{1}{i} - \int_i^{i+1} \frac{1}{x} dx \right) + \frac{1}{n} = \sum_{i=1}^{n-1} d_i + \frac{1}{n}
\] または、
\[
\sum_{i=1}^n \frac{1}{i} - \ln n = \sum_{i=1}^n \left( \frac{1}{i} - \int_i^{i+1} \frac{1}{x} dx \right) + \int_n^{n+1} \frac{1}{x} dx - \int_1^n \frac{1}{x} dx + \ln n
\] \[
\sum_{i=1}^n \frac{1}{i} - \ln n = \sum_{i=1}^n \left( \frac{1}{i} - \int_i^{i+1} \frac{1}{x} dx \right) + \int_n^{n+1} \frac{1}{x} dx - (\ln n) + \ln n
\] 少し整理を変えます。
\[
\sum_{i=1}^n \frac{1}{i} - \ln n = \sum_{i=1}^n \frac{1}{i} - \int_1^n \frac{1}{x} dx = \sum_{i=1}^{n-1} \frac{1}{i} + \frac{1}{n} - \int_1^n \frac{1}{x} dx
\] \[
= \sum_{i=1}^{n-1} \left( \frac{1}{i} - \int_i^{i+1} \frac{1}{x} dx \right) + \frac{1}{n} + \sum_{i=1}^{n-1} \int_i^{i+1} \frac{1}{x} dx - \int_1^n \frac{1}{x} dx
\] \[
= \sum_{i=1}^{n-1} d_i + \frac{1}{n} + \int_1^n \frac{1}{x} dx - \int_1^n \frac{1}{x} dx = \sum_{i=1}^{n-1} d_i + \frac{1}{n}
\] 差 \(d_i = \frac{1}{i} - \int_i^{i+1} \frac{1}{x} dx\) は、区間 \([i, i+1]\) における \(1/x\) のグラフ上の面積と高さ \(1/i\) の長方形の面積との差です。この差 \(d_i\) は、\(i \to \infty\) のときに \(O(1/i^2)\) のオーダーで減少することが示せます（テイラー展開などを用います）。
例えば、\( \int_i^{i+1} \frac{1}{x} dx = \ln(i+1) - \ln i = \ln(1 + 1/i) \approx 1/i - 1/(2i^2) + O(1/i^3) \) ( \(x \approx 0\) で \( \ln(1+x) \approx x - x^2/2 \))。
したがって、\( d_i = \frac{1}{i} - (\frac{1}{i} - \frac{1}{2i^2} + O(1/i^3)) = \frac{1}{2i^2} + O(1/i^3) \) となり、\(d_i\) は正で、\(i \to \infty\) のときに \(O(1/i^2)\) の速さで 0 に収束します。
級数 \(\sum_{i=1}^\infty d_i\) は、\( \sum_{i=1}^\infty 1/i^2 \) が収束する（例えば \(\pi^2/6\) に収束）ことから、収束することが分かります。
つまり、\(\sum_{i=1}^\infty d_i = D\) という有限の値に収束します。
したがって、
\[
\sum_{i=1}^n \frac{1}{i} - \ln n = \sum_{i=1}^{n-1} d_i + \frac{1}{n} = \left( \sum_{i=1}^\infty d_i \right) - \left( \sum_{i=n}^\infty d_i \right) + \frac{1}{n} = D - \left( \sum_{i=n}^\infty d_i \right) + \frac{1}{n}
\] ここで、\( \sum_{i=n}^\infty d_i \) は \(n \to \infty\) のときに 0 に収束する項です。実際、\(d_i = O(1/i^2)\) なので、\( \sum_{i=n}^\infty d_i = O(\sum_{i=n}^\infty 1/i^2) = O(1/n) \) です。また、\(1/n\) も \(n \to \infty\) のときに 0 に収束する項です。
したがって、
\[
\sum_{i=1}^n \frac{1}{i} - \ln n = D + O(1/n)
\] この \(D\) がオイラー・マスケローニ定数 \(\gamma\) です。\(O(1/n)\) は \(n \to \infty\) のときに 0 に収束するので、有界です。したがって、\(O(1)\) に含まれます。

以上の議論から、
\[
\sum_{i=1}^n \frac{1}{i} = \ln n + \gamma + O(1/n)
\] というより精密な式が成り立ち、これから \(\sum_{i=1}^n \frac{1}{i} = \ln n + O(1)\) が厳密に導かれます。\(O(1)\) は、\( \gamma + O(1/n) \) という項が \(n\) にかかわらず有界であることを意味します。実際、\(n \to \infty\) の極限では定数 \(\gamma\) に収束します。

最終的に、積分を用いた比較と、差分の級数の収束性を示すことで、調和級数と自然対数の間に差が定数に収束するという関係が厳密に証明されました。□

「少なくとも2人が同じ誕生日である」という事象の確率は、「全員の誕生日が異なる」という事象の確率を1から引いたものです。この「全員の誕生日が異なる」確率を計算する方が簡単です。

\(k\) 人の人を順番に1番目の人、2番目の人、...、\(k\) 番目の人とします。
- 1番目の人の誕生日は、どの日でも構いません（365通り）。
- 2番目の人の誕生日が1番目の人と異なる確率は \((365 - 1) / 365\) です。
- 3番目の人の誕生日が1番目と2番目の人（異なる誕生日です）と異なる確率は \((365 - 2) / 365\) です。
- ...
- \(i\) 番目の人の誕生日が、それ以前の \(i-1\) 人全員（異なる誕生日です）と異なる確率は \((365 - (i-1)) / 365\) です。

全員の誕生日が異なる確率は、これらの確率を全て掛け合わせたものです。これを \(Pr\{\text{全員異なる}\}\) と書くと、
$$
Pr\{\text{全員異なる}\} = \frac{365}{365} \times \frac{365-1}{365} \times \frac{365-2}{365} \times \cdots \times \frac{365-(k-1)}{365}
$$
$$
= 1 \times \left(1 - \frac{1}{365}\right) \times \left(1 - \frac{2}{365}\right) \times \cdots \times \left(1 - \frac{k-1}{365}\right) \quad \text{(テキストの式 5.8 と関連)}
$$
この式は、階乗を使って \(\frac{P(365, k)}{365^k} = \frac{365! / (365-k)!}{365^k}\) と書くこともできます。

求めたい確率「少なくとも2人が同じ誕生日である」は、
$$
Pr\{\text{少なくとも2人同じ}\} = 1 - Pr\{\text{全員異なる}\} = 1 - \prod_{i=1}^{k-1} \left(1 - \frac{i}{365}\right)
$$
この確率が0.5を超えるような最小の \(k\) を見つけたいのです。
$$
1 - \prod_{i=1}^{k-1} \left(1 - \frac{i}{365}\right) \ge 0.5
$$
$$
\prod_{i=1}^{k-1} \left(1 - \frac{i}{365}\right) \le 0.5
$$
この不等式を解くには、具体的な \(k\) の値を計算していくか、近似式を用いる必要があります。近似として、\(1+x \approx e^x\) (xが小さい場合) という関係から導かれる \(1-x \le e^{-x}\) という不等式を使います 。
$$
\prod_{i=1}^{k-1} \left(1 - \frac{i}{365}\right) \le \prod_{i=1}^{k-1} e^{-i/365} = e^{-\sum_{i=1}^{k-1} i/365} = e^{-k(k-1)/(2 \times 365)}
$$
したがって、\(e^{-k(k-1)/(2 \times 365)} \le 0.5\) となる \(k\) を探します。両辺の自然対数を取ると、
$$
-\frac{k(k-1)}{2 \times 365} \le \ln(0.5) = -\ln 2
$$
$$
\frac{k(k-1)}{730} \ge \ln 2
$$
$$
k(k-1) \ge 730 \times \ln 2 \approx 730 \times 0.693 \approx 505.89
$$
\(k(k-1)\) が約506以上になる最小の整数 \(k\) を探します。\(k^2 \approx 506\) とすると \(k \approx \sqrt{506} \approx 22.49\)。したがって、\(k=23\) のときにこの不等式を満たします。
正確な計算（または表の参照）によると、\(k=22\) のときの確率は約0.475、\(k=23\) のときの確率は約0.507となります。
**驚くべきことに、23人いれば、少なくとも2人が同じ誕生日である確率は50%を超えるのです。**

部屋にいる \(k\) 人の中から、任意の2人組（ペア）を選びます。ペアの総数は \(\binom{k}{2} = \frac{k(k-1)}{2}\) 通りあります。これらのペアそれぞれについて、「誕生日が一致するかどうか」という事象を考え、指示確率変数を使います。

\(k\) 人の人々を 1, 2, ..., \(k\) と番号付けします。
1 \(\le i < j \le k\) である任意のペア \((i, j)\) に対して、以下の指示確率変数 \(X_{i,j}\) を定義します。
\[
X_{i,j} = I\{ \text{人 } i \text{ と 人 } j \text{ の誕生日が同じである} \} = \begin{cases} 1 & \text{（一致する場合）} \\ 0 & \text{（一致しない場合）} \end{cases}
\] 補題5.1より、指示確率変数の期待値はその事象が起こる確率に等しいです。
\[
E[X_{i,j}] = Pr\{ \text{人 } i \text{ と 人 } j \text{ の誕生日が同じである} \}
\] 人 \(i\) と 人 \(j\) の誕生日が同じ日である確率はいくつでしょうか？ 人 \(i\) の誕生日は365日中の特定の日であり、人 \(j\) の誕生日がその特定の日と同じである確率は \(1/365\) です（誕生日は独立に、365日全てが等確率であると仮定しているからです）。
したがって、\(E[X_{i,j}] = 1/365\) です。

部屋にいる全員の中で、誕生日が一致するペアの総数を確率変数\(X\) とします。これは、全ての可能なペアに対する指示確率変数の合計です。
\[
X = \sum_{1 \le i < j \le k} X_{i,j}
\] 誕生日が一致するペア数の期待値\(E[X]\) は、期待値の線形性を用いて、個々の指示確率変数の期待値の合計として求められます。期待値の線形性は、確率変数が独立でなくても成り立ちます。\(X_{i,j}\) と \(X_{i,l}\) は、どちらも 人 \(i\) が関わるため独立ではありませんが、合計の期待値は単純な和になります。
\[
E[X] = E\left[\sum_{1 \le i < j \le k} X_{i,j}\right] = \sum_{1 \le i < j \le k} E[X_{i,j}] \quad \text{(テキストの式 5.4.1 より)}
\] 全てのペア \((i, j)\) について \(E[X_{i,j}] = 1/365\) なので、
\[
E[X] = \sum_{1 \le i < j \le k} \frac{1}{365}
\] 和は、\(1 \le i < j \le k\) という条件を満たすペア \((i, j)\) の数に \(1/365\) を掛けたものです。ペアの総数は \(\binom{k}{2} = \frac{k(k-1)}{2}\) です。
\[
E[X] = \binom{k}{2} \times \frac{1}{365} = \frac{k(k-1)}{2 \times 365} = \frac{k(k-1)}{730}
\] この期待値 \(E[X]\) が1以上になる \(k\) を求めてみましょう。
\[
\frac{k(k-1)}{730} \ge 1
\] \[
k(k-1) \ge 730
\] \(k^2 \approx 730\) とすると \(k \approx \sqrt{730} \approx 27.01\)。したがって、\(k=28\) のときにこの不等式を満たします。
28人いれば、誕生日が一致するペア数の期待値は1以上になります。

この結果（期待値が1以上となるのが28人）は、確率が50%を超える23人という結果とは異なります。しかし、どちらの解析も、誕生日が一致する現象が、人数 \(n\) に対して \(\Theta(\sqrt{n})\) のオーダーで起こりうることを示しています（365日の場合は \(\sqrt{365} \approx 19.1\)）。期待値が1以上というのは「平均して1つ以上のペアが一致する」という意味であり、確率が0.5を超えるというのは「少なくとも1つのペアが一致する可能性が半分以上」という意味です。期待値が1に近いとき、確率も0.5に近い値になる傾向がありますが、これらは異なる指標です。

プロセスを以下の \(b\) 個の段階に分けます。

• 第1段階: 0個のビンにボールが入っている状態から、1個目のビンにボールが入るまでの投げ入れ。
• 第2段階: 1個のビンにボールが入っている状態から、2個目のビンにボールが入るまでの投げ入れ。
• 第 \(i\) 段階:\(i-1\) 個の異なるビンにボールが入っている状態から、\(i\) 個目の異なるビンにボールが入るまでの投げ入れ。
• 第 \(b\) 段階:\(b-1\) 個の異なるビンにボールが入っている状態から、\(b\) 個目の（最後の）ビンにボールが入るまでの投げ入れ。

第 i 段階が始まる時点では、既に \(i-1\) 個のビンにボールが入っています。まだボールが入っていないビンは \(b - (i-1) = b - i + 1\) 個あります。第 i段階での各投げ入れで、ボールがまだ空であるビンのいずれかに入る確率は、\(\frac{\text{空のビンの数}}{\text{全ビンの数}} = \frac{b - i + 1}{b}\) です。これを「成功」の確率と見なせます。

第 i 段階で必要な投げ入れ回数を確率変数 \(n_i\) とします。これは、成功確率 \(p_i = (b - i + 1)/b\) の**幾何分布**に従います。幾何分布の期待値（初めて成功するまでの試行回数の期待値）は \(1/p\) です。
したがって、第 i 段階に必要な投げ入れ回数の期待値は、
\[
E[n_i] = \frac{1}{p_i} = \frac{1}{(b - i + 1)/b} = \frac{b}{b - i + 1}
\] 全てのビンにボールが入る（すなわち、全 b 段階が終了する）までに必要な投げ入れ回数 n の総数は、各段階の投げ入れ回数 \(n_i\) の合計です。
\[
n = \sum_{i=1}^b n_i
\] 求めたいのはこの合計回数の期待値 \(E[n]\) です。期待値の線形性により、
\[
E[n] = E\left[\sum_{i=1}^b n_i\right] = \sum_{i=1}^b E[n_i] \] 各 \(E[n_i]\) を代入して、
\[
E[n] = \sum_{i=1}^b \frac{b}{b - i + 1}
\] ここで、和の添え字を \(j = b - i + 1\) と置き換えます。
i = 1 のとき \(j = b\)、 i = b のとき \(j = 1\) となります。
\[
E[n] = \sum_{j=1}^b \frac{b}{j} = b \sum_{j=1}^b \frac{1}{j} = b H_b
\] ここで \(H_b = \sum_{j=1}^b \frac{1}{j}\) は調和級数です。前回の証明で見たように、調和級数は自然対数と関係があり、\(H_b = \ln b + \gamma + O(1/b)\) です（\(\gamma\) はオイラー・マスケローニ定数）。\(O(1)\) という精度で書けば \(H_b = \ln b + O(1)\) です (テキストの式 A.9)。
したがって、全てのビンにボールが入るまでに必要な投げ入れ回数の期待値は、
$$
E[n] = b (\ln b + O(1))
$$
つまり、ビンの数 b が大きい場合、全てのビンにボールを入れるには、平均して約 \(b \ln b\) 回の投げ入れが必要になります。これは b に対して線形より少し大きいオーダーです。例えば、100種類のクーポンを全て集めるには、平均して約 \(100 \times \ln(100) \approx 100 \times 4.6 = 460\) 個のお菓子を買う必要があると期待されます。

上限の評価

長さ \(k\) の連続した表のストリークが、投げ入れ列のどこかに現れる確率を評価することで、最長ストリークの長さを上から抑えることができます。
長さ \(k\) の表のストリークは、位置 1 から始まるか、位置 2 から始まるか、...、位置 \(n-k+1\) から始まる可能性があります。
位置 \(i\) から始まる長さ \(k\) の表のストリークとは、投げ入れ \(R_i, R_{i+1}, \ldots, R_{i+k-1}\) が全て表である事象です。投げ入れは独立しており、各投げ入れが表になる確率は \(1/2\) なので、この事象が起こる確率は \((1/2)^k = 1/2^k\) です。
これを \(Pr\{A_{i,k}\}\) とします。

投げ入れ列の中に、少なくとも1つ長さ \(k\) の表のストリークが現れる事象は、これらの \(A_{i,k}\) という事象のいずれかが起こる事象 \(\cup_{i=1}^{n-k+1} A_{i,k}\) です。この確率を評価するために、ブールの不等式を使います (\(Pr\{\cup_j B_j\} \le \sum_j Pr\{B_j\}\))。
\[
Pr\{\text{長さ } k \text{ のストリークがどこかに現れる}\} = Pr\left\{\cup_{i=1}^{n-k+1} A_{i,k}\right\} \le \sum_{i=1}^{n-k+1} Pr\{A_{i,k}\}
\] \[
\le \sum_{i=1}^{n-k+1} \frac{1}{2^k} = \frac{n-k+1}{2^k} \le \frac{n}{2^k}
\] ここで、\(k\) を \(c \lg n\) （c は正の定数）と置いてみましょう。
\[
\frac{n}{2^{c \lg n}} = \frac{n}{2^{\lg (n^c)}} = \frac{n}{n^c} = \frac{1}{n^{c-1}}
\] もし \(c > 1\) であれば、この確率は \(n\) が大きくなるにつれて非常に小さくなります (\(1/n^{c-1} \to 0\))。
例えば、\(k = 2 \lg n\) とすると、長さ \(2 \lg n\) 以上のストリークが現れる確率は \(n/2^{2 \lg n} = n/n^2 = 1/n\) 以下になります。これは、\(n\) が大きい場合、長さが \(2 \lg n\) を超えるストリークが現れる可能性は低いことを示しています。

期待される最長ストリークの長さ \(L\) は、その定義から \(E[L] = \sum_{j=0}^n j \cdot Pr\{L=j\}\) と書けます。ここで \(L=j\) は最長ストリークの長さがちょうど \(j\) である事象です。
長さ \(k\) 以上のストリークが現れる確率 \(Pr\{L \ge k\}\) は、ブールの不等式から \(Pr\{L \ge k\} \le n/2^k\) です。
期待値 \(E[L]\) を以下の2つの部分に分けて評価します。
\(E[L] = \sum_{j=0}^{k-1} j \cdot Pr\{L=j\} + \sum_{j=k}^n j \cdot Pr\{L=j\}\)
ここで、\(k\) として例えば \(2 \lg n\) を選びます。
\[
E[L] \le \sum_{j=0}^{2\lg n - 1} (2\lg n - 1) \cdot Pr\{L=j\} + \sum_{j=2\lg n}^n n \cdot Pr\{L=j\}
\] \[
\le (2\lg n) \sum_{j=0}^{2\lg n - 1} Pr\{L=j\} + n \sum_{j=2\lg n}^n Pr\{L=j\}
\] \(\sum_{j=0}^{2\lg n - 1} Pr\{L=j\} \le \sum_{j=0}^n Pr\{L=j\} = 1\) です。
\(\sum_{j=2\lg n}^n Pr\{L=j\} = Pr\{L \ge 2\lg n\}\) です。ブールの不等式より \(Pr\{L \ge 2\lg n\} \le n/2^{2\lg n} = 1/n\) です。
したがって、
\[
E[L] \le (2\lg n) \times 1 + n \times \frac{1}{n} = 2\lg n + 1
\] これは、期待される最長ストリーク長が \(O(\lg n)\) であることを示しています。

下限の評価

次に、期待される最長ストリークの長さが \(\Omega(\lg n)\) であることを示します。これは、長さが \(\lg n\) のオーダーであるストリークが、高い確率で現れることを示せば十分です。

\(n\) 回の投げ入れを、それぞれ長さ \(s\) の連続する部分に分けます。約 \(n/s\) 個のグループができます。\(s\) の値として、例えば \(s = \lfloor (\lg n) / 2 \rfloor\) を選びます。
特定のグループ（長さ \(s\)）が全て表になる確率は \(1/2^s = 1/2^{\lfloor (\lg n)/2 \rfloor}\) です。
\[
\frac{1}{2^{\lfloor (\lg n)/2 \rfloor}} \ge \frac{1}{2^{(\lg n)/2}} = \frac{1}{\sqrt{n}}
\] したがって、特定のグループが全て表にならない確率は \(1 - 1/2^s \le 1 - 1/\sqrt{n}\) です。

約 \(n/s\) 個のグループは、ほぼ独立したコイン投げから形成されます。これらのグループの**全て**が全て表にならない確率は、それぞれのグループが全て表にならない確率を掛け合わせたものとして近似できます。
この確率は \((1 - 1/2^s)^{\approx n/s}\) です。不等式 \((1-x)^m \le e^{-mx}\) を用いると、
\[
\left(1 - \frac{1}{2^s}\right)^{n/s} \le e^{-(n/s)/2^s} = e^{-n/(s 2^s)}
\] \(s = \lfloor (\lg n)/2 \rfloor\) なので、\(2^s \approx \sqrt{n}\) です。\(s \approx (\lg n)/2\) です。
指数部分は \( -n / (s 2^s) \approx -n / ((\lg n)/2 \cdot \sqrt{n}) = -2\sqrt{n} / \lg n \) です。
この指数は \(n\) が大きくなるにつれて負の無限大に発散するので、確率は 0 に収束します。
実際、テキストでは \(e^{-(2n/\lg n - 1)/\sqrt{n}} = O(e^{-\ln n}) = O(1/n)\) であることが示されています 。
つまり、全てのグループが全て表にならない確率は非常に小さい (\(O(1/n)\)) です。

これは逆に、**少なくとも1つのグループが全て表になる確率が非常に高い** (\(1 - O(1/n)\)) ことを意味します。もし少なくとも1つのグループが全て表になれば、その長さ \(s = \lfloor (\lg n)/2 \rfloor\) のストリークが必ず存在することになります。
したがって、\(Pr\{L \ge s\} \ge 1 - O(1/n)\) です 。

期待値 \(E[L]\) を再び評価します。
\[
E[L] = \sum_{j=0}^{s-1} j \cdot Pr\{L=j\} + \sum_{j=s}^n j \cdot Pr\{L=j\}
\] ここで \(s = \lfloor (\lg n)/2 \rfloor\) です。
\[
E[L] \ge \sum_{j=s}^n j \cdot Pr\{L=j\} \ge \sum_{j=s}^n s \cdot Pr\{L=j\} = s \sum_{j=s}^n Pr\{L=j\} = s \cdot Pr\{L \ge s\}
\] \[
\ge \lfloor (\lg n)/2 \rfloor \times (1 - O(1/n))
\] \(n \to \infty\) のとき、\(\lfloor (\lg n)/2 \rfloor\) は \(\Omega(\lg n)\) で増加し、\((1 - O(1/n))\) は1に近づきます。
したがって、\(E[L] = \Omega(\lg n)\) であることが示されました。

期待される最長ストリーク長が \(O(\lg n)\) かつ \(\Omega(\lg n)\) であることから、**\(\Theta(\lg n)\)** であることが結論付けられます。