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

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

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

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

График зависимости вероятности совпадения дней рождения хотя бы у двух человек от количества людей

Интуитивное восприятие

В группе из 23 человек вероятность совпадения дней рождения у двух человек столь высока, потому что рассматривается вероятность совпадения дней рождения у любых двух человек в группе. Эта вероятность определяется количеством пар людей, которые можно составить из 23 человек. Так как порядок людей в парах не имеет значения, общее число таких пар равно числу сочетаний из 23 по 2, то есть Шаблон:Nobr.

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

Расчёт вероятности

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

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

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

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

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

$\overline{p}(n)=$ $1\cdot (1-\frac{1}{365})\cdot (1-\frac{2}{365})\cdot \dots \cdot (1-\frac{n-1}{365})=$ $\frac{365\cdot 364\cdot \dots \cdot (365-n+1)}{365^n}=$ $\frac{365!}{365^n(365-n)!}.$

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

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

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

n	Шаблон:Nobr
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 %

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

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

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

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

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

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

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

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

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

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

$p(n)=1$ при $n>365$.

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

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

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

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

Аппроксимации

Экспоненциальная функция

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

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

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

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

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

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

Файл:График аппроксимации (парадокс дней рождения).png

Графики функции Шаблон:Nobr и близкой к ней функции аппроксимации

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

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

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

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

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

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

Следовательно, получаем приближение для искомой вероятности Шаблон:Nobr:

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

Пуассоновское приближение

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

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

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

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

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

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

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

$\overline{p}(n)=1-p(n)=\prod _{k=1}^{n-1}(1-\frac{k}{365}).$

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

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

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

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

Воспользуемся приведённой выше аппроксимацией Шаблон:Nobr экспоненциальной функцией:

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

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

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

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

$n^2-n>2\cdot 365\cdot \ln 2.$

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

Шаблон:Nobr.

Родившиеся в один день с заданным человеком

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

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

Сравнение графиков функций Шаблон:Nobr и Шаблон:Nobr.
Ось абсцисс: количество человек n.
Ось ординат: вероятность.
Шаблон:Nobr — вероятность того, что в группе из n человек как минимум у двух из них дни рождения совпадут.
Шаблон:Nobr — вероятностью того, что в группе из n человек день рождения какого‑либо человека из группы совпадёт с днём рождения некоторого заранее выбранного человека, не принадлежащего группе.

Подставляя Шаблон:Nobr, получаем Шаблон:Nobr. Для того, чтобы вероятность Шаблон:Nobr превысила Шаблон:Nobr, число людей в группе должно быть не менее 253 (Шаблон:Nobr; Шаблон:Nobr). Это число больше, чем половина дней в году (Шаблон:Nobr); так происходит из-за того, что у остальных членов группы дни рождения могут совпадать между собой, и это уменьшает вероятность Шаблон:Nobr. Если выразиться точнее, то это происходит из-за того, что при сложении вероятностей совпадений мы каждый раз вычитаем вероятность совместного появления этих событий, так как события являются совместными и вероятность их совместного появления при сложении учтена дважды. P(A + B) = P(A) + P(B) − P(AB) и т. д с каждым добавлением нового слагаемого.

Обобщения

Совпадение дискретных случайных величин

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

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

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

$p(n;d)=\{\begin{array}{cc}1-\prod _{k=1}^{n-1}(1-\frac{k}{d})& n\le d\\ 1& n>d\end{array};$

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

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

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

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

Решение:

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

Несколько типов людей

Вероятность совпадения дня рождения хотя бы у одного мужчины и у одной женщины

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

$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),$

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

Близкие дни рождения

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

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

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

Применение

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

N	Количество различных выходных цепочек (2N)	Вероятность хотя бы одной коллизии (p)
		10−18	10−15	10−12	10−9	10−6	0,1 %	1 %	25 %	50 %	75 %
32	4,3 × 109	2	2	2	2,9	93	2,9 × 10³	9,3 × 10³	5,0 × 10⁴	7,7 × 10⁴	1,1 × 10⁵
64	1,8 × 1019	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 × 1038	2,6 × 1010	8,2 × 1011	2,6 × 1013	8,2 × 1014	2,6 × 1016	8,3 × 1017	2,6 × 1018	1,4 × 1019	2,2 × 1019	3,1 × 1019
256	1,2 × 1077	4,8 × 1029	1,5 × 1031	4,8 × 1032	1,5 × 1034	4,8 × 1035	1,5 × 1037	4,8 × 1037	2,6 × 1038	4,0 × 1038	5,7 × 1038
384	3,9 × 10115	8,9 × 1048	2,8 × 1050	8,9 × 1051	2,8 × 1053	8,9 × 1054	2,8 × 1056	8,9 × 1056	4,8 × 1057	7,4 × 1057	1,0 × 1058
512	1,3 × 10154	1,6 × 1068	5,2 × 1069	1,6 × 1071	5,2 × 1072	1,6 × 1074	5,2 × 1075	1,6 × 1076	8,8 × 1076	1,4 × 1077	1,9 × 1077

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

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

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

Обратные задачи

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

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

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

$n(p;365)\approx \sqrt{2\cdot 365\cdot \ln \left(\frac{1}{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

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

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

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

Шаблон:Nobr.

Используя приведённую выше формулу для Шаблон:Nobr, получим Шаблон:Nobr.

Среднее число людей

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

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

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

где

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

Функция

$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}}$

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

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

При Шаблон:Nobr среднее число людей равно

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

Это число немного больше, чем число людей, обеспечивающих вероятность Шаблон:Nobr. Как ни удивительно, необходимое число людей равно Шаблон:Nobr (у 365 людей дни рождения могут распределиться по каждому из 365 дней года без совпадений), хотя в среднем нужно лишь 25.

См. также

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

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья

Ссылки

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