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

Годовые изменения показателей смертности см. в разделе « Эффект дня рождения» . Чтобы узнать о математической головоломке, которую задавали на математической олимпиаде, см. День рождения Шерил .

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

В теории вероятностей задача о дне рождения предполагает вероятность того, что из n случайно выбранных людей хотя бы у двоих день рождения будет одинаковым . Парадокс дня рождения связан с противоречивым фактом, что для того, чтобы вероятность превысить 50%, необходимо всего 23 человека.

Парадокс дня рождения — это настоящий парадокс : на первый взгляд он кажется неправильным, но на самом деле это правда. Хотя может показаться удивительным, что для достижения 50%-ной вероятности общего дня рождения требуется всего 23 человека, этот результат становится более интуитивным, если учесть, что сравнения дней рождения будут проводиться между каждой возможной парой людей. Из 23 человек есть ⁠ 23 × 22/2 ⁠ = 253 пары , которые следует учитывать, что намного больше половины количества дней в году.

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

Эту проблему обычно приписывают Гарольду Дэвенпорту примерно в 1927 году, хотя он тогда не опубликовал ее. Давенпорт не претендовал на роль его первооткрывателя, «потому что не мог поверить, что об этом не было заявлено ранее». Первую версию задачи о дне рождения опубликовал Рихард фон Мизес в 1939 году.

Вычисление вероятности

С точки зрения перестановок , пусть событием А будет вероятность найти группу из 23 человек без повторяющихся дней рождения. Если событие B — это вероятность найти группу из 23 человек, в которой по крайней мере два человека имеют один и тот же день рождения, P ( B ) = 1 — P ( A ) . P ( A ) – отношение общего числа дней рождения, $V_{nr}$, без повторений и порядка (например, для группы из 2 человек, формат дня рождения мм/дд, один из возможных результатов: $\left\{\left\{01/02,05/20\right\},\left\{05/20,01/02\right\},\left\{10/02,08/04\right\},...\right\}$) разделить на общее количество дней рождения с учетом повторений и порядка, $V_{t}$, поскольку это общее пространство результатов эксперимента (например, 2 человека, один из возможных результатов — $\left\{\left\{01/02,01/02\right\},\left\{10/02,08/04\right\},...\right\}$). Поэтому $V_{nr}$ и $V_{t}$ являются перестановками .

${\begin{aligned}V_{nr}&={\frac {n!}{(n-k)!}}={\frac {365!}{(365-23)!}}\\[8pt]V_{t}&=n^{k}=365^{23}\\[8pt]P(A)&={\frac {V_{nr}}{V_{t}}}\approx 0.492703\\[8pt]P(B)&=1-P(A)\approx 1-0.492703\approx 0.507297\quad (50.7297\%)\end{aligned}}$

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

Для независимых дней рождения равномерное распределение дней рождения сводит к минимуму вероятность того, что у двух человек в группе будет один и тот же день рождения. Любая неравномерность увеличивает вероятность того, что у двух людей день рождения будет совпадать. Однако реальные дни рождения не настолько неравномерны, чтобы что-то изменить: размер реальной группы, необходимый для того, чтобы вероятность общего дня рождения была более 50%, равна 23, как и в теоретическом равномерном распределении.

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

Вот расчет P ( B ) для 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 ′) равно произведению этих отдельных вероятностей:

$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 ) можно объединить, чтобы получить:

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

Вычисление уравнения ( 2 ) дает P ( A ′) ≈ 0,492703.

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

Этот процесс можно обобщить на группу из n человек, где p ( n ) — вероятность того, что по крайней мере у двух из n человек день рождения совпадет. Проще сначала вычислить вероятность p ( n ) того, что все n дней рождения разные . Согласно принципу «ячейки» , p ( n ) равно нулю, когда n > 365 . Когда n ≤ 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}}$

где ! — оператор факториала , ( ³⁶⁵
_n ) — биномиальный коэффициент , а _k P _r обозначает перестановку .

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

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

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

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

Вероятность того, что никакие два человека в группе из n человек не имеют одинаковых дней рождения. Обратите внимание, что вертикальный масштаб логарифмический (каждый шаг вниз равен 10). ²⁰ раз менее вероятно).

н	п ( п )
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 −80 )%
350	(100 − 3 × 10 −129 )%
365	(100 − 1.45 × 10 −155 )%
≥ 366	100%

Приближения

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

График, показывающий точность аппроксимации 1 − e ^{− п 2 /730} ( красный )

( в ряд Тейлора Разложение показательной функции константа e ≈ 2,718 281 828 )

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

