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

Парадо́кс дней рожде́ния — утверждение, состоящее в том, что в группе, состоящей из 23 или более человек, вероятность совпадения дней рождения (число и месяц) хотя бы у двух людей превышает 50 %. Например, если в классе 23 ученика или более, то более вероятно то, что у какой-то пары одноклассников дни рождения придутся на один день, чем то, что у каждого будет свой неповторимый день рождения^[1]. Впервые эта задача была рассмотрена Рихардом Мизесом в 1939 году^[2][3].

Для 57 и более человек вероятность такого совпадения превышает 99 %, хотя 100 % она достигает, согласно принципу Дирихле, только тогда, когда в группе не менее 367 человек (ровно на единицу больше, чем число дней в високосном году; с учётом високосных лет).

Такое утверждение может показаться неочевидным, так как вероятность совпадения дней рождения двух человек с любым днём в году ${\displaystyle ({\tfrac {1}{365}}=0{,}27\,\%)}$, умноженная на число человек в группе (23), даёт лишь ${\displaystyle {\tfrac {1}{365}}\times 23=6{,}3\,\%}$. Это рассуждение неверно, так как число возможных пар ${\displaystyle ({\tfrac {23\times 22}{2}}=253)}$ значительно превышает число человек в группе (253 > 23). Таким образом, утверждение не является парадоксом в строгом научном смысле: логического противоречия в нём нет, а парадокс заключается лишь в различиях между интуитивным восприятием ситуации человеком и результатами математического расчёта.

В группе из 23 человек вероятность совпадения дней рождения у двух человек столь высока, потому что рассматривается вероятность совпадения дней рождения у любых двух человек в группе. Эта вероятность определяется количеством пар людей, которые можно составить из 23 человек. Так как порядок людей в парах не имеет значения, общее число таких пар равно числу сочетаний из 23 по 2, то есть (23 × 22) / 2 = 253 пары.

В формулировке парадокса речь идёт именно о совпадении дней рождения у каких-либо двух членов группы. Одно из распространённых заблуждений состоит в том, что этот случай путают с другим случаем, на первый взгляд похожим, когда из группы выбирается один человек и оценивается вероятность того, что день рождения каких-либо других членов группы совпадёт с днём рождения выбранного человека. В последнем случае вероятность совпадения значительно ниже.

Требуется определить вероятность того, что в группе из n человек как минимум у двух из них дни рождения совпадут.

Пусть дни рождения распределены равномерно, то есть примем, что:

• в году 365 дней (нет високосных лет);
• в группе нет людей, заведомо родившихся в один день (например, близнецов);
• рождаемость не зависит от дня недели, времени года и других факторов.

В действительности это не совсем так — в частности, в некоторых странах из-за особенностей работы больниц больше детей рождается в определённые дни недели. Однако неравномерность распределения может лишь увеличить вероятность совпадения дней рождения, но не уменьшить: если бы все люди рождались только в 3 дня из 365, то вероятность совпадения дней рождения была бы очень высокой.

Рассчитаем сначала ${\displaystyle {\bar {p}}(n)}$ — вероятность того, что в группе из ${\displaystyle n}$ человек дни рождения всех людей будут различными. Если ${\displaystyle n>365}$, то в силу принципа Дирихле вероятность ${\displaystyle {\bar {p}}(n)}$ равна нулю. Если же ${\displaystyle n\leqslant 365}$, то будем рассуждать следующим образом. Возьмём наугад одного человека из группы и запомним его день рождения. Затем возьмём наугад второго человека, при этом вероятность того, что у него день рождения не совпадёт с днем рождения первого человека, равна ${\displaystyle 1-{\frac {1}{365}}}$. Затем возьмём третьего человека; при этом вероятность того, что его день рождения не совпадёт с днём рождения одного из первых двух, равна ${\displaystyle 1-{\frac {2}{365}}}$. Рассуждая по аналогии, мы дойдём до последнего человека, для которого вероятность несовпадения его дня рождения со всеми предыдущими будет равна ${\displaystyle 1-{\frac {n-1}{365}}}$. Перемножая все эти вероятности, получаем вероятность того, что все дни рождения в группе будут различными:

