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

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

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

n	p ( n )
10	12 %
20	41 %
30	70 %
50	97 %
100	99,99996 %
200	99,9999999999999999999999999998 %
300	(1 − 7×10 −73 ) × 100 %
350	(1 − 3×10 −131 ) × 100 %
367	100 %

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

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

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

Альтернативный метод

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

Расчёт количества человек, при котором вероятность составляет 50 %

Из приведённой ранее формулы ${\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 % . При решении этой задачи используется принцип включения-исключения . Результат (опять-таки в предположении, что дни рождения распределены равномерно ) получается следующим:

Максимальное различие дней рождения, количество дней	Необходимое количество людей
1	23
2	14
3	11
4	9
5	8
6	8
7	7
8	7

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

Применение

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

N	Количество различных выходных цепочек (2 N )	Вероятность хотя бы одной коллизии ( p )
		10 −18	10 −15	10 −12	10 −9	10 −6	0,1 %	1 %	25 %	50 %	75 %
32	4,3 × 10 9	2	2	2	2,9	93	2,9 × 10³	9,3 × 10³	5,0 × 10⁴	7,7 × 10⁴	1,1 × 10⁵
64	1,8 × 10 19	6,1	1,9 × 10²	6,1 × 10³	1,9 × 10⁵	6,1 × 10⁶	1,9 × 10⁸	6,1 × 10⁸	3,3 × 10⁹	5,1 × 10⁹	7,2 × 10⁹
128	3,4 × 10 38	2,6 × 10 10	8,2 × 10 11	2,6 × 10 13	8,2 × 10 14	2,6 × 10 16	8,3 × 10 17	2,6 × 10 18	1,4 × 10 19	2,2 × 10 19	3,1 × 10 19
256	1,2 × 10 77	4,8 × 10 29	1,5 × 10 31	4,8 × 10 32	1,5 × 10 34	4,8 × 10 35	1,5 × 10 37	4,8 × 10 37	2,6 × 10 38	4,0 × 10 38	5,7 × 10 38
384	3,9 × 10 115	8,9 × 10 48	2,8 × 10 50	8,9 × 10 51	2,8 × 10 53	8,9 × 10 54	2,8 × 10 56	8,9 × 10 56	4,8 × 10 57	7,4 × 10 57	1,0 × 10 58
512	1,3 × 10 154	1,6 × 10 68	5,2 × 10 69	1,6 × 10 71	5,2 × 10 72	1,6 × 10 74	5,2 × 10 75	1,6 × 10 76	8,8 × 10 76	1,4 × 10 77	1,9 × 10 77

В белых ячейках указано количество человек в группе, при котором коллизия произойдёт с заданной вероятностью (по аналогии с парадоксом количество выходных цепочек равно 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)}}.}$

p	n	n ↓	p ( n ↓)	n ↑	p ( n ↑)
0,01	0,14178√365 = 2,70864	2	0,00274	3	0,00820
0,05	0,32029√365 = 6,11916	6	0,04046	7	0,05624
0,1	0,45904√365 = 8,77002	8	0,07434	9	0,09462
0,2	0,66805√365 = 12,76302	12	0,16702	13	0,19441
0,3	0,84460√365 = 16,13607	16	0,28360	17	0,31501
0,5	1,17741√365 = 22,49439	22	0,47570	23	0,50730
0,7	1,55176√365 = 29,64625	29	0,68097	30	0,70632
0,8	1,79412√365 = 34,27666	34	0,79532	35	0,81438
0,9	2,14597√365 = 40,99862	40	0,89123	41	0,90315
0,95	2,44775√365 = 46,76414	46	0,94825	47	0,95477
0,99	3,03485√365 = 57,98081	57	0,99012	58	0,99166

Наилучшая позиция

Пусть в комнате находятся 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. (англ.) // The Mathematics Teacher. — Май 1962 года . — P. —325 .

Ссылки

• .
• .
• (англ.) . Практический пример.