обеспечивает приближение первого порядка для e ^х для $|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^{-{\big (}1+2+\,\cdots \,+(n-1){\big )}/365}\\[6pt]&=e^{-{\frac {n(n-1)/2}{365}}}=e^{-{\frac {n(n-1)}{730}}}.\end{aligned}}$

Поэтому,

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

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

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

который, как показывает график, все еще довольно точен.

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

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

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

Вероятность того, что у любых двух людей день рождения не совпадет, равна ⁠ 364/365 ​ ​ ⁠ . В комнате, содержащей n человек, находятся ( ^н
₂ ) = ⁠ n ( n − 1) / 2 ⁠ пар людей, т.е. ( ^н
₂ ) события. Вероятность того, что никакие два человека не родятся в один и тот же день рождения, можно приблизительно определить, если предположить, что эти события независимы, и, следовательно, перемножив их вероятность. Быть независимым было бы равносильно выбору замены любой пары людей в мире, а не только в комнате. Суммируя ⁠ 364/365 ⁠ на ( можно умножить само себя ^н
₂ ) раз, что дает нам

${\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 человек вероятность поделиться равна

$p(23)\approx 1-\left({\frac {364}{365}}\right)^{\binom {23}{2}}=1-\left({\frac {364}{365}}\right)^{253}\approx 0.500477.$

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

Применяя приближение Пуассона для бинома на группе из 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 ^х ≈ 1 + х .

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

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

$p(n,d)\approx {\frac {n^{2}}{2d}}$

что также можно записать как

$n\approx {\sqrt {2d\times p(n)}}$

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

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

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

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

Примерное количество человек

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

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

Это результат хорошего приближения, согласно которому событие с ⁠ 1 / k ⁠ вероятность будет иметь ⁠ 1/2 хотя бы один раз , ⁠ вероятность появления если оно повторяется k ln 2 раза.

Таблица вероятностей

Основная статья: Атака на день рождения

длина шестнадцатеричная строка	нет. из биты ( б )	хеш-пространство размер ( 2 б )	Количество хешированных элементов, при которых вероятность хотя бы одного хеш-коллизии ≥ p
			р = 10 −18	р = 10 −15	р = 10 −12	р = 10 −9	р = 10 −6	р = 0,001	р = 0,01	р = 0,25	р = 0,50	р = 0,75
8	32	4.3 × 10 9	2	2	2	2.9	93	2.9 × 10 3	9.3 × 10 3	5.0 × 10 4	7.7 × 10 4	1.1 × 10 5
(10)	(40)	( 1.1 × 10 12 )	2	2	2	47	1.5 × 10 3	4.7 × 10 4	1.5 × 10 5	8.0 × 10 5	1.2 × 10 6	1.7 × 10 6
(12)	(48)	( 2.8 × 10 14 )	2	2	24	7.5 × 10 2	2.4 × 10 4	7.5 × 10 5	2.4 × 10 6	1.3 × 10 7	2.0 × 10 7	2.8 × 10 7
16	64	1.8 × 10 19	6.1	1.9 × 10 2	6.1 × 10 3	1.9 × 10 5	6.1 × 10 6	1.9 × 10 8	6.1 × 10 8	3.3 × 10 9	5.1 × 10 9	7.2 × 10 9
(24)	(96)	( 7.9 × 10 28 )	4.0 × 10 5	1.3 × 10 7	4.0 × 10 8	1.3 × 10 10	4.0 × 10 11	1.3 × 10 13	4.0 × 10 13	2.1 × 10 14	3.3 × 10 14	4.7 × 10 14
32	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
(48)	(192)	( 6.3 × 10 57 )	1.1 × 10 20	3.5 × 10 21	1.1 × 10 23	3.5 × 10 24	1.1 × 10 26	3.5 × 10 27	1.1 × 10 28	6.0 × 10 28	9.3 × 10 28	1.3 × 10 29
64	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
(96)	(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
128	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

Сравнение проблемы дня рождения (1) и атаки дня рождения (2):

В (1) столкновения обнаружены в пределах одного набора, в данном случае 3 из 276 пар 24 лунных астронавтов.

В (2) обнаружены коллизии между двумя наборами, в данном случае 1 из 256 пар только первых байтов SHA-256 хэшей по 16 вариантов каждого из доброкачественных и вредных контрактов.

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

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

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

Приведенный ниже аргумент адаптирован из аргумента Пола Халмоша .

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

$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 ^{− х} в приведенном выше выражении мы заменяем 1 — ⁠ к / 365 ⁠ с е ^{− k ⁄ 365} . Это дает

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

Следовательно, выражение выше является не только приближением, но и границей верхней p ( n ) . Неравенство

$e^{-{\frac {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 ² − n достигается, когда n = 23 . Поэтому 23 человека достаточно. Кстати, решение n ² − 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 ):

д	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 ) . Был опубликован Для любого d ≥ 1 число n ( d ) удовлетворяет условию

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

Эти границы оптимальны в том смысле, что последовательность n ( d ) − √ 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 ) в большинстве случаев. Например, для d = 365 эти границы подразумевают, что 22,7633 < n (365) < 23,7736 и 23 — единственное целое число в этом диапазоне. В общем случае из этих границ следует, что n ( d ) всегда равно либо

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

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

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

справедливо для 73% всех целых чисел d . Формула

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

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

Формула

$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 ≤ 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}}}}-{\frac {2(\ln 2)^{2}}{135d}}\right\rceil$