${\displaystyle {\bar {p}}(n)=}$ ${\displaystyle 1\cdot \left(1-{\frac {1}{365}}\right)\cdot \left(1-{\frac {2}{365}}\right)\cdot \ldots \cdot \left(1-{\frac {n-1}{365}}\right)=}$ ${\displaystyle {365\cdot 364\cdot \ldots \cdot (365-n+1) \over 365^{n}}=}$ ${\displaystyle {365! \over 365^{n}(365-n)!}.}$

Тогда вероятность того, что хотя бы у двух человек из n дни рождения совпадут, равна

${\displaystyle p(n)=1-{\bar {p}}(n).}$

Значение этой функции превосходит 1/2 при ${\displaystyle n=23}$, при этом вероятность совпадения равна примерно 50,73 %, а ${\displaystyle p(22)\approx 47,57\%}$. Список значений n и соответствующих им вероятностей приведён в следующей таблице.

Данную задачу можно переформулировать в терминах классической «задачи о совпадениях». Пусть:

• урна содержит ${\displaystyle M}$ шаров (в данном случае ${\displaystyle M}$ — количество дней в году, принятое равным 365 дням);
• шары пронумерованных числами 1, 2, …, ${\displaystyle M}$;
• производится несколько выборок по n шаров из урны (в данном случае n — количество человек в группе);
• изъятые шары возвращаются в урну после каждой выборки;
• выборки считаются упорядоченными, то есть выборки ${\displaystyle \{1,2,4,6\}}$ и ${\displaystyle \{4,2,6,1\}}$ считаются различными.

Требуется посчитать вероятность события, заключающегося в отсутствии повторений в выборке. Все расчёты аналогичны приведённым выше.

Вероятность совпадения дней рождения у двух человек, входящих в группу из n людей, можно также рассчитать с использованием формул комбинаторики^[4]. Представим, что каждый день года — это одна буква в алфавите, и алфавит состоит из 365 букв. Дни рождения n человек могут быть представлены строкой, состоящей из n букв такого алфавита. По формуле Хартли, количество возможных строк равно

${\displaystyle n_{\text{total}}=365^{n}.}$

Количество возможных строк, в которых буквы не повторяются (размещение из 365 по n), составит

${\displaystyle n_{\text{unique}}={\frac {365!}{(365-n)!}}.}$

Если строки выбираются случайно (с равномерным распределением), вероятность выбора строки, в которой хотя бы две буквы совпадут, равна

${\displaystyle p(n)=1-{\frac {n_{\text{unique}}}{n_{\text{total}}}}=1-{\frac {\frac {365!}{(365-n)!}}{365^{n}}}}$ при ${\displaystyle n\leqslant 365}$ и

${\displaystyle p(n)=1}$ при ${\displaystyle n>365}$.

Таким образом,

${\displaystyle {\frac {\left({\frac {365!}{(365-n)!}}\right)}{365^{n}}}={\frac {365\cdot 364\cdot 363\cdots (365-n+1)}{365^{n}}}={}}$${\displaystyle {\frac {365}{365}}\cdot {\frac {364}{365}}\cdot {\frac {363}{365}}\cdots {\frac {365-n+1}{365}}={}}$${\displaystyle 1\cdot \left(1-{\frac {1}{365}}\right)\cdot \left(1-{\frac {2}{365}}\right)\cdots \left(1-{\frac {n-1}{365}}\right),}$

а это выражение эквивалентно представленному выше.

Также общее количество возможных строк можно рассчитать по формуле комбинаторики количества размещений с повторениями А(повт) n/365 = 365ⁿ.

Используя разложение экспоненциальной функции в ряд Тейлора

${\displaystyle e^{x}=1+x+{\frac {x^{2}}{2!}}+\ldots ,}$

приведённое выше выражение для ${\displaystyle {\bar {p}}(n)}$ можно аппроксимировать следующим образом:

${\displaystyle {\bar {p}}(n)\approx 1\cdot e^{-1/365}\cdot e^{-2/365}\cdots e^{-(n-1)/365}=}$ ${\displaystyle 1\cdot e^{-(1+2+\cdots +(n-1))/365}=}$ ${\displaystyle e^{-{\frac {n(n-1)}{2\cdot 365}}}.}$

Следовательно:

