Проблема дня рождения

Вычисленная вероятность того, что по крайней мере два человека разделяют день рождения, по сравнению с количеством людей

В теории вероятностей , то проблема рождения или день рождения парадокс касается вероятности , что в совокупности $п$ случайно выбранных людей, некоторые пары из них будет иметь тот же день рождения . По принципу «голубятни» вероятность достигает 100%, когда число людей достигает 367 (поскольку возможных дней рождения всего 366, включая 29 февраля ). Однако вероятность 99,9% достигается всего с 70 людьми, а вероятность 50% - с 23 людьми. Эти выводы основаны на предположении, что каждый день в году (кроме 29 февраля) одинаково вероятен для дня рождения.

Фактические записи о рождении показывают, что в разные дни рождается разное количество людей. В этом случае можно показать, что количество людей, необходимое для достижения порога 50%, составляет 23 или меньше . ^[1] Например, если половина людей родилась в один день, а другая половина - в другой, то вероятность того , что у любых двоих день рождения совпадают, составляет 50%.

Может показаться удивительным, что группа всего из 23 человек требуется для достижения 50% вероятности того, что по крайней мере два человека в группе имеют один и тот же день рождения: этот результат, возможно, будет более правдоподобным, если учесть, что сравнение дней рождения действительно будет между всеми возможными парами людей = 23 × 22/2 = 253 сравнений, что намного больше половины количества дней в году (не более 183), в отличие от сосредоточения на одном человеке и сравнения его дня рождения с днем рождения всех остальных. . Проблема дня рождения не является « парадоксом » в буквальном логическом смысле противоречащей самому себе, это просто на первый взгляд неинтуитивно.

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

История проблемы неясна. Результат был приписан Гарольду Давенпорту ; ^[2] однако версия того, что сегодня считается проблемой дня рождения, была предложена ранее Ричардом фон Мизесом . ^[3]

Расчет вероятности [ править ]

Задача состоит в том, чтобы вычислить приблизительную вероятность того, что в группе из $n$ человек по крайней мере двое имеют одинаковый день рождения. Для простоты вариации в распределении, такие как високосные годы , близнецы , сезонные вариации или вариации дня недели, не принимаются во внимание, и предполагается, что все 365 возможных дней рождения одинаково вероятны. (Распределение дней рождения в реальной жизни не является равномерным, поскольку не все даты одинаково вероятны, но эти отклонения мало влияют на анализ. ^{[Nb 1]} На самом деле, равномерное распределение дат рождения - наихудший случай. ^[5] )

