forked from vlsergey/infosec
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathbirthdays_paradox.tex
29 lines (23 loc) · 2.69 KB
/
birthdays_paradox.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
\subsection{Парадокс дней рождений}
\selectlanguage{russian}
Найдем вероятность $P(n)$ того, что в группе из $n$ человек хотя бы двое имеют день рождения в один день года. Кроме того, найдем минимальный размер группы, в которой дни рождения совпадают хотя бы у двоих с вероятностью не менее $\frac{1}{2}$\index{парадокс дней рождений}.
Вероятность того, что $n$ человек ($n < 365$) не имеют общего дня рождения, есть
\[
\bar{P}(n) = 1 \cdot \left( 1 - \frac{1}{365} \right) \cdot \left(1 - \frac{2}{365} \right) \dots \left( 1 - \frac{n-1}{365} \right) = \prod\limits_{i=0}^{n-1} \left( 1 - \frac{i}{365} \right).
\]
Аппроксимируя $1-x \leq e^{-x}$, находим
\[ \bar{P}(n) \approx \prod\limits_{i=0}^{n-1} e^{-\frac{i}{365}} = e^{-\frac{n(n-1)}{2} \cdot \frac{1}{365}} \approx e^{-\frac{n^2}{2} \cdot \frac{1}{365}}. \]
Вероятность того, что хотя бы 2 человека из $n$ имеют общий день рождения, есть
\[ P(n) = 1 - \bar{P}(n) \approx 1 - e^{-\frac{n^2}{2} \cdot \frac{1}{365}}. \]
Найдем такое число $n_{1/2}$, чтобы выполнялось условие $P(n_{1/2}) \geq \frac{1}{2}$. Подставляя это значение в формулу для вероятности, получим $\frac{1}{2} \geq e^{-\frac{n_{1/2}^2}{2} \cdot \frac{1}{365}}$. Следовательно,
\[
n_{1/2} \geq \sqrt{2 \ln 2 \cdot 365} \geq 23.
\]
Парадокс дней рождений заключается в том, что вероятность совпадения дней рождения хотя бы у одной пары в группе, много меньше вероятности совпадения дней рождения двух людей не в группе.
%Средний размер $\bar{n}$ группы, в которой есть хотя бы 2 человека с одним днем рождения, асимптотически $\bar{n} \approx 1 + \sqrt{\frac{\pi}{2}365}$.
Обобщим эту задачу на выборку из $n$ случайных элементов с повторами из множества $2^k$ различных элементов и получим формулы для вероятности и числа $n$:
\[
P(n) \approx 1 - e^{-\frac{n^2}{2} 2^{-k}}, ~~
n_{1/2} \approx \sqrt{2 \ln 2} \cdot 2^{k/2}. ~~
% \bar{n} \approx \sqrt{\frac{\pi}{2}} \cdot 2^{k/2}.
\]