${\displaystyle p(n)=1-{\bar {p}}(n)\approx 1-e^{-{\frac {n(n-1)}{2\cdot 365}}}.}$

Заметим, что упрощённая аппроксимация

${\displaystyle p(n)\approx 1-e^{-{\frac {n^{2}}{2\cdot 365}}},}$

как видно по графику, также даёт достаточную точность.

Приведём ещё одну аппроксимацию.

Вероятность того, что у двух людей дни рождения не совпадают, равна 364/365. В группе из ${\displaystyle n}$ человек ${\displaystyle C(n,2)={\frac {n(n-1)}{2}}}$ пар. Поэтому вероятность ${\displaystyle {\bar {p}}(n)}$ при условии независимости этих событий может быть приближена числом

${\displaystyle \left({\frac {364}{365}}\right)^{C(n,2)}.}$

Отсюда получаем приближение для искомой вероятности p(n):

${\displaystyle p(n)\approx 1-\left({\frac {364}{365}}\right)^{C(n,2)}.}$

Используя приближение Пуассона для бинома, исходя из предыдущего приближения для ${\displaystyle p(n)}$, получим чуть больше 50 %:

${\displaystyle \operatorname {Poi} \left({\frac {C(23,2)}{365}}\right)=\operatorname {Poi} \left({\frac {253}{365}}\right)\approx \operatorname {Poi} (0{,}693\,2);}$

${\displaystyle \mathbb {P} \left(\{X>0\}\right)=1-\mathbb {P} \left(\{X=0\}\right)=1-e^{-0{,}693\,2}=1-0{,}499\,998=0{,}500\,002.}$

Из приведённой ранее формулы ${\displaystyle p(n)=1-{\bar {p}}(n)\approx 1-e^{-{\frac {n(n-1)}{2\cdot 365}}}}$ выразим n. Затем вместо p(n) подставим 50 % (0,5). В результате получим:

${\displaystyle n\approx {\frac {1}{2}}+{\sqrt {{\frac {1}{4}}-2\cdot 365\cdot \ln 0{,}5}}=22{,}9999.}$

Существует ещё один способ оценки n при вероятности 50 %. Согласно доказанному выше:

${\displaystyle {\bar {p}}(n)=1-p(n)=\prod _{k=1}^{n-1}\left(1-{\frac {k}{365}}\right).}$

Найдём наименьшее n, при котором

${\displaystyle p(n)>{\frac {1}{2}}}$

или, что то же самое,

${\displaystyle {\bar {p}}(n)<{\frac {1}{2}}.}$

Воспользуемся приведённой выше аппроксимацией функции ${\displaystyle {\bar {p}}(n)}$ экспоненциальной функцией:

${\displaystyle {\bar {p}}_{\text{approx}}(n)=\prod _{k=1}^{n-1}e^{\frac {-k}{365}}=e^{\frac {-n(n-1)}{2\cdot 365}}.}$

Подставив ${\displaystyle {\bar {p}}_{\text{approx}}(n)}$ вместо ${\displaystyle {\bar {p}}(n)}$ в выражение ${\displaystyle {\bar {p}}(n)<{\frac {1}{2}}}$, получим

${\displaystyle e^{\frac {-n(n-1)}{2\cdot 365}}<{\frac {1}{2}}.}$

Решая относительно n, получим

${\displaystyle n^{2}-n>2\cdot 365\cdot \ln 2.}$

Отсюда найдём n и округлим до целого:

n = 23.

Сравним вероятность p(n) с вероятностью того, что в группе из n человек день рождения какого-либо человека из группы совпадёт с днём рождения некоторого заранее выбранного человека, не принадлежащего группе. Эта вероятность равна

${\displaystyle q(n)=1-\left({\frac {365-1}{365}}\right)^{n}.}$

Подставляя n = 23, получаем q(n) ≈ 6,12 %. Для того, чтобы вероятность q(n) превысила 50 %, число людей в группе должно быть не менее 253 (q(252) ≈ 49,91 %; q(253) ≈ 50,05 %). Это число больше, чем половина дней в году (365/2 = 182,5); так происходит из-за того, что у остальных членов группы дни рождения могут совпадать между собой, и это уменьшает вероятность q(n). Если выразиться точнее, то это происходит из-за того, что при сложении вероятностей совпадений мы каждый раз вычитаем вероятность совместного появления этих событий, так как события являются совместными и вероятность их совместного появления при сложении учтена дважды. P(A + B) = P(A) + P(B) − P(AB) и т. д с каждым добавлением нового слагаемого.