Цель состоит в том, чтобы вычислить $P (A)$ , вероятность того, что по крайней мере два человека в комнате имеют одинаковый день рождения. Однако проще вычислить $P (A')$ , вероятность того, что у двух человек в комнате нет одного дня рождения. Тогда, поскольку $A$ и $A'$ - единственные две возможности, а также взаимоисключающие , $P (A) = 1 - P (A').$

Из уважения к широко опубликованным решениям ^{[ какие? ]} придя к выводу, что 23 - это минимальное количество людей, необходимое для того, чтобы $P (A)$ превышал 50%, следующий расчет $P (A)$ будет использовать 23 человека в качестве примера. Если пронумеровать 23 человека от 1 до 23, событието, что у всех 23 человек разные дни рождения, это то же самое, что и случай, когда у человека 2 не тот же день рождения, что у человека 1, и у этого человека 3 не тот же день рождения, что у человека 1 или человека 2, и так далее, и, наконец, этот человек 23 не имеет того же дня рождения, что и любой из лиц с 1 по 22. Пусть эти события соответственно будут называться «Событие 2», «Событие 3» и так далее. Можно также добавить «Событие 1», соответствующее событию дня рождения человека 1, которое происходит с вероятностью 1. Это сочетание событий может быть вычислено с использованием условной вероятности.: вероятность События 2 составляет 364/365, поскольку у человека 2 может быть любой день рождения, кроме дня рождения человека 1. Точно так же вероятность События 3 с учетом того, что Событие 2 произошло, составляет 363/365, так как человек 3 может иметь любой из дни рождения, которые еще не зарегистрированы лицами 1 и 2. Это продолжается до тех пор, пока, наконец, вероятность события 23, учитывая, что все предшествующие события произошли, составляет 343/365. Наконец, принцип условной вероятности подразумевает, что $P (A')$ равно произведению этих индивидуальных вероятностей:

{\ displaystyle P (A ') = {\ frac {365} {365}} \ times {\ frac {364} {365}} \ times {\ frac {363} {365}} \ times {\ frac {362 } {365}} \ times \ cdots \ times {\ frac {343} {365}}}

( 1 )

Члены уравнения ( 1 ) можно собрать, чтобы получить:

{\ displaystyle P (A ') = \ left ({\ frac {1} {365}} \ right) ^ {23} \ times (365 \ times 364 \ times 363 \ times \ cdots \ times 343)}

( 2 )

Оценка уравнения ( 2 ) дает $P (A') \approx 0,492703$

Следовательно, $P (A) \approx 1 - 0,492703 = 0,507297$ (50,7297%).

Этот процесс можно обобщить на группу из $n$ человек, где $p (n)$ - это вероятность того, что по крайней мере двое из $n$ человек будут праздновать день рождения. Проще сначала вычислить вероятность $p (n) того,$ что все $n$ дней рождения различны . Согласно принципу "голубятни" , $p (n)$ равно нулю, когда $n > 365$ . Когда $n \leq 365$ :

{\begin{aligned}{\bar {p}}(n)&=1\times \left(1-{\frac {1}{365}}\right)\times \left(1-{\frac {2}{365}}\right)\times \cdots \times \left(1-{\frac {n-1}{365}}\right)\\[6pt]&={\frac {365\times 364\times \cdots \times (365-n+1)}{365^{n}}}\\[6pt]&={\frac {365!}{365^{n}(365-n)!}}={\frac {n!\cdot {\binom {365}{n}}}{365^{n}}}={\frac {_{365}P_{n}}{365^{n}}}\end{aligned}}

где $!$ - факториальный оператор, $(365 п)$ -биномиальный коэффициент,а $k P r$ -перестановка.

Уравнение выражает тот факт, что у первого человека некому разделить день рождения, у второго человека не может быть того же дня рождения, что и у первого (364/365), у третьего не может быть того же дня рождения, что и у первых двух (363/365), и, как правило, $n-$ й день рождения не может совпадать с любым из $n - 1$ предшествующих дней рождения.

Событие , по меньшей мере , двух из $п$ лиц , имеющих один и тот же день рождения дополняют друг друга , чтобы все $п$ рождения отличаться от других. Следовательно, его вероятность $p (n)$ равна

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

В следующей таблице показаны вероятности для некоторых других значений $n$ (для этой таблицы наличие високосных лет игнорируется, и предполагается, что каждый день рождения является одинаково вероятным):

Вероятность того, что в группе из

n

человек не бывает одного дня рождения . Обратите внимание, что вертикальная шкала является логарифмической (каждый шаг вниз в ^10-20 раз меньше).

$п$	$п (п)$
1	0 0,0%
5	0 2,7%
10	11,7%
20	41,1%
23	50,7%
30	70,6%
40	89,1%
50	97,0%
60	99,4%
70	99,9%
75	99,97%
100	99,999 97 %
200	99,999 999 999 999 999 999 999 999 9998 %
300	(100 - 6 × 10 ⁻⁸⁰ )%
350	(100 - 3 × 10 ⁻¹²⁹ )%
365	(100 - 1,45 × 10 ⁻¹⁵⁵ )%
≥ 366	100%

Високосные годы . Если мы заменим 366 на 365 в формуле для , аналогичный расчет показывает, что для високосных лет количество людей, необходимое для вероятности совпадения более 50%, также равно 23; вероятность совпадения в этом случае составляет 50,6%. ${\bar {p}}(n)$

Приближения [ править ]

Графики, показывающие приблизительную вероятность того, что как минимум два человека разделяют день рождения ( красный ) и его дополнительное событие ( синий )

График , показывающий точность аппроксимации

1 - е - п 2 / 730

( красный )

Ряд Тейлора разложение показательной функции (константа $е \approx 2,718 281828$ )

e^{x}=1+x+{\frac {x^{2}}{2!}}+\cdots

обеспечивает приближение первого порядка для $e x$ для : $|x|\ll 1$

e^{x}\approx 1+x.

Чтобы применить это приближение к первому выражению, полученному для $p (n)$ , установите $x = - а / 365$ . Таким образом,

e^{-a/365}\approx 1-{\frac {a}{365}}.

Затем замените $a$ неотрицательными целыми числами для каждого члена в формуле $p (n)$ до тех пор, пока $a = n - 1$ , например, когда $a = 1$ ,

e^{-1/365}\approx 1-{\frac {1}{365}}.

Первое выражение, полученное для $p (n),$ можно аппроксимировать как

{\begin{aligned}{\bar {p}}(n)&\approx 1\cdot e^{-1/365}\cdot e^{-2/365}\cdots e^{-(n-1)/365}\\[6pt]&=e^{-\left.{\big (}1+2+\,\cdots \,+(n-1){\big )}\right/365}\\[6pt]&=e^{-(n(n-1)/2)/365}=e^{-n(n-1)/730}.\end{aligned}}

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

p(n)=1-{\bar {p}}(n)\approx 1-e^{-n(n-1)/730}.

Еще более грубое приближение дается формулой

p(n)\approx 1-e^{-n^{2}/730},

что, как показывает график, по-прежнему достаточно точное.

Согласно приближению, тот же подход можно применить к любому количеству «людей» и «дней». Если вместо 365 дней есть $d$ , если есть $n$ человек и если $n ≪ d$ , то, используя тот же подход, что и выше, мы достигаем результата, что если $p (n, d)$ - это вероятность того, что по крайней мере двое из $n$ люди разделяют один и тот же день рождения из набора из $d$ доступных дней, тогда:

{\begin{aligned}p(n,d)&\approx 1-e^{-n(n-1)/(2d)}\\[6pt]&\approx 1-e^{-n^{2}/(2d)}.\end{aligned}}

Простое возведение в степень [ править ]

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

{\bar {p}}(n)\approx \left({\frac {364}{365}}\right)^{\binom {n}{2}}.

Так как это вероятность того, что ни у кого нет одного дня рождения, то вероятность того, что кто-то разделит день рождения, равна

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

Приближение Пуассона [ править ]

Применяя приближение Пуассона для бинома к группе из 23 человек,

\operatorname {Poi} \left({\frac {\binom {23}{2}}{365}}\right)=\operatorname {Poi} \left({\frac {253}{365}}\right)\approx \operatorname {Poi} (0.6932)

так

\Pr(X>0)=1-\Pr(X=0)\approx 1-e^{-0.6932}\approx 1-0.499998=0.500002.

Результат более 50%, как и в предыдущих описаниях. Это приближение такое же, как и приведенное выше, основанное на разложении Тейлора, которое использует . $e^{x}\approx 1+x$

Квадратное приближение [ править ]

Хорошее практическое правило, которое можно использовать для мысленных вычислений, - это соотношение

p(n)\approx {\frac {n^{2}}{2m}}

который также можно записать как

n\approx {\sqrt {2m\times p(n)}}

который хорошо работает для вероятностей, меньших или равных 1/2. В этих уравнениях $m$ - количество дней в году.

Например, чтобы оценить количество людей, необходимое для 1/2 шанс общего дня рождения, мы получаем

n\approx {\sqrt {2\times 365\times {\tfrac {1}{2}}}}={\sqrt {365}}\approx 19

Что не так уж далеко от правильного ответа 23.

Примерное количество человек [ править ]

Это также можно приблизительно оценить, используя следующую формулу для определения количества людей, необходимых для того, чтобы иметь как минимум1/2 шанс совпадения:

n\approx {\tfrac {1}{2}}+{\sqrt {{\tfrac {1}{4}}+2\times \ln(2)\times 365}}=22.999943.

Это результат хорошего приближения того, что событие с $1 / k$ вероятность будет иметь 1/2вероятность появления хотя бы один раз при повторении $k ln 2$ раза. ^[6]

Таблица вероятностей [ править ]

длина шестнадцатеричной строки	нет. из битов ( $б$ )	размер хэш-пространства ( $2 б$ )	Количество хешированных элементов таких, что вероятность хотя бы одного хеш-коллизии ≥ $p$
длина шестнадцатеричной строки	нет. из битов ( $б$ )	размер хэш-пространства ( $2 б$ )	$p$ =10 ⁻¹⁸	$p$ =10 ⁻¹⁵	$p$ =10 ⁻¹²	$p$ =10 ⁻⁹	$p$ =10 ⁻⁶	$р$ = 0,001	$р$ = 0,01	$р$ = 0,25	$р$ = 0,50	$р$ = 0,75
8	32	4,3 × 10 ⁹	2	2	2	2,9	93	2,9 × 10 ³	9,3 × 10 ³	5,0 × 10 ⁴	7,7 × 10 ⁴	1,1 × 10 ⁵
(10)	(40)	(1,1 × 10 ¹² )	2	2	2	47	1,5 × 10 ³	4,7 × 10 ⁴	1,5 × 10 ⁵	8,0 × 10 ⁵	1,2 × 10 ⁶	1,7 × 10 ⁶
(12)	(48)	(2,8 × 10 ¹⁴ )	2	2	24	7,5 × 10 ²	2,4 × 10 ⁴	7,5 × 10 ⁵	2,4 × 10 ⁶	1,3 × 10 ⁷	2,0 × 10 ⁷	2,8 × 10 ⁷
16	64	1,8 × 10 ¹⁹	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 ⁹
(24)	(96)	(7,9 × 10 ²⁸ )	4,0 × 10 ⁵	1,3 × 10 ⁷	4,0 × 10 ⁸	1,3 × 10 ¹⁰	4,0 × 10 ¹¹	1,3 × 10 ¹³	4,0 × 10 ¹³	2,1 × 10 ¹⁴	3,3 × 10 ¹⁴	4,7 × 10 ¹⁴
32	128	3,4 × 10 ³⁸	2,6 × 10 ¹⁰	8,2 × 10 ¹¹	2,6 × 10 ¹³	8,2 × 10 ¹⁴	2,6 × 10 ¹⁶	8,3 × 10 ¹⁷	2,6 × 10 ¹⁸	1,4 × 10 ¹⁹	2,2 × 10 ¹⁹	3,1 × 10 ¹⁹
(48)	(192)	(6,3 × 10 ⁵⁷ )	1,1 × 10 ²⁰	3,5 × 10 ²¹	1,1 × 10 ²³	3,5 × 10 ²⁴	1,1 × 10 ²⁶	3,5 × 10 ²⁷	1,1 × 10 ²⁸	6,0 × 10 ²⁸	9,3 × 10 ²⁸	1,3 × 10 ²⁹
64	256	1,2 × 10 ⁷⁷	4,8 × 10 ²⁹	1,5 × 10 ³¹	4,8 × 10 ³²	1,5 × 10 ³⁴	4,8 × 10 ³⁵	1,5 × 10 ³⁷	4,8 × 10 ³⁷	2,6 × 10 ³⁸	4,0 × 10 ³⁸	5,7 × 10 ³⁸
(96)	(384)	(3,9 × 10 ¹¹⁵ )	8,9 × 10 ⁴⁸	2,8 × 10 ⁵⁰	8,9 × 10 ⁵¹	2,8 × 10 ⁵³	8,9 × 10 ⁵⁴	2,8 × 10 ⁵⁶	8,9 × 10 ⁵⁶	4,8 × 10 ⁵⁷	7,4 × 10 ⁵⁷	1,0 × 10 ⁵⁸
128	512	1,3 × 10 ¹⁵⁴	1,6 × 10 ⁶⁸	5,2 × 10 ⁶⁹	1,6 × 10 ⁷¹	5,2 × 10 ⁷²	1,6 × 10 ⁷⁴	5,2 × 10 ⁷⁵	1,6 × 10 ⁷⁶	8,8 × 10 ⁷⁶	1,4 × 10 ⁷⁷	1,9 × 10 ⁷⁷

Более светлые поля в этой таблице показывают количество хешей, необходимых для достижения заданной вероятности коллизии (столбец) с учетом хеш-пространства определенного размера в битах (строка). Используя аналогию с днем рождения: «размер хеш-пространства» похож на «доступные дни», «вероятность столкновения» похожа на «вероятность общего дня рождения», а «необходимое количество хешированных элементов» похоже на «требуемое количество людей в группа". Можно также использовать эту диаграмму для определения минимального требуемого размера хэша (с учетом верхних границ хешей и вероятности ошибки) или вероятности коллизии (для фиксированного количества хешей и вероятности ошибки).

Для сравнения, ^От 10 ⁻¹⁸ до10 ^-15 - это уровень неисправимых битовых ошибок типичного жесткого диска. ^[7] Теоретически 128-битные хэш-функции, такие как MD5 , должны оставаться в этом диапазоне примерно до8,2 × 10 ¹¹ документов, даже если его возможных выходов намного больше.

Верхняя граница вероятности и нижняя граница количества людей [ править ]

Приведенный ниже аргумент адаптирован из аргумента Пола Халмоса . ^{[nb 2]}

Как указано выше, вероятность того, что никакие два дня рождения не совпадают, равна

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

Как и в предыдущих параграфах, интерес представляет наименьшее $n$ такое, что $p (n)> 1 / 2$ ; или, что то же самое, наименьшее $n$ такое, что $p (n) < 1 / 2$ .

Используя неравенство $1 - x < e - x$ в приведенном выше выражении, заменим $1 - k / 365$ с $е - к / 365$ . Это дает

{\bar {p}}(n)=\prod _{k=1}^{n-1}\left(1-{\frac {k}{365}}\right)<\prod _{k=1}^{n-1}\left(e^{-k/365}\right)=e^{-n(n-1)/730}.

Таким образом, выражение выше, не только приближение, но и верхняя граница по $р (п)$ . Неравенство

e^{-n(n-1)/730}<{\frac {1}{2}}

следует $p (n) < 1 / 2$ . Решение для $n$ дает

n^{2}-n>730\ln 2.

Теперь $730 ln 2$ составляет приблизительно 505,997, что чуть меньше 506, значение $n 2 - n$ достигается при $n = 23$ . Следовательно, достаточно 23 человек. Между прочим, решение $n 2 - n = 730 ln 2$ относительно n дает приблизительную формулу Фрэнка Х. Мэтиса, процитированную выше.

Этот вывод показывает только то, что необходимо не более 23 человек, чтобы обеспечить совпадение по случаю дня рождения с равными шансами; он оставляет открытой возможность того, что $n$ равно 22 или меньше, также может работать.

Обобщения [ править ]

Обобщенная проблема дня рождения [ править ]

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

1-\left(1-{\frac {1}{d}}\right)\left(1-{\frac {2}{d}}\right)\cdots \left(1-{\frac {n-1}{d}}\right)\geq {\frac {1}{2}}.

Таким образом, классическая задача дня рождения соответствует определению $n (365)$ . Здесь приведены первые 99 значений $n (d)$ (последовательность A033810 в OEIS ):

$d$	1–2	3–5	6–9	10–16	17–23	24–32	33–42	43–54	55–68	69–82	83–99
$п (г)$	2	3	4	5	6	7	8	9	10	11	12

Аналогичный расчет показывает, что $n (d)$ = 23, когда $d$ находится в диапазоне 341–372.

Был опубликован ряд оценок и формул для $n (d)$ . ^[8] Для любого $d \geq 1$ число $n (d)$ удовлетворяет ^[9]

{\frac {3-2\ln 2}{6}}<n(d)-{\sqrt {2d\ln 2}}\leq 9-{\sqrt {86\ln 2}}.

Эти оценки оптимальны в том смысле, что последовательность $n (d) - \sqrt 2 d ln 2$ сколь угодно близка к

{\frac {3-2\ln 2}{6}}\approx 0.27,

пока у него есть

9-{\sqrt {86\ln 2}}\approx 1.28

в качестве максимального, взятого при $d = 43$ .

Границы достаточно жесткие, чтобы дать точное значение $n (d)$ в 99% всех случаев, например $n (365) = 23$ . Вообще говоря, из этих оценок следует, что $n (d)$ всегда равно либо

\left\lceil {\sqrt {2d\ln 2}}\,\right\rceil \quad {\text{or}}\quad \left\lceil {\sqrt {2d\ln 2}}\,\right\rceil +1

где $⌈ \cdot ⌉$ обозначает потолочную функцию . Формула

n(d)=\left\lceil {\sqrt {2d\ln 2}}\,\right\rceil

выполняется для 73% всех целых чисел $d$ . ^[10] Формула

n(d)=\left\lceil {\sqrt {2d\ln 2}}+{\frac {3-2\ln 2}{6}}\right\rceil

выполняется почти для всех $d$ , т. е. для набора целых чисел $d$ с асимптотической плотностью 1. ^[10]

Формула

n(d)=\left\lceil {\sqrt {2d\ln 2}}+{\frac {3-2\ln 2}{6}}+{\frac {9-4(\ln 2)^{2}}{72{\sqrt {2d\ln 2}}}}\right\rceil

выполняется для всех $d \leq 1018$ , но предполагается, что существует бесконечно много контрпримеров к этой формуле. ^[11]

Формула

n(d)=\left\lceil {\sqrt {2d\ln 2}}+{\frac {3-2\ln 2}{6}}+{\frac {9-4(\ln 2)^{2}}{72{\sqrt {2d\ln 2}}}}-{\frac {2(\ln 2)^{2}}{135d}}\right\rceil

выполняется для всех $d \leq 1018$ , и предполагается, что эта формула верна для всех $d$ . ^[11]

Более 2 человек [ править ]

Можно расширить проблему, задав вопрос, сколько человек в группе необходимо для того, чтобы с вероятностью более 50% было не менее 3/4/5 и т. Д. группы имеют один день рождения.

Первые несколько значений следующие:> 50% вероятность того, что 3 человека разделяют день рождения - 88 человек; > 50% вероятность того, что 4 человека разделят день рождения - 187 человек. Полный список можно найти как последовательность A014088 в Интернет-энциклопедии целочисленных последовательностей. ^[12]

Cast как проблема столкновения [ править ]

Задачу дня рождения можно обобщить следующим образом:

Для

n

случайных целых чисел, взятых из дискретного равномерного распределения с диапазоном

[1, d]

, какова вероятность

p (n; d) того,

что по крайней мере два числа совпадают? (

d = 365

дает обычную задачу о дне рождения.) ^[13]

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

{\begin{aligned}p(n;d)&={\begin{cases}1-\displaystyle \prod _{k=1}^{n-1}\left(1-{\frac {k}{d}}\right)&n\leq d\\1&n>d\end{cases}}\\[8px]&\approx 1-e^{-{\frac {n(n-1)}{2d}}}\\&\approx 1-\left({\frac {d-1}{d}}\right)^{\frac {n(n-1)}{2}}\end{aligned}}

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

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

Проблема рождения в этом более широком смысле относится к хэш - функций : ожидаемое число $N$ - битных хешей , которые могут быть сгенерированы перед тем , как столкновение не $2 N$ , а только $2 N / 2$ . Это используется атаками по случаю дня рождения на криптографические хеш-функции и является причиной того, что небольшое количество коллизий в хеш-таблице для всех практических целей неизбежно.

Теория, лежащая в основе проблемы дня рождения, была использована Зои Шнабель ^[14] под названием статистики вылова-повторной поимки для оценки размера популяции рыб в озерах.

Обобщение на несколько типов [ править ]

График вероятности хотя бы одного общего дня рождения хотя бы у одного мужчины и одной женщины

В основной задаче все испытания считаются однотипными. Задача дня рождения была обобщена для рассмотрения произвольного числа типов. ^[15] В простейшем случае есть два типа людей, скажем, $m$ мужчин и $n$ женщин, и проблема заключается в том, чтобы характеризовать вероятность общего дня рождения хотя бы одного мужчины и одной женщины. (Общие дни рождения двух мужчин или двух женщин не учитываются.) Вероятность отсутствия общих дней рождения здесь равна

p_{0}={\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 2$ - числа Стирлинга второго рода . Следовательно, желаемая вероятность равна $1 - p 0$ .

Этот вариант задачи о дне рождения интересен тем, что не существует единственного решения для общего числа людей $m + n$ . Например, обычное значение вероятности 50% реализуется как для группы из 32 человек, состоящей из 16 мужчин и 16 женщин, так и для группы из 49 человек, состоящей из 43 женщин и 6 мужчин.

Другие проблемы с днем рождения [ править ]

Первый матч [ править ]

Связанный с этим вопрос: когда люди входят в комнату по одному, у кого из них, скорее всего, будет тот же день рождения, что и у кого-то, кто уже находится в комнате? То есть, за что $п$ является $р (п) - р (п - 1)$ максимум? Ответ - 20 - если есть приз за первый матч, лучшая позиция в очереди - 20-е. ^{[ необходима цитата ]}

В тот же день рождения, что и вы [ править ]

Сравнивая

р (п)

= вероятность встречи рождения с

д (п)

= вероятность соответствия вашего рождения

В задаче о дне рождения ни один из двух человек заранее не выбран. Напротив, вероятность $q (n) того,$ что кто-то в комнате из $n$ других людей имеет тот же день рождения, что и конкретный человек (например, вы), определяется как

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

и для общего $г$ по

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

В стандартном случае $d = 365$ подстановка $n = 23$ дает около 6,1%, что меньше 1 шанса из 16. Для шанса более 50%, что один человек в комнате, заполненной $n$ людьми, имеет тот же день рождения, что и вы , $n$ должно быть не менее 253. Это число значительно больше, чем $365 / 2 = 182,5$ : причина в том, что, вероятно, есть совпадения по дням рождения среди других людей в комнате.

Ближайшие совпадения [ править ]

Другое обобщение - спросить о вероятности нахождения хотя бы одной пары в группе из $n$ человек, дни рождения которых находятся в пределах $k$ календарных дней друг от друга, если существует $d$ равновероятных дней рождения. ^[16]

{\begin{aligned}p(n,k,d)&=1-{\frac {(d-nk-1)!}{d^{n-1}{\bigl (}d-n(k+1){\bigr )}!}}\end{aligned}}

Количество людей, необходимое для того, чтобы вероятность того, что у какой-то пары день рождения разделится на $k$ дней или меньше, будет выше 50%, приведено в следующей таблице:

$k$	$n$ для $d = 365$
0	23
1	14
2	11
3	9
4	8
5	8
6	7
7	7

Таким образом, в группе из семи случайных людей более вероятно, что у двоих из них будет день рождения в пределах недели друг от друга. ^[16]

Подсчет столкновений [ править ]

Вероятность того, что $k-$ е целое число, случайно выбранное из $[1, d]$ , повторит хотя бы один предыдущий выбор, равна $q (k - 1; d)$ выше. Ожидаемое общее количество раз, когда выборка будет повторять предыдущий выбор, если выбрано $n$ таких целых чисел, равное ^[17]

\sum _{k=1}^{n}q(k-1;d)=n-d+d\left({\frac {d-1}{d}}\right)^{n}.

Среднее количество людей [ править ]

В альтернативной формулировке задачи о дне рождения спрашивают, сколько людей в среднем требуется, чтобы найти пару с одинаковым днем рождения. Если мы рассмотрим функцию вероятности Pr [ $n$ людей имеют хотя бы один общий день рождения], это среднее значение определяет среднее значение распределения, в отличие от обычной формулировки, которая требует медианы . Проблема актуальна для нескольких алгоритмов хеширования, проанализированных Дональдом Кнутом в его книге «Искусство компьютерного программирования» . Можно показать ^[18]^[19], что если взять единообразную выборку с заменой из совокупности размера $M$ , количество испытаний, необходимое для первого повторного отбора проб от некоторого человека, имеет ожидаемое значение $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 .

При $M = 365$ дней в году среднее количество людей, необходимое для поиска пары с одинаковым днем рождения, равно $n = 1 + Q (M) \approx 24,61659$ , что несколько больше 23, число, необходимое для 50% вероятности. В лучшем случае хватит двух человек; в худшем случае нужно максимально возможное количество $M + 1 = 366$ человек; но в среднем требуется всего 25 человек

Анализ с использованием индикаторных случайных величин может дать более простой, но приблизительный анализ этой проблемы. ^[20] Для каждой пары (i, j) для k человек в комнате мы определяем индикаторную случайную величину X _ij для , как $1\leq i\leq j\leq k$

${\begin{alignedat}{2}X_{ij}&=I\{{\text{person }}i{\text{ and person }}j{\text{ have the same birthday}}\}\\&={\begin{cases}1,&{\text{if person }}i{\text{ and person }}j{\text{ have the same birthday;}}\\0,&{\text{otherwise.}}\end{cases}}\end{alignedat}}$

${\begin{alignedat}{2}E[X_{ij}]&=\Pr\{{\text{person }}i{\text{ and person }}j{\text{ have the same birthday}}\}\\&=1/n\end{alignedat}}$

Пусть X - случайная величина, считающая пары людей с одним днем рождения.

$X=\sum _{i=1}^{k}\sum _{j=i+1}^{k}X_{ij}$

${\begin{alignedat}{3}E[X]&=\sum _{i=1}^{k}\sum _{j=i+1}^{k}E[X_{ij}]\\&={\binom {k}{2}}{\frac {1}{n}}\\&={\frac {k(k-1)}{2n}}\\\end{alignedat}}$

Для $n = 365$ , если $k = 28$ , ожидаемое количество с одинаковым днем рождения равно. Следовательно, мы можем ожидать, по крайней мере, одну подходящую пару, по крайней мере, из 28 человек. $(28\cdot 27)/(2\cdot 365)\approx 1.0356.$

Неформальная демонстрация проблемы может быть сделана из списка премьер-министров Австралии , которого по состоянию на 2017 год было 29 ^[update], в котором Пол Китинг , 24-й премьер-министр, и Эдмунд Бартон , первый премьер-министр, разделяют то же самое. день рождения, 18 января.

На чемпионате мира по футболу 2014 года в каждой из 32 команд было по 23 игрока. Анализ официальных списков команд показал, что у 16 команд были пары игроков, у которых были дни рождения, и из этих 5 команд было две пары: Аргентина, Франция, Иран, Южная Корея и Швейцария имели по две пары, а Австралия, Босния и Герцеговина, Бразилия. , Камерун, Колумбия, Гондурас, Нидерланды, Нигерия, Россия, Испания и США - каждая по одной паре. ^[21]

Ворачек, Тран и Форманн показали, что большинство людей заметно переоценивают количество людей, необходимое для достижения заданной вероятности того, что люди имеют один и тот же день рождения, и заметно недооценивают вероятность того, что люди имеют один и тот же день рождения, если дан конкретный размер выборки. . ^[22] Дальнейшие результаты показали, что студенты-психологи и женщины справились с задачей лучше, чем посетители / персонал казино или мужчины, но были менее уверены в своих оценках.

Обратная задача [ править ]

Обратная задача состоит в том, чтобы найти для фиксированной вероятности $p$ наибольшее $n,$ для которого вероятность $p (n)$ меньше заданного $p$ , или наименьшее $n,$ для которого вероятность $p (n)$ больше заданного $p$ . ^{[ необходима цитата ]}

Принимая приведенную выше формулу для $d = 365$ , имеем

n(p;365)\approx {\sqrt {730\ln \left({\frac {1}{1-p}}\right)}}.

В следующей таблице приведены некоторые примеры расчетов.

$п$	$п$	$п ↓$	$п (п ↓)$	$п ↑$	$п (п ↑)$
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

Некоторые значения, выходящие за границы, были окрашены, чтобы показать, что приближение не всегда является точным.

Проблема с разделом [ править ]

Смежная проблема - это проблема разбиения , вариант задачи о ранце из исследования операций. Некоторые гири ставятся на весы ; каждый вес представляет собой целое число граммов, случайно выбранных от одного грамма до одного миллиона граммов (одна тонна). Вопрос в том, можно ли обычно (то есть с вероятностью, близкой к 1) переносить веса между левой и правой рукой, чтобы сбалансировать весы. (В случае, если сумма всех весов - нечетное количество граммов, допускается отклонение в один грамм.) Если есть только два или три веса, ответ, безусловно, отрицательный; хотя есть некоторые комбинации, которые работают, большинство случайно выбранных комбинаций трех весов не работают. Если весов очень много, ответ однозначно положительный. Вопрос в том, сколько всего достаточно? То есть, какое количество гирь такое, что уравновесить их с равной вероятностью можно будет, поскольку это невозможно?

Часто интуиция подсказывает, что ответ выше. 100 000 . Интуиция большинства людей подсказывает, что они исчисляются тысячами или десятками тысяч, в то время как другие считают, что их должны быть как минимум сотни. Правильный ответ - 23. ^{[ необходима ссылка ]}

Причина в том, что правильное сравнение заключается в количестве разделений весов на левую и правую. Существует $2 N - 1$ различных разделов для $N$ весов, и левую сумму за вычетом правой суммы можно рассматривать как новую случайную величину для каждого раздела. Распределение суммы весов приблизительно гауссово с максимумом на $1000000 Н$ и ширина $Один 000000 \sqrt Н$ , так чтокогда $2 Н - 1$ приблизительно равно $1000000 \sqrt N$ переход происходит. 2^{23 - 1} составляет около 4 миллионов, тогда как ширина распределения составляет всего 5 миллионов. ^[23]

В художественной литературе [ править ]

Роман Артура Кларка « Падение лунной пыли» , опубликованный в 1961 году, содержит раздел, в котором главные герои, оказавшиеся в ловушке под землей на неопределенное время, празднуют день рождения и обнаруживают, что обсуждают обоснованность проблемы дня рождения. Как сказал пассажир-физик: «Если у вас группа из более чем двадцати четырех человек, шансы даже выше, чем даже у двоих из них в один день рождения». В конце концов, из 22 присутствующих выясняется, что у двух персонажей один день рождения, 23 мая.

Примечания [ править ]

^
На самом деле дни рождения распределяются в течение года неравномерно; в одни сезоны рождается больше детей в день, чем в другие, но для решения этой проблемы распределение считается равномерным. В частности, многие дети рождаются летом, особенно в августе и сентябре (для северного полушария) [1] , а в США было отмечено, что многие дети рождаются в период рождественских и новогодних праздников. .^[1] Кроме того, поскольку в больницах редко назначают кесарево сечение и искусственные роды на выходные, между вторником и пятницей рождается больше людей, чем в выходные дни;^[1]когда у многих людей один год рождения (например, в классе в школе), это создает тенденцию к определенным датам. В Швеции 9,3% населения родилось в марте и 7,3% в ноябре, когда равномерное распределение дало бы 8,3% шведского статистического управления . Смотрите также:
- Мерфи, Рон. «Анализ распределения дней рождения в календарном году» . Проверено 27 декабря 2011 .
- Mathers, CD; RS Harris (1983). «Сезонное распределение рождений в Австралии» . Международный журнал эпидемиологии . 12 (3): 326–331. DOI : 10.1093 / ije / 12.3.326 . PMID 6629621 . Проверено 27 декабря 2011 .
Эти факторы, как правило, увеличивают вероятность идентичных дат рождения, поскольку более плотное подмножество имеет больше возможных пар (в крайнем случае, когда все родились в три дня, очевидно, будет много одинаковых дней рождения). Проблема неравномерного количества рождений, происходящих в течение каждого дня в году, была впервые понята Мюрреем Кламкиным в 1967 году. ^[4] Формальное доказательство того, что вероятность двух совпадающих дней рождения является наименьшей для равномерного распределения дней рождения, было дано Блум ( Bloom 1973 ).
↑ В своей автобиографии Халмос подверг критике форму, в которой часто представляется парадокс дня рождения, с точки зрения числовых вычислений. Он считал, что это следует использовать как пример использования более абстрактных математических понятий. Он написал:
Рассуждения основаны на важных инструментах, к которым все студенты-математики должны иметь свободный доступ. Проблема дня рождения была великолепной иллюстрацией преимуществ чистого мышления перед механическими манипуляциями; неравенства могут быть получены за минуту или две, тогда как умножение займет гораздо больше времени и будет гораздо более подвержено ошибкам, независимо от того, является ли инструмент карандашом или старомодным настольным компьютером. Что калькуляторы не дают понимание, или математический объект, или прочную основу для более продвинутых, обобщенных теорий.

Ссылки [ править ]

^ a b c Марио Кортина Борха; Джон Хей (сентябрь 2007 г.). «Проблема дня рождения» . Значение . Королевское статистическое общество. 4 (3): 124–127. DOI : 10.1111 / j.1740-9713.2007.00246.x .
↑ WW Rouse Ball и HSM Coxeter , "Mathematical Recreations and Essays, 13th edition", Dover Publications, New York, 1987, p 45.
^ Франк, P .; Goldstein, S .; Kac, M .; Prager, W .; Szegö, G .; Биркгоф, Г., ред. (1964). Избранные статьи Рихарда фон Мизеса . 2 . Провиденс, Род-Айленд: амер. Математика. Soc. С. 313–334.
^ Klamkin & Newman 1967 .
^ Стил, Дж. Майкл (2004). Мастер-класс Коши-Шварца . Кембридж: Издательство Кембриджского университета. стр. 206 , 277. ISBN 9780521546775.
Перейти ↑ Mathis, Frank H. (июнь 1991). «Обобщенная проблема дня рождения» . SIAM Обзор . 33 (2): 265–270. DOI : 10.1137 / 1033051 . ISSN 0036-1445 . JSTOR 2031144 . OCLC 37699182 .
^ Джим Грей, Кэтрин ван Инген. Эмпирические измерения частоты отказов дисков и ошибок
^ Д. Бринк, (вероятно) точное решение проблемы дней рождения, Ramanujan Journal, 2012, [2] .
^ Бринк 2012 , теорема 2
^ a b Brink 2012 , теорема 3
^ a b Brink 2012 , таблица 3, гипотеза 1
^ «Минимальное количество людей, дающее 50% вероятность иметь по крайней мере n совпадающих дней рождения в течение одного года» . Он-лайн энциклопедия целочисленных последовательностей . OEIS . Дата обращения 17 февраля 2020 .
^ Suzuki, K .; Tonien, D .; и другие. (2006). «Парадокс дня рождения для множественных столкновений». В Ри М.С., Ли Б. (ред.). Конспект лекций по информатике, том 4296 . Берлин: Springer. DOI : 10.1007 / 11927587_5 . Информационная безопасность и криптология - ICISC 2006.
↑ ZE Schnabel (1938) Оценка общей популяции рыб в озере , American Mathematical Monthly 45 , 348–352.
^ MC Wendl (2003) Вероятность столкновения между наборами случайных величин, статистикой и вероятностными буквами 64 (3), 249–254.
^ a b М. Абрамсон и У. Дж. Мозер (1970) Еще сюрпризы на день рождения , American Mathematical Monthly 77 , 856–858
^ Могу, Мэтт. «Столкновение хеш-коллизий с парадоксом дня рождения» . Блог Мэтта Мая . Проверено 17 июля 2015 года .
^ Knuth, DE (1973). Искусство программирования . Vol. 3, Сортировка и поиск. Ридинг, Массачусетс: Эддисон-Уэсли. ISBN 978-0-201-03803-3.
^ Flajolet, P .; Grabner, PJ; Kirschenhofer, P .; Продингер, Х. (1995). «О Q-функции Рамануджана» . Журнал вычислительной и прикладной математики . 58 : 103–116. DOI : 10.1016 / 0377-0427 (93) E0258-N .
^ Кормен; и другие. Введение в алгоритмы .
↑ Флетчер, Джеймс (16 июня 2014 г.). «Парадокс дня рождения на чемпионате мира» . bbc.com . BBC . Проверено 27 августа 2015 года .
^ Voracek, M .; Тран, США; Форманн, АК (2008). "День рождения и проблемы с партнером по рождению: неправильные представления о вероятности среди студентов-психологов, посетителей и персонала казино". Перцептивные и моторные навыки . 106 (1): 91–103. DOI : 10,2466 / pms.106.1.91-103 . PMID 18459359 . S2CID 22046399 .
^ Borgs, C .; Chayes, J .; Питтель, Б. (2001). «Фазовый переход и масштабирование конечного размера в задаче целочисленного разбиения». Случайные структуры и алгоритмы . 19 (3–4): 247–288. DOI : 10.1002 / rsa.10004 . S2CID 6819493 .

Библиография [ править ]

Abramson, M .; Мозер, WOJ (1970). «Еще сюрпризы на день рождения». Американский математический ежемесячник . 77 (8): 856–858. DOI : 10.2307 / 2317022 . JSTOR 2317022 .
Блум, Д. (1973). «Проблема дня рождения». Американский математический ежемесячник . 80 (10): 1141–1142. DOI : 10.2307 / 2318556 . JSTOR 2318556 .
Кемени, Джон Дж .; Снелл, Дж. Лори; Томпсон, Джеральд (1957). Введение в конечную математику (Первое изд.).
Кламкин, М .; Ньюман, Д. (1967). «Продление сюрприза на день рождения» . Журнал комбинаторной теории . 3 (3): 279–282. DOI : 10.1016 / s0021-9800 (67) 80075-9 .
Маккинни, EH (1966). «Обобщенная проблема дня рождения». Американский математический ежемесячник . 73 (4): 385–387. DOI : 10.2307 / 2315408 . JSTOR 2315408 .
Шнепс, Лейла ; Колмез, Корали (2013). «Математическая ошибка номер 5. Случай Дайаны Сильвестр: анализ холодного попадания». Математика на пробу. Как числа используются и злоупотребляют в зале суда . Основные книги. ISBN 978-0-465-03292-1.
Сай М. Блиндер (2013). Руководство по основам математики: обзор для студентов-физиков, химиков и инженеров . Эльзевир. С. 5–6. ISBN 978-0-12-407163-6.

Внешние ссылки [ править ]

Парадокс дня рождения с учетом дней рождения в високосном году
Вайсштейн, Эрик В. «Проблема дня рождения» . MathWorld .
Юмористическая статья, объясняющая парадокс
Эксперимент по случаю дня рождения SOCR EduMaterials
Понимание проблемы дня рождения (объяснение лучше)
Евророждение 2012. Проблема дня рождения. Практический футбольный пример парадокса дня рождения.
Грайм, Джеймс. «23: Вероятность дня рождения» . Numberphile . Брэди Харан . Архивировано из оригинала на 2017-02-25 . Проверено 2 апреля 2013 .
Вычисление вероятностей проблемы рождения в WolframAlpha

[nonuniform_birthdays-5] На самом деле дни рождения распределяются в течение года неравномерно; в одни сезоны рождается больше детей в день, чем в другие, но для решения этой проблемы распределение считается равномерным. В частности, многие дети рождаются летом, особенно в августе и сентябре (для северного полушария) [1] , а в США было отмечено, что многие дети рождаются в период рождественских и новогодних праздников. .^[1] Кроме того, поскольку в больницах редко назначают кесарево сечение и искусственные роды на выходные, между вторником и пятницей рождается больше людей, чем в выходные дни;^[1]когда у многих людей один год рождения (например, в классе в школе), это создает тенденцию к определенным датам. В Швеции 9,3% населения родилось в марте и 7,3% в ноябре, когда равномерное распределение дало бы 8,3% шведского статистического управления . Смотрите также:
Мерфи, Рон. «Анализ распределения дней рождения в календарном году» . Проверено 27 декабря 2011 .
Mathers, CD; RS Harris (1983). «Сезонное распределение рождений в Австралии» . Международный журнал эпидемиологии . 12 (3): 326–331. DOI : 10.1093 / ije / 12.3.326 . PMID 6629621 . Проверено 27 декабря 2011 .
Эти факторы, как правило, увеличивают вероятность идентичных дат рождения, поскольку более плотное подмножество имеет больше возможных пар (в крайнем случае, когда все родились в три дня, очевидно, будет много одинаковых дней рождения). Проблема неравномерного количества рождений, происходящих в течение каждого дня в году, была впервые понята Мюрреем Кламкиным в 1967 году. ^[4] Формальное доказательство того, что вероятность двух совпадающих дней рождения является наименьшей для равномерного распределения дней рождения, было дано Блум ( Bloom 1973 ).

[2] Мерфи, Рон. «Анализ распределения дней рождения в календарном году» . Проверено 27 декабря 2011 .

[3] Mathers, CD; RS Harris (1983). «Сезонное распределение рождений в Австралии» . Международный журнал эпидемиологии . 12 (3): 326–331. DOI : 10.1093 / ije / 12.3.326 . PMID 6629621 . Проверено 27 декабря 2011 .

[9] В своей автобиографии Халмос подверг критике форму, в которой часто представляется парадокс дня рождения, с точки зрения числовых вычислений. Он считал, что это следует использовать как пример использования более абстрактных математических понятий. Он написал:
Рассуждения основаны на важных инструментах, к которым все студенты-математики должны иметь свободный доступ. Проблема дня рождения была великолепной иллюстрацией преимуществ чистого мышления перед механическими манипуляциями; неравенства могут быть получены за минуту или две, тогда как умножение займет гораздо больше времени и будет гораздо более подвержено ошибкам, независимо от того, является ли инструмент карандашом или старомодным настольным компьютером. Что калькуляторы не дают понимание, или математический объект, или прочную основу для более продвинутых, обобщенных теорий.

[Borja-1] Марио Кортина Борха; Джон Хей (сентябрь 2007 г.). «Проблема дня рождения» . Значение . Королевское статистическое общество. 4 (3): 124–127. DOI : 10.1111 / j.1740-9713.2007.00246.x .

[2] WW Rouse Ball и HSM Coxeter , "Mathematical Recreations and Essays, 13th edition", Dover Publications, New York, 1987, p 45.

[3] Франк, P .; Goldstein, S .; Kac, M .; Prager, W .; Szegö, G .; Биркгоф, Г., ред. (1964). Избранные статьи Рихарда фон Мизеса . 2 . Провиденс, Род-Айленд: амер. Математика. Soc. С. 313–334.

[FOOTNOTEKlamkinNewman1967-4] Klamkin & Newman 1967 .

[6] Стил, Дж. Майкл (2004). Мастер-класс Коши-Шварца . Кембридж: Издательство Кембриджского университета. стр. 206 , 277. ISBN 9780521546775.

[7] Перейти ↑ Mathis, Frank H. (июнь 1991). «Обобщенная проблема дня рождения» . SIAM Обзор . 33 (2): 265–270. DOI : 10.1137 / 1033051 . ISSN 0036-1445 . JSTOR 2031144 . OCLC 37699182 .

[8] Джим Грей, Кэтрин ван Инген. Эмпирические измерения частоты отказов дисков и ошибок

[10] Д. Бринк, (вероятно) точное решение проблемы дней рождения, Ramanujan Journal, 2012, [2] .

[11] Бринк 2012 , теорема 2

[Brink-12] Brink 2012 , теорема 3

[ReferenceA-13] Brink 2012 , таблица 3, гипотеза 1

[14] «Минимальное количество людей, дающее 50% вероятность иметь по крайней мере n совпадающих дней рождения в течение одного года» . Он-лайн энциклопедия целочисленных последовательностей . OEIS . Дата обращения 17 февраля 2020 .

[15] Suzuki, K .; Tonien, D .; и другие. (2006). «Парадокс дня рождения для множественных столкновений». В Ри М.С., Ли Б. (ред.). Конспект лекций по информатике, том 4296 . Берлин: Springer. DOI : 10.1007 / 11927587_5 . Информационная безопасность и криптология - ICISC 2006.

[16] ZE Schnabel (1938) Оценка общей популяции рыб в озере , American Mathematical Monthly 45 , 348–352.

[17] MC Wendl (2003) Вероятность столкновения между наборами случайных величин, статистикой и вероятностными буквами 64 (3), 249–254.

[abramson-18] М. Абрамсон и У. Дж. Мозер (1970) Еще сюрпризы на день рождения , American Mathematical Monthly 77 , 856–858

[19] Могу, Мэтт. «Столкновение хеш-коллизий с парадоксом дня рождения» . Блог Мэтта Мая . Проверено 17 июля 2015 года .

[knuth73-20] Knuth, DE (1973). Искусство программирования . Vol. 3, Сортировка и поиск. Ридинг, Массачусетс: Эддисон-Уэсли. ISBN 978-0-201-03803-3.

[flajolet95-21] Flajolet, P .; Grabner, PJ; Kirschenhofer, P .; Продингер, Х. (1995). «О Q-функции Рамануджана» . Журнал вычислительной и прикладной математики . 58 : 103–116. DOI : 10.1016 / 0377-0427 (93) E0258-N .

[22] Кормен; и другие. Введение в алгоритмы .

[23] Флетчер, Джеймс (16 июня 2014 г.). «Парадокс дня рождения на чемпионате мира» . bbc.com . BBC . Проверено 27 августа 2015 года .

[24] Voracek, M .; Тран, США; Форманн, АК (2008). "День рождения и проблемы с партнером по рождению: неправильные представления о вероятности среди студентов-психологов, посетителей и персонала казино". Перцептивные и моторные навыки . 106 (1): 91–103. DOI : 10,2466 / pms.106.1.91-103 . PMID 18459359 . S2CID 22046399 .

[25] Borgs, C .; Chayes, J .; Питтель, Б. (2001). «Фазовый переход и масштабирование конечного размера в задаче целочисленного разбиения». Случайные структуры и алгоритмы . 19 (3–4): 247–288. DOI : 10.1002 / rsa.10004 . S2CID 6819493 .

[1]