справедливо для всех d ≤ 10 ¹⁸ , и предполагается, что эта формула справедлива для всех d .

День рождения у более двух человек

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

Первые несколько значений таковы: >50% вероятность того, что у 3 человек один день рождения - 88 человек; >50% вероятность того, что у четырех человек один день рождения — 187 человек (последовательность A014088 в OEIS ).

Вероятность общего дня рождения (столкновение)

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

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

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

${\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. ^Н , а скорее только 2 ^{N ⁄ 2} . Это используется атаками «дня рождения» на криптографические хэш-функции и является причиной того, что небольшое количество коллизий в хеш-таблице для всех практических целей неизбежно.

Теорию проблемы дня рождения использовала Зои Шнабель. под названием « статистика повторного вылова» для оценки численности рыбной популяции в озерах.

Обобщение на несколько типов людей

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

Основная проблема заключается в том, что все испытания относятся к одному «типу». Проблема дня рождения была обобщена для рассмотрения произвольного числа типов. В простейшем случае есть два типа людей, скажем, 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 ₂ — числа Стирлинга второго рода . Следовательно, желаемая вероятность равна 1 − p ₀ .

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

Другие проблемы с днем ​​рождения

Первый матч

Связанный с этим вопрос: когда люди входят в комнату по одному, у кого из них, скорее всего, будет тот же день рождения, что и у кого-то, кто уже находится в комнате? То есть, для какого n является p ( n ) − p ( n − 1) максимальным? Ответ: 20. Если за первое совпадение есть приз, то лучшая позиция в очереди — 20-я.

Тот же день рождения, что и у тебя

Сравнение p ( n ) = вероятности совпадения дня рождения с q ( n ) = вероятность совпадения вашего дня рождения

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

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

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

$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 человек вероятность того, что день его рождения совпадает с кем-то еще, равна $q(n-1;d)$, как объяснено выше. Ожидаемое количество людей с общим (неуникальным) днем ​​рождения теперь можно легко вычислить, умножив эту вероятность на количество людей ( n ), то есть:

$n\left(1-\left({\frac {d-1}{d}}\right)^{n-1}\right)$

(Это умножение можно выполнить таким образом из-за линейности ожидаемого значения индикаторных переменных). Это означает, что ожидаемое количество людей с необщим (уникальным) днем ​​рождения составляет:

$n\left({\frac {d-1}{d}}\right)^{n-1}$

Аналогичные формулы можно вывести для ожидаемого числа людей, которые делятся с тремя, четырьмя и т. д. другими людьми.

Количество человек до достижения каждого дня рождения

Ожидаемое количество людей, необходимое для достижения каждого дня рождения, называется задачей коллекционера купонов . Его можно рассчитать по формуле nH _n , где H _n — n- й номер гармоники . Для 365 возможных дат (задача о днях рождения) ответ — 2365.

Рядом матчи

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

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

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

к	н для d = 365
0	23
1	14
2	11
3	9
4	8
5	8
6	7
7	7

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

Количество дней с определенным количеством дней рождения

Количество дней, в течение которых есть хотя бы один день рождения

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

$d-d\left({\frac {d-1}{d}}\right)^{n}$

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

$d\left({\frac {d-1}{d}}\right)^{n}$

что следует из вероятности того, что в данный день ни у кого нет дня рождения ( ⁠ d − 1 / d ⁠ ) ^н
 , легко суммируется из-за линейности ожидаемого значения.

Например, при d = 365 вы должны ожидать около 21 разных дней рождения, если в группе 22 человека, или 46 разных дней рождения, если в группе 50 человек. При 1000 человек будет около 341 разных дней рождения (24 невостребованных дня рождения).

Количество дней с минимум двумя днями рождения

Вышеизложенное можно обобщить на основе распределения числа людей с днем ​​рождения в любой конкретный день, которое представляет собой биномиальное распределение с вероятностью. ⁠ 1 / д ⁠ . Умножение соответствующей вероятности на d даст ожидаемое количество дней. Например, ожидаемое количество дней, которые будут разделены; т.е. у которых хотя бы два (т.е. не ноль и не один) день рождения человека:

$$d-d\left({\frac {d-1}{d}}\right)^{n}-d\cdot {\binom {n}{1}}\left({\frac {1}{d}}\right)^{1}\left({\frac {d-1}{d}}\right)^{n-1}=d-d\left({\frac {d-1}{d}}\right)^{n}-n\left({\frac {d-1}{d}}\right)^{n-1}$$

Количество людей, у которых день рождения повторяется

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

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

Можно увидеть, что это равно количеству людей минус ожидаемое количество разных дней рождения.

Среднее количество людей, у которых будет хотя бы один общий день рождения

В альтернативной формулировке задачи о дне рождения задается вопрос о среднем количестве людей, необходимых для поиска пары с одинаковым днем ​​рождения. Если мы рассмотрим функцию вероятности Pr[ n людей имеют хотя бы один общий день рождения], это среднее значение определяет среднее значение распределения, в отличие от обычной формулировки, которая требует медианы . Проблема актуальна для нескольких алгоритмов хеширования, проанализированных Дональдом Кнутом в его книге «Искусство компьютерного программирования» . Это может быть показано что если производить выборку равномерно, с замещением, из популяции размером 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 ) ≈ 24,61659 , что несколько больше 23, числа, необходимого для 50% вероятности. В лучшем случае хватит двух человек; максимально возможное количество М +1=366 в худшем случае необходимо человек; но в среднем требуется всего 25 человек