Описанная задача может быть сформулирована в общем виде:

• даны случайные числа;
• случайные числа распределены равномерно в диапазоне от 1 до d;
• n — количество случайных чисел;
• определить p( n ; d ) — вероятность того, что совпадут хотя бы два числа из заданных.

Если рассуждать таким же образом, как описано выше, можно получить общие решения:

${\displaystyle p(n;d)={\begin{cases}1-\prod _{k=1}^{n-1}\left(1-{k \over d}\right)&n\leq d\\1&n>d\end{cases}};}$

${\displaystyle p(n;d)\approx 1-e^{-(n(n-1))/2d};}$

${\displaystyle q(n;d)=1-\left({\frac {d-1}{d}}\right)^{n}.}$

Обратная задача:

• дана p — вероятность того, что совпадают хотя бы два случайных числа;
• известно, что случайные числа распределены равномерно в диапазоне от 1 до d;
• найти n(p;d) — количество случайных чисел.

Решение:

${\displaystyle n(p;d)\approx {\sqrt {2d\cdot \ln \left({1 \over 1-p}\right)}}.}$

Выше парадокс дней рождения был представлен для одного «типа» людей. Можно обобщить задачу, введя несколько «типов», например, разделив людей на мужчин (m) и женщин (n). Подсчитаем вероятность того, что хотя бы у одной женщины и у одного мужчины совпадают дни рождения (совпадение дней рождения у двух женщин или у двух мужчин не учитываются):

${\displaystyle p_{0}=1-{\frac {1}{d^{m+n}}}\sum _{i=1}^{m}\sum _{j=1}^{n}S_{2}(m,i)S_{2}(n,j)\prod _{k=0}^{i+j-1}(d-k),}$

где d = 365 и S₂() — числа Стирлинга второго рода. Интересно, что нет однозначного ответа на вопрос о величине n+m для заданной вероятности. Например, вероятность 0,5 даёт как набор из 16 мужчин и 16 женщин, так и набор из 43 мужчин и 6 женщин.

Другое обобщение парадокса дней рождения состоит в постановке задачи о том, сколько требуется человек для того, чтобы вероятность наличия в группе людей, дни рождения которых различаются не более чем на один день (или на два, три дня и так далее), превысила 50 %. При решении этой задачи используется принцип включения-исключения. Результат (опять-таки в предположении, что дни рождения распределены равномерно) получается следующим:

Таким образом, вероятность того, что даже в группе из 7 человек дни рождения хотя бы у двух из них будут различаться не более чем на неделю, превышает 50 %.

Парадокс дней рождения в общем виде применим к хеш-функциям: если хеш-функция генерирует N‑битное значение, то число случайных входных данных, для которых хеш-коды с большой вероятностью дадут коллизию (то есть найдутся равные хеш-коды, полученные на разных входных данных), равно не 2^N, а только около 2^N/2. Это наблюдение используется в атаке на криптографические хеш‑функции, получившей название «атака „дней рождения“».

В белых ячейках указано количество человек в группе, при котором коллизия произойдёт с заданной вероятностью (по аналогии с парадоксом количество выходных цепочек равно 365).

Сходный математический аппарат используется для оценки размера популяции рыб, обитающих в озёрах. Метод называется «capture-recapture» («поймать — поймать снова»). Действительно, если каждую пойманную рыбу помечать и отпускать, то вероятность поймать помеченную рыбу будет расти нелинейно (в соответствии с приведённым выше графиком) с ростом количества попыток. Размер популяции грубо может быть оценён как квадрат числа попыток, совершаемых до вылавливания первой помеченной рыбы.

Решение задачи в общем виде находит применение во многих разделах математики, например, в недетерминированных алгоритмах факторизации. Так, одно из самых простых объяснений ρ-метода Полларда аналогично объяснению парадокса дней рождения: достаточно иметь примерно ${\displaystyle {\sqrt {p}}}$ случайных чисел от 0 до ${\displaystyle n=pq}$, где ${\displaystyle p<q}$ — простые, чтобы хотя бы для одной из пар чисел с высокой вероятностью нашёлся ${\displaystyle \gcd \left(|x-y|,n\right)>1}$, который и будет делителем числа n.

