Парадокс дней рождений
Задача
Какая вероятность совпадения дня рождения у двух людей в группе из $n$ человек.
Интуиция
Вероятность, что у человека - день рождения в день $x - \frac{1}{365}$, тогда, выберем двух людей, вероятность, что совпадет - $\frac{1}{365^2}$, пар - $\frac{n \cdot (n - 1)}{2}$, тогда вероятность для 50 людей чуть больше 1 процента
Правильная интуиция
Поскольку рассматривается вероятность совпадения дней рождения у любых двух человек в группе, то эта вероятность определяется количеством пар людей, которые можно составить из $n$ человек. Так как порядок людей в парах не имеет значения, то общее число таких пар равно числу сочетаний из $n$ по 2, уже для 23 имеем есть $\frac{23 \cdot 22}{2} = 253$ пары. Посмотрев на это число, легко понять, что при рассмотрении 253 пар людей вероятность совпадения дней рождения хотя бы у одной пары будет достаточно высокой.
Ключевым моментом здесь является то, что утверждение парадокса дней рождения говорит именно о совпадении дней рождения у каких-либо двух членов группы. Одно из распространённых заблуждений состоит в том, что этот случай путают с другим — похожим, на первый взгляд, — случаем, когда из группы выбирается один человек и оценивается вероятность того, что у кого-либо из других членов группы день рождения совпадёт с днем рождения выбранного человека. В последнем случае вероятность совпадения значительно ниже.
Решение
Рассчитаем сначала, какова вероятность $p(n)$ того, что в группе из $n$ человек дни рождения всех людей будут различными. Если $n > 365$, то в силу принципа Дирихле вероятность равна нулю. Если же $n \le 365$, то будем рассуждать следующим образом. Возьмём наугад одного человека из группы и запомним его день рождения. Затем возьмём наугад второго человека, при этом вероятность того, что у него день рождения не совпадёт с днем рождения первого человека, равна $1 — \frac{1}{365}$. Затем возьмём третьего человека, при этом вероятность того, что его день рождения не совпадёт с днями рождения первых двух, равна $1 — \frac{2}{365}$. Рассуждая по аналогии, мы дойдём до последнего человека, для которого вероятность несовпадения его дня рождения со всеми предыдущими будет равна $1 — \frac{n - 1}{365}$. Перемножая все эти вероятности, получаем вероятность того, что все дни рождения в группе будут различными:
$p(n) = 1 \cdot (1 − \frac{1}{365}) \cdot (1 − \frac{1}{365}) \dots (1 - \frac{n - 1}{365}) = \frac{365 \cdot 364 \dots (365 − n + 1)}{365^n}=\frac{365!}{365^n \cdot (365−n)!}$, тогда нужная нам вероятность = $1 - p(n)$, уже для 23 она будет больше 50 процентов.
Общая формулировка
Если $n$ объектов равномерно случайно размещают по $M$ корзинам, где $n \geq \sqrt{M}$, то с вероятностью $\geq \frac{1}{2}$ какие-то 2 объекта попадут в одну корзину.
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin
Автор конспекта: Александр Гришутин
По всем вопросам пишите в telegram @rationalex