Анализ с использованием индикаторных случайных величин может обеспечить более простой, но приблизительный анализ этой проблемы. Для каждой пары ( 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}}\}\\[10pt]&={\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}}\}={\frac {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}]\\[8pt]&={\binom {k}{2}}{\frac {1}{n}}\\[8pt]&={\frac {k(k-1)}{2n}}\end{alignedat}}$$

Для n = 365 , если k = 28 , ожидаемое количество пар людей с одинаковым днем ​​рождения равно ⁠ 28×27 / 2×365 ⁠ ≈ 1,0356. Следовательно, мы можем ожидать как минимум одну совпадающую пару, состоящую как минимум из 28 человек.

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

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

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

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

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

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

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

п	н	n ↓	п ( п ↓)	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

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

Проблема с разделом

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

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

Причина в том, что правильное сравнение заключается в количестве делений весов на левые и правые. Есть 2 ^{Н - 1} разные разделы для N весов, а левую сумму минус правую сумму можно рассматривать как новую случайную величину для каждого раздела. Распределение суммы весов приблизительно гауссово , с пиком при 500 000 Н и шириной 1 000 000 √ Н , так что при 2 ^{Н - 1} приблизительно равен 1 000 000 √ N, происходит переход. 2 ^{23 − 1} составляет около 4 миллионов, тогда как ширина распределения всего 5 миллионов.

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

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

Библиография

• Абрамсон, М.; Мозер, WOJ (1970). «Еще сюрпризы на день рождения». Американский математический ежемесячник . 77 (8): 856–858. дои : 10.2307/2317022 . JSTOR   2317022 .
• Блум, Д. (1973). «Проблема дня рождения». Американский математический ежемесячник . 80 (10): 1141–1142. дои : 10.2307/2318556 . JSTOR   2318556 .
• Кемени, Джон Г.; Снелл, Дж. Лори; Томпсон, Джеральд (1957). Введение в конечную математику (первое изд.).
• МакКинни, Э.Х. (1966). «Обобщенная проблема дня рождения». Американский математический ежемесячник . 73 (5): 385–387. дои : 10.2307/2315408 . JSTOR   2315408 .
• Мостеллер, Ф. (1962). «Понимание проблемы дня рождения». Учитель математики . 55 (5): 322–325. JSTOR   27956609 . Перепечатано в Избранные статьи Фредерика Мостеллера . Серия Спрингера по статистике. 2006. стр. 349–353. дои : 10.1007/978-0-387-44956-2_21 . ISBN  978-0-387-20271-6 .
• Шнепс, Лейла ; Кольмез, Корали (2013). «Математическая ошибка номер 5. Случай Дианы Сильвестр: анализ холодного удара». Математика на суде. Как числа используются и злоупотребляются в зале суда . Основные книги. ISBN  978-0-465-03292-1 .
• Сай М. Блиндер (2013). Руководство по основам математики: обзор для студентов-физиков, химиков и инженеров . Эльзевир. стр. 5–6. ISBN  978-0-12-407163-6 .

Внешние ссылки

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