1. Поиск наименьшего числа n, при котором вероятность p(n) больше заданного числа p.

2. Поиск наибольшего числа n, при котором вероятность p(n) меньше заданного числа p.

Пользуясь формулой, приведённой выше, получаем:

${\displaystyle n(p;365)\approx {\sqrt {2\cdot 365\cdot \ln \left({1 \over 1-p}\right)}}.}$

Пусть в комнате находятся n - 1 человек, и их дни рождения различны. Пусть g(n) — вероятность того, что день рождения вошедшего человека совпадает с днём рождения кого‑либо из присутствующих в комнате. Требуется найти значение n, при котором значение функции g(n) максимально.

Решение сводится к нахождению максимального значения выражения

p(n) - p(n-1).

Используя приведённую выше формулу для p(n), получим n = 20.

Рассмотрим другую задачу. Сколько в среднем нужно людей для того, чтобы хотя бы у двух из них совпали дни рождения?

Эта проблема имела отношение к алгоритмам хеширования и была исследована Дональдом Кнутом. Оказывается, что интересующая нас случайная величина имеет математическое ожидание, равное

${\displaystyle {\overline {n}}\,=\,1+Q(M),}$

где

${\displaystyle Q(M)=\sum _{k=1}^{M}{\frac {M!}{(M-k)!M^{k}}}.}$

Функция

${\displaystyle Q(M)\,=\,1+{\frac {M-1}{M}}+{\frac {(M-1)(M-2)}{M^{2}}}+\cdots +{\frac {(M-1)(M-2)\cdots 1}{M^{M-1}}}}$

была исследована Рамануджаном. Он же получил для этой функции следующее асимптотическое разложение:

${\displaystyle Q(M)\sim {\sqrt {\frac {\pi M}{2}}}-{\frac {1}{3}}+{\frac {1}{12}}{\sqrt {\frac {\pi }{2M}}}-{\frac {4}{135M}}+\cdots .}$

При M = 365 среднее число людей равно

${\displaystyle {\overline {n}}\,=\,1+Q(M)\approx 24,61658.}$

Это число немного больше, чем число людей, обеспечивающих вероятность 50 %. Как ни удивительно, необходимое число людей равно M + 1 = 366 (у 365 людей дни рождения могут распределиться по каждому из 365 дней года без совпадений), хотя в среднем нужно лишь 25.

• Задача о письмах
• Закон больших чисел

• Кемени Дж., Снелл Дж., Томпсон Дж. Введение в конечную математику = Introduction to Finite Mathematics. — Издательство иностранной литературы, 1963. — 488 с.
• Козлов М. В. Элементы теории вероятностей в примерах и задачах. — Издательство Московского университета, 1990 год. — ISBN 5-211-00312-8.
• Мазур, Джозеф. Задача о дне рождения // Игра случая. Математика и мифология совпадения. — Альпина нон-фикшн, 2017. — С. 116—123. — 292 с. — ISBN 978-5-91671-636-8.
• Секей Г. Парадоксы в теории вероятностей и математической статистике. — РХД, 2003 год. — ISBN 5-93972-150-8.
• Ширяев А. Н. Вероятность-1. — МЦНМО, 2007 год. — ISBN 978-5-94057-036-3.
• Goldberg S. A Direct Attack on a Birthday Problem (англ.) // Mathematical Mathematics Magazine. — Май 1976 года. — Iss. 49. — P. 130—132.
• Mosteller F. Understanding the Birthday Problem (англ.) // The Mathematics Teacher. — Май 1962 года. — P. 322—325.

• Парадоксы теории вероятностей.
• Сравнительный обзор алгоритмов PGP. Парадокс «дней рождения» и стойкость криптографии.
• Eurobirthdays 2012 года (англ.). Практический пример.

В статье есть список источников, но не хватает сносок. Без сносок сложно определить, из какого источника взято каждое отдельное утверждение. Вы можете улучшить статью, проставив сноски на источники, подтверждающие информацию. Сведения без сносок могут быть удалены. (3 июня 2011)