В теории вероятностей , то проблема рождения или день рождения парадокс касается вероятности , что в совокупности п случайно выбранных людей, некоторые пары из них будет иметь тот же день рождения . В группе из 23 человек вероятность общего дня рождения превышает 50%, в то время как в группе из 70 человек вероятность общего дня рождения составляет 99,9%. (По принципу ячейки , вероятность достигает 100%, когда число людей достигает 367, поскольку существует только 366 возможных дней рождения, включая 29 февраля .)
Эти выводы основаны на предположении, что каждый день в году равновероятен для дня рождения. Фактические записи о рождении показывают, что в разные дни рождается разное количество людей. В этом случае можно показать, что количество людей, необходимое для достижения порога 50%, составляет 23 человека или меньше . [1]
Проблема дня рождения - это реальный парадокс : утверждение, которое сначала кажется нелогичным, но на самом деле верным. Хотя может показаться удивительным, что для достижения 50% вероятности общего дня рождения требуется всего 23 человека, этот результат становится более интуитивным, если учесть, что сравнение дней рождения будет проводиться между всеми возможными парами людей. При 23 особях необходимо рассмотреть (23 × 22) / 2 = 253 пары, что намного больше половины числа дней в году (182,5 или 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 ′) равно произведению этих индивидуальных вероятностей:
( 1 )
Члены уравнения ( 1 ) можно собрать, чтобы получить:
( 2 )
Оценка уравнения ( 2 ) дает P ( A ′) ≈ 0,492703
Следовательно, P ( A ) ≈ 1 - 0,492703 = 0,507297 (50,7297%).
Этот процесс можно обобщить на группу из n человек, где p ( n ) - это вероятность того, что по крайней мере двое из n человек будут праздновать день рождения. Проще сначала вычислить вероятность p ( n ) того, что все n дней рождения различны . Согласно принципу ячейки , p ( n ) равно нулю, когда n > 365 . Когда n ≤ 365 :
где ! - факториальный оператор, (365
п) -биномиальный коэффициент,а k P r -перестановка.
Уравнение выражает тот факт, что у первого человека некому разделить день рождения, у второго человека не может быть того же дня рождения, что и у первого (364/365), у третьего не может быть того же дня рождения, что и у первых двух ( 363/365), и, как правило, n- й день рождения не может совпадать с любым из n - 1 предшествующих дней рождения.
Событие , по меньшей мере , двух из п лиц , имеющих один и тот же день рождения дополняют друг друга , чтобы все п рождения отличаться от других. Следовательно, его вероятность p ( n ) равна
В следующей таблице показана вероятность для некоторых других значений n (для этой таблицы наличие високосных лет игнорируется, и предполагается, что каждый день рождения является одинаково вероятным):
п п ( п ) 1 0,0% 5 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%
Високосные годы . Если мы заменим 366 на 365 в формуле дляаналогичный расчет показывает, что для високосных лет количество людей, необходимое для вероятности совпадения более 50%, также равно 23; вероятность совпадения в этом случае составляет 50,6%.
Приближения
Ряд Тейлора разложение показательной функции (константа е ≈2,718 281 828 )
обеспечивает приближение первого порядка для e x для:
Чтобы применить это приближение к первому выражению, полученному для p ( n ) , установите x = - а/365. Таким образом,
Затем замените a неотрицательными целыми числами для каждого члена в формуле p ( n ) до тех пор, пока a = n - 1 , например, когда a = 1 ,
Первое выражение, полученное для p ( n ), можно аппроксимировать как
Следовательно,
Еще более грубое приближение дается формулой
что, как показано на графике, все еще довольно точное.
Согласно приближению, тот же подход можно применить к любому количеству «людей» и «дней». Если вместо 365 дней есть d , если есть n человек и если n ≪ d , то, используя тот же подход, что и выше, мы достигаем результата, что если p ( n , d ) - это вероятность того, что по крайней мере двое из n люди разделяют один и тот же день рождения из набора из d доступных дней, тогда:
Простое возведение в степень
Вероятность того, что у любых двух человек не будет одного дня рождения, равна 364/365. В комнате, содержащей n человек, находятся (п
2) = п ( п - 1)/2пары людей, т. е. (п
2) события. Вероятность того, что у двух людей не будет одного дня рождения, можно приблизительно оценить, предположив, что эти события независимы, и, следовательно, умножив их вероятность вместе. Коротко 364/365можно умножить на себя (п
2) раз, что дает нам
Поскольку это вероятность того, что ни у кого нет одного дня рождения, то вероятность того, что кто-то разделит день рождения, равна
Пуассоновское приближение
Применяя приближение Пуассона для бинома к группе из 23 человек,
так
Результат более 50%, как и в предыдущих описаниях. Это приближение такое же, как и приведенное выше, основанное на разложении Тейлора, которое использует.
Квадратное приближение
Хорошее практическое правило, которое можно использовать для мысленных вычислений, - это соотношение
который также можно записать как
который хорошо работает для вероятностей, меньших или равных 1/2. В этих уравнениях m - количество дней в году.
Например, чтобы оценить количество людей, необходимое для 1/2 шанс на совместный день рождения, мы получаем
Что не так уж далеко от правильного ответа 23.
Примерное количество человек
Это также можно приблизительно определить, используя следующую формулу для определения количества людей, необходимых для того, чтобы иметь как минимум 1/2 шанс совпадения:
Это результат хорошего приближения того, что событие с 1/k вероятность будет иметь 1/2вероятность появления хотя бы один раз, если это повторяется k ln 2 раза. [6]
Таблица вероятностей
длина
шестнадцатеричной строкинет. из
битов
( б )
размер хэш-пространства
( 2 б )Количество хешированных элементов таких, что вероятность хотя бы одного хеш-коллизии ≥ p p =10 −18 p =10 −15 p =10 −12 p =10 −9 p =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
Более светлые поля в этой таблице показывают количество хешей, необходимых для достижения заданной вероятности коллизии (столбец) с учетом хеш-пространства определенного размера в битах (строка). Используя аналогию с днем рождения: «размер хеш-пространства» похож на «доступные дни», «вероятность столкновения» похожа на «вероятность общего дня рождения», а «необходимое количество хешированных элементов» похоже на «требуемое количество людей в группа". Можно также использовать эту диаграмму для определения минимального требуемого размера хэша (с учетом верхних границ хешей и вероятности ошибки) или вероятности коллизии (для фиксированного количества хешей и вероятности ошибки).
Для сравнения, От 10 −18 до10 -15 - это уровень неисправимых битовых ошибок типичного жесткого диска. [7] Теоретически 128-битные хеш-функции, такие как MD5 , должны оставаться в этом диапазоне примерно до8,2 × 10 11 документов, даже если его возможных выходов намного больше.
Верхняя граница вероятности и нижняя граница количества людей
Приведенный ниже аргумент адаптирован из аргумента Пола Халмоса . [nb 2]
Как указано выше, вероятность того, что два дня рождения не совпадают, равна
Как и в предыдущих параграфах, интерес представляет наименьшее n такое, что p ( n )> 1/2; или, что то же самое, наименьшее n такое, что p ( n ) < 1/2.
Используя неравенство 1 - x < e - x в приведенном выше выражении, мы заменяем 1 - k/365с е- к ⁄ 365 . Это дает
Таким образом, выражение выше, не только приближение, но и верхняя граница по р ( п ) . Неравенство
следует p ( n ) < 1/2. Решение для n дает
Теперь 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 такое, что
Таким образом, классическая задача дня рождения соответствует определению 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 ≥ 1 число n ( d ) удовлетворяет [9]
Эти оценки оптимальны в том смысле, что последовательность n ( d ) - √ 2 d ln 2 сколь угодно близка к
пока у него есть
в качестве максимального, взятого при d = 43 .
Границы достаточно жесткие, чтобы дать точное значение n ( d ) в 99% всех случаев, например n (365) = 23 . В общем случае из этих оценок следует, что n ( d ) всегда равно либо
где ⌈ · ⌉ обозначает функцию потолка . Формула
выполняется для 73% всех целых чисел d . [10] Формула
выполняется почти для всех d , т. е. для набора целых чисел d с асимптотической плотностью 1. [10]
Формула
выполняется для всех d ≤10 18 , но предполагается, что существует бесконечно много контрпримеров к этой формуле. [11]
Формула
выполняется для всех d ≤10 18 , и предполагается, что эта формула верна для всех d . [11]
Более двух человек отмечают день рождения
Можно расширить задачу, задав вопрос, сколько человек необходимо в группе, чтобы с вероятностью более 50% было не менее 3/4/5 и т. Д. группы имеют один день рождения.
Первые несколько значений следующие:> 50% вероятность того, что 3 человека разделяют день рождения - 88 человек; > 50% вероятность того, что 4 человека разделяют день рождения - 187 человек (последовательность A014088 в OEIS ). [12]
Задачу дня рождения можно обобщить следующим образом:
- Для n случайных целых чисел, взятых из дискретного равномерного распределения с диапазоном [1, d ] , какова вероятность p ( n ; d ) того, что по крайней мере два числа совпадают? ( d = 365 дает обычную задачу о дне рождения.) [13]
Общие результаты могут быть получены с использованием тех же аргументов, которые приведены выше.
И наоборот, если n ( p ; d ) обозначает количество случайных целых чисел, взятых из [1, d ], чтобы получить вероятность p того, что по крайней мере два числа совпадают, тогда
Проблема рождения в этом более широком смысле относится к хэш - функциям : ожидаемое число N - битовые хэш , которые могут быть сгенерированы перед тем , как столкновением не 2 N , а только 2N ⁄ 2 . Это используетсяатакамипослучаю дня рождениянакриптографические хеш-функциии является причиной того, что небольшое количество коллизий вхеш-таблицедля всех практических целей неизбежно.
Теория, лежащая в основе проблемы дня рождения, была использована Зои Шнабель [14] под названием статистики вылова-повторной поимки для оценки размера популяции рыб в озерах.
Обобщение на несколько типов людей
В основной задаче все испытания относятся к одному «типу». Проблема дня рождения была обобщена для рассмотрения произвольного числа типов. [15] В простейшем расширении существует два типа людей, скажем, m мужчин и n женщин, и проблема заключается в том, чтобы характеризовать вероятность общего дня рождения хотя бы одного мужчины и одной женщины. (Общие дни рождения двух мужчин или двух женщин не учитываются.) Вероятность отсутствия общих дней рождения здесь равна
где d = 365 и S 2 - числа Стирлинга второго рода . Следовательно, желаемая вероятность равна 1 - p 0 .
Этот вариант задачи о дне рождения интересен тем, что не существует единственного решения для общего числа людей m + n . Например, обычное значение вероятности 50% реализуется как для группы из 32 человек, состоящей из 16 мужчин и 16 женщин, так и для группы из 49 человек, состоящей из 43 женщин и 6 мужчин.
Другие проблемы с днем рождения
Первый матч
Связанный с этим вопрос: когда люди входят в комнату по одному, какой из них, скорее всего, будет первым, у кого будет такой же день рождения, как и у кого-то, кто уже находится в комнате? То есть, для чего n является максимумом p ( n ) - p ( n - 1) ? Ответ - 20 - если есть приз за первый матч, лучшая позиция в очереди - 20-е. [ необходима цитата ]
В тот же день рождения, что и ты
В задаче о дне рождения ни один из двух человек заранее не выбран. Напротив, вероятность q ( n ) того, что кто-то в комнате из n других людей имеет тот же день рождения, что и конкретный человек (например, вы), определяется как
и для общего г по
В стандартном случае d = 365 подстановка n = 23 дает около 6,1%, что меньше 1 шанса из 16. Для шанса более 50%, что у одного человека в комнате, заполненной n людьми, такой же день рождения, как и у вас , n должно быть не менее 253. Это число значительно больше, чем365/2= 182,5 : причина в том, что есть вероятность, что среди других людей в комнате есть совпадения по случаю дня рождения.
Для любого человека в группе из n человек вероятность того, что он или она разделяет свой день рождения с кем-то еще, равна, как объяснено выше. Ожидаемое количество людей с общим (неуникальным) днем рождения теперь можно легко вычислить, умножив эту вероятность на количество людей ( n ), так что это:
(Это умножение может быть выполнено таким образом из-за линейности ожидаемого значения индикаторных переменных). Это означает, что ожидаемое количество людей с нераздельным (уникальным) днем рождения составляет:
Подобные формулы могут быть получены для ожидаемого числа людей, которые делятся с тремя, четырьмя и т. Д. Другими людьми.
Ближайшие матчи
Другое обобщение - спросить о вероятности найти хотя бы одну пару в группе из n человек, дни рождения которых находятся в пределах k календарных дней друг от друга, если существует d равновероятных дней рождения. [16]
Количество людей, необходимое для того, чтобы вероятность того, что у какой-то пары день рождения разделится на k дней или меньше, будет выше 50%, приведено в следующей таблице:
k n
для d = 3650 23 1 14 2 11 3 9 4 8 5 8 6 7 7 7
Таким образом, в группе из семи случайных людей более вероятно, что у двоих из них будет день рождения в пределах недели друг от друга. [16]
Количество дней с определенным количеством дней рождения
Количество дней хотя бы с одним днем рождения
Ожидаемое количество разных дней рождения, т. Е. Количество дней, приходящихся на день рождения хотя бы одного человека, составляет:
Это следует из ожидаемого количества дней, в которые нет ни одного дня рождения:
что следует из вероятности того, что в конкретный день никто не день рождения, , легко суммируется из-за линейности ожидаемого значения.
Например, при d = 365 вы должны ожидать около 21 разных дней рождения, когда есть 22 человека, или 46 разных дней рождения, когда есть 50 человек. Когда будет 1000 человек, будет около 341 разных дней рождения (24 невостребованных дня рождения).
Количество дней минимум с двумя днями рождения
Вышеупомянутое можно обобщить из распределения количества людей, чьи дни рождения отмечены в любой конкретный день, которое является биномиальным распределением с вероятностью 1 / d . Умножение соответствующей вероятности на d даст ожидаемое количество дней. Например, ожидаемое количество общих дней; то есть, по крайней мере, два (т.е. не ноль и не один) день рождения:
Количество людей, которые повторяют день рождения
Вероятность того, что k- е целое число, случайно выбранное из [1, d ] , повторит хотя бы один предыдущий выбор, равна q ( k - 1; d ) выше. Ожидаемое общее количество раз, когда выборка будет повторять предыдущий выбор, если выбрано n таких целых чисел, равное [17]
Можно увидеть, что это равно количеству людей за вычетом ожидаемого количества разных дней рождения.
В альтернативной формулировке задачи о дне рождения спрашивают, сколько в среднем людей требуется, чтобы найти пару с одинаковым днем рождения. Если мы рассмотрим функцию вероятности Pr [ n людей имеют по крайней мере один общий день рождения], это среднее значение определяет среднее значение распределения, в отличие от обычной формулировки, которая требует медианы . Проблема актуальна для нескольких алгоритмов хеширования, проанализированных Дональдом Кнутом в его книге «Искусство компьютерного программирования» . Можно показать [18] [19], что если один выборку однородно, с заменой, из популяции размера M , количество испытаний, необходимое для первого повторного отбора выборки некоторого человека, будет иметь ожидаемое значение n = 1 + Q ( M ) , где
Функция
был изучен Шринивасой Рамануджаном и имеет асимптотическое разложение :
При M = 365 дней в году среднее количество людей, необходимое для поиска пары с одинаковым днем рождения, равно n = 1 + Q ( M ) ≈ 24,61659 , что несколько больше 23, число, необходимое для 50% вероятности. В лучшем случае хватит двух человек; в худшем случае нужно максимально возможное количество M + 1 = 366 человек; но в среднем требуется всего 25 человек
Анализ с использованием индикаторных случайных величин может дать более простой, но приблизительный анализ этой проблемы. [20] Для каждой пары (i, j) для k человек в комнате мы определяем индикаторную случайную величину X ij , для, от
Пусть X - случайная величина, считающая пары людей с одним днем рождения.
Для n = 365 , если k = 28 , ожидаемое количество с таким же днем рождения равно Следовательно, мы можем ожидать хотя бы одну подходящую пару как минимум из 28 человек.
Неформальная демонстрация проблемы может быть сделана из списка премьер-министров Австралии , которых по состоянию на 2017 год было 29.[Обновить], в котором 24-й премьер-министр Пол Китинг и первый премьер-министр Эдмунд Бартон разделяют день рождения 18 января.
На чемпионате мира по футболу 2014 года в каждой из 32 команд было по 23 игрока. Анализ официальных списков команд показал, что в 16 командах были пары игроков, у которых были дни рождения, и из этих 5 команд было две пары: Аргентина, Франция, Иран, Южная Корея и Швейцария имели по две пары, а Австралия, Босния и Герцеговина, Бразилия. , Камерун, Колумбия, Гондурас, Нидерланды, Нигерия, Россия, Испания и США - каждая по одной паре. [21]
Ворачек, Тран и Форманн показали, что большинство людей заметно переоценивают количество людей, необходимое для достижения заданной вероятности того, что люди имеют один и тот же день рождения, и заметно недооценивают вероятность того, что люди имеют один и тот же день рождения, если дан конкретный размер выборки. . [22] Дальнейшие результаты показали, что студенты-психологи и женщины справились с задачей лучше, чем посетители / персонал казино или мужчины, но были менее уверены в своих оценках.
Обратная задача
Обратная задача состоит в том, чтобы найти для фиксированной вероятности p наибольшее n, для которого вероятность p ( n ) меньше заданного p , или наименьшее n, для которого вероятность p ( n ) больше заданного p . [ необходима цитата ]
Принимая приведенную выше формулу для d = 365 , имеем
В следующей таблице приведены некоторые примеры расчетов.
п п п ↓ п ( п ↓) п ↑ п ( п ↑) 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 весов, и левую сумму минус правую сумму можно рассматривать как новую случайную величину для каждого раздела. Распределение суммы весов приблизительно гауссово с максимумом на1 000 000 Н и ширина1 000 000 √ Н , так чтокогда 2 Н - 1 приблизительно равен1 000 000 √ 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 .
Эти факторы, как правило, увеличивают вероятность идентичных дат рождения, поскольку более плотное подмножество имеет больше возможных пар (в крайнем случае, когда все родились в три дня, очевидно, будет много одинаковых дней рождения). Проблема неравномерного количества рождений, происходящих в течение каждого дня в году, была впервые понята Мюрреем Кламкиным в 1967 году. [4] Формальное доказательство того, что вероятность двух совпадающих дней рождения является наименьшей для равномерного распределения дней рождения, было дано Блум ( Bloom 1973 ).
- ↑ В своей автобиографии Халмос раскритиковал форму, в которой часто представляется парадокс дня рождения, с точки зрения числовых вычислений. Он считал, что это следует использовать как пример использования более абстрактных математических понятий. Он написал:
Рассуждения основаны на важных инструментах, к которым все студенты-математики должны иметь свободный доступ. Проблема дня рождения была великолепной иллюстрацией преимуществ чистой мысли перед механическими манипуляциями; неравенства можно получить за минуту или две, в то время как умножение займет гораздо больше времени и будет гораздо более подвержено ошибкам, независимо от того, является ли инструмент карандашом или старомодным настольным компьютером. Что калькуляторы не дают понимание, или математический объект, или прочную основу для более продвинутых, обобщенных теорий.
Рекомендации
- ^ а б в Марио Кортина Борха; Джон Хей (сентябрь 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.
- ^ Frank, P .; Goldstein, S .; Kac, M .; Prager, W .; Szegö, G .; Биркгоф, Г., ред. (1964). Избранные статьи Рихарда фон Мизеса . 2 . Провиденс, Род-Айленд: амер. Математика. Soc. С. 313–334.
- ^ Klamkin & Newman 1967 .
- ^ Стил, Дж. Майкл (2004). Мастер-класс Коши-Шварца . Кембридж: Издательство Кембриджского университета. стр. 206 , 277. ISBN 9780521546775.
- ^ Матис, Фрэнк Х. (июнь 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 .
- ^ Сузуки, К .; 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 года .
- ^ Кнут, Д.Е. (1973). Искусство программирования . Vol. 3, Сортировка и поиск. Ридинг, Массачусетс: Эддисон-Уэсли. ISBN 978-0-201-03803-3.
|volume=
есть дополнительный текст ( справка ) - ^ Flajolet, P .; Грабнер, П.Дж.; 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