16.2. Парадокс дней рождения

Парадокс дней рождения связан с контринтуитивным ответом на следующую задачу: какой должен быть минимальный размер группы, чтобы вероятность совпадения дней рождения хотя бы у пары человек из этой группы была больше $1 / 2$? Первый возникающий в голове вариант ответа «183 человека» (то есть $\left\lceil 365 / 2 \right\rceil$) является неверным.

Найдём вероятность $P(n)$ того, что в группе из $n$ человек хотя бы двое имеют дни рождения в один день года. Вероятность того, что $n$ человек ($n < N = 365$) не имеют общего дня рождения, есть

$$ \bar{P}(n) = 1 \cdot \left( 1 - \frac{1}{N} \right) \cdot \left(1 - \frac{2}{N} \right)\cdot \dots \cdot \left( 1 - \frac{n-1}{N} \right) = \prod\limits_{i=0}^{n-1} \left( 1 - \frac{i}{N} \right). $$

Аппроксимируя $1-x \leq \exp({-x})$, находим

$$ \bar{P}(n) \approx \prod\limits_{i=0}^{n-1} \exp\left(-\frac{i}{N}\right) = \exp\left(-\frac{n(n-1)}{2} \cdot \frac{1}{N}\right) \approx \exp\left(-\frac{n^2}{2} \cdot \frac{1}{N}\right). $$

Вероятность того, что хотя бы 2 человека из $n$ имеют общий день рождения, есть

$$ P(n) = 1 - \bar{P}(n) \approx 1 - \exp\left(-\frac{n^2}{2} \cdot \frac{1}{N}\right). $$

Кроме того, найдём минимальный размер группы, в которой дни рождения совпадают хотя бы у двоих с вероятностью не менее $1 / 2$. То есть найдём такое число $n_{1/2}$, чтобы выполнялось условие $P(n_{1/2}) \geq \frac{1}{2}$. Подставляя это значение в формулу для вероятности, получим $\frac{1}{2} \geq \exp\left(-\frac{n_{1/2}^2}{2} \cdot \frac{1}{N}\right)$. Следовательно,

$$n_{1/2} \geq \sqrt{2 \ln 2 \cdot N} \approx 1,18 \sqrt{ N } \approx 22,5.$$

В криптографии при оценках стойкости алгоритмов часто опускают коэффициент $\sqrt{2 \ln 2}$, считая ответом на задачу «округлённое» значение $\sqrt{ N }$. Например, оценку числа операций хеширования для поиска коллизии идеальной криптографической хеш-функции с размером выхода $k$ бит часто записывают как $2^{k/2}$.