birthdays_paradox.tex

\section{Парадокс дней рождения}\label{section-birthday-padradox}
\selectlanguage{russian}

Парадокс дней рождения\index{парадокс дней рождения} связан с контринтуитивным ответом на следующую задачу: какой должен быть минимальный размер группы, чтобы вероятность совпадения дней рождения хотя бы у пары человек из этой группы была больше $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}$.