15-10-2023
Парадо́кс дней рожде́ния — утверждение, гласящее, что если дана группа из 23 или более человек, то вероятность того, что хотя бы у двух из них дни рождения (число и месяц) совпадут, превышает 50 %. С практической точки зрения это означает, что если, например, в вашем классе более 22 учеников, то более вероятно, что у кого-то из одноклассников дни рождения придутся на один день, чем что у каждого будет свой собственный день рождения.
Для 60 и более человек вероятность такого совпадения превышает 99 %, хотя 100 % она достигает, согласно принципу Дирихле, только когда в группе не менее 367 человек (с учётом високосных лет).
Такое утверждение может показаться неочевидным, так как вероятность совпадения дней рождения двух человек в любой день года (1/365 = 0,27 %), помноженная на число человек в группе из 23, даёт лишь 23/365 = 6,3 %. Это рассуждение неверно, так как число возможных пар (253) значительно превышает число человек в группе. Таким образом, утверждение не является парадоксом в строгом научном смысле — логического противоречия в нём нет, а парадокс заключается лишь в различиях между интуитивным восприятием ситуации человеком и результатами математического расчёта.
Содержание |
Один из способов понять на интуитивном уровне, почему в группе из 23 человек вероятность совпадения дней рождения у двух человек столь высока, состоит в осознании следующего факта: поскольку рассматривается вероятность совпадения дней рождения у любых двух человек в группе, то эта вероятность определяется количеством пар людей, которые можно составить из 23 человек. Так как порядок людей в парах не имеет значения, то общее число таких пар равно числу сочетаний из 23 по 2, то есть (23 × 22)/2 = 253 пары. Посмотрев на это число, легко понять, что при рассмотрении 253 пар людей вероятность совпадения дней рождения хотя бы у одной пары будет достаточно высокой.
Ключевым моментом здесь является то, что утверждение парадокса дней рождения говорит именно о совпадении дней рождения у каких-либо двух членов группы. Одно из распространённых заблуждений состоит в том, что этот случай путают с другим — похожим, на первый взгляд, — случаем, когда из группы выбирается один человек и оценивается вероятность того, что у кого-либо из других членов группы день рождения совпадёт с днем рождения выбранного человека. В последнем случае вероятность совпадения значительно ниже.
В данном примере для расчёта вероятности того, что в группе из n человек как минимум у двух дни рождения совпадут, примем, что дни рождения распределены равномерно, то есть нет високосных лет, близнецов, рождаемость не зависит от дня недели, времени года и других факторов. В действительности это не совсем так — обычно летом рождается больше детей; кроме того, в некоторых странах из-за особенностей работы больниц больше детей рождается в определённые дни недели. Однако неравномерность распределения может лишь увеличить вероятность совпадения дней рождения, но не уменьшить: если бы все люди рождались только в 3 дня из 365, то вероятность совпадения дней рождения была бы очень высокой.
Рассчитаем сначала, какова вероятность того, что в группе из человек дни рождения всех людей будут различными. Если , то в силу принципа Дирихле вероятность равна нулю. Если же , то будем рассуждать следующим образом. Возьмём наугад одного человека из группы и запомним его день рождения. Затем возьмём наугад второго человека, при этом вероятность того, что у него день рождения не совпадёт с днем рождения первого человека, равна . Затем возьмём третьего человека — при этом вероятность того, что его день рождения не совпадёт с днями рождения первых двух, равна . Рассуждая по аналогии, мы дойдём до последнего человека, для которого вероятность несовпадения его дня рождения со всеми предыдущими будет равна . Перемножая все эти вероятности, получаем вероятность того, что все дни рождения в группе будут различными:
Тогда вероятность того, что хотя бы у двух человек из n дни рождения совпадут, равна
Значение этой функции превосходит 1/2 при (при этом вероятность совпадения равна примерно 50,7 %). Вероятности для некоторых значений иллюстрируются следующей таблицей:
10 | 12 % |
20 | 41 % |
30 | 70 % |
50 | 97 % |
100 | 99,99996 % |
200 | 99,9999999999999999999999999998 % |
300 | (1 − 7×10−73) × 100 % |
350 | (1 − 3×10−131) × 100 % |
367 | 100 % |
Данную задачу можно переформулировать в терминах классической «задачи о совпадениях». Пусть урна содержит (в данном случае 365) шаров, занумерованных числами . Производится выборка с возвращением объёма (в данном случае количество человек в группе), при этом рассматриваемые выборки считаются упорядоченными (то есть выборки и считаются различными). Требуется посчитать вероятность события, заключающегося в отсутствии повторений в выборке (все расчёты аналогичны приведённым выше).
Вероятность совпадения дней рождения в группе можно также рассчитать с использованием формул комбинаторики. Представим, что каждый день года — это одна буква в алфавите из 365 букв. Дни рождения n человек могут быть представлены строкой, состоящей из n букв такого алфавита. Общее число таких строк равно
Общее число строк, в которых буквы не повторяются, составит
Тогда если строки выбираются случайно (с равномерным распределением), то вероятность выбрать строку, в которой хотя бы две буквы совпадут, равна
для и для .
Поскольку
то это выражение эквивалентно представленному выше.
Используя разложение экспоненциальной функции в ряд Тейлора
приведённое выше выражение, дающее значение , можно аппроксимировать следующим образом:
Следовательно,
Для ещё более грубой аппроксимации можно взять выражение
которое, как показывает график, всё ещё даёт достаточную точность.
Приведём ещё одну аппроксимацию.
Вероятность того, что у двух людей день рождения не совпадает, равна 364/365. В группе из человек пар. Поэтому вероятность при условии независимости этих событий может быть приближена числом
Следовательно, получаем приближение для искомой вероятности p (n)
Используя приближение Пуассона для бинома, исходя из предыдущего приближения для , получим чуть больше 50 %:
Используя предыдущую формулу для подсчёта p (n), мы можем выразить n, считая p (n) равной 50 %,получим
Есть ещё один способ оценки n для 50 % вероятности. Как доказывалось выше
Найдём наименьшее n,для которого p(n) > 1/2; или, что то же самое,p(n) < 1/2.
Используя разложение экспоненты в ряд Тейлора, получим 1 − x < e−x. И следовательно,
Так как p(n) < 1/2,
Решая относительно n,получаем
Отсюда находим n равно 23.
Интересно сравнить вероятность p (n) с вероятностью того, что в группе из n человек у кого-либо день рождения совпадет с днём рождения некоторого заранее выбранного человека (не принадлежащего к этой группе). Эта вероятность равна
Подставляя n = 23, получаем q (n) примерно 5,9 %, что лишь немногим лучше одного шанса из 17. Для того, чтобы вероятность совпадения дня рождения с заданным человеком превысила 50 %, число людей в группе должно быть не менее 253. Это число заметно больше, чем половина дней в году (365/2 = 182.5); так происходит из-за того, что у остальных членов группы дни рождения могут совпадать между собой, и это уменьшает вероятность совпадения одного из них с днём рождения заданного человека.
Задача, представленная парадоксом дней рождения, может быть поставлена в общем виде следующим образом: если даны n равномерно распределённых случайных чисел в диапазоне от 1 до d, то какова вероятность p (n ; d) того, что хотя бы два из этих чисел совпадут?
Рассуждая таким же образом, как описано выше, можно получить общие решения:
И наоборот, если n(p;d) обозначает количество чисел, принимающих значения от 1 до d,для которого вероятность того, что хотя бы 2 из них совпадают равно p,то
Выше парадокс дней рождения был представлен для одного «типа» людей. Можно обобщить задачу, введя несколько «типов», например, разделив людей на мужчин (m) и женщин (n). Подсчитаем вероятность того, что хотя бы у одной женщины и у одного мужчины совпадают дни рождения (совпадение дней рождения у двух женщин или у двух мужчин не учитываются):
где d = 365 и S2() — числа Стирлинга второго рода. Интересно, что нет однозначного ответа на вопрос о величине n+m для заданной вероятности. Например, вероятность 0,5 даёт как набор из 16 мужчин и 16 женщин, так и набор из 43 мужчин и 6 женщин.
Другое обобщение парадокса дней рождения состоит в постановке задачи о том, сколько человек нужно для того, чтобы вероятность наличия в группе людей, дни рождения которых различаются не более чем на один день (или на два, три дня и так далее), превысила 50 %. Эта задача более сложная, при её решении используется принцип включения-исключения. Результат (опять-таки в предположении, что дни рождения распределены равномерно) получается следующим:
Максимальное различие дней рождения, дней | Необходимое число людей |
---|---|
1 | 23 |
2 | 14 |
3 | 11 |
4 | 9 |
5 | 8 |
6 | 8 |
7 | 7 |
8 | 7 |
Таким образом, вероятность того, что даже в группе из 7 людей дни рождения хотя бы у двух будут различаться не более чем на неделю, превышает 50 %.
Парадокс дней рождения в общем смысле применим к хеш-функциям: если хеш-функция генерирует N-битное значение, то число случайных входных данных, для которых хеш-коды с большой вероятностью дадут коллизию (то есть найдутся равные хеш-коды, полученные на разных входных данных), равно не 2N, а только около 2N/2. Это наблюдение используется в атаке «дней рождения» на криптографические хеш-функции.
N | количество различных выходных цепочек (2^N) |
Вероятность хотя бы одной коллизии (p) | |||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
10−18 | 10−15 | 10−12 | 10−9 | 10−6 | 0,1 % | 1 % | 25 % | 50 % | 75 % | ||
32 | 4,3 × 109 | 2 | 2 | 2 | 2.9 | 93 | 2.9 × 10³ | 9.3 × 10³ | 5.0 × 104 | 7.7 × 104 | 1.1 × 105 |
64 | 1,8 × 1019 | 6.1 | 1.9 × 10² | 6.1 × 10³ | 1.9 × 105 | 6.1 × 106 | 1.9 × 108 | 6.1 × 108 | 3.3 × 109 | 5.1 × 109 | 7.2 × 109 |
128 | 3,4 × 1038 | 2.6 × 1010 | 8.2 × 1011 | 2.6 × 1013 | 8.2 × 1014 | 2.6 × 1016 | 8.3 × 1017 | 2.6 × 1018 | 1.4 × 1019 | 2.2 × 1019 | 3.1 × 1019 |
256 | 1,2 × 1077 | 4.8 × 1029 | 1.5 × 1031 | 4.8 × 1032 | 1.5 × 1034 | 4.8 × 1035 | 1.5 × 1037 | 4.8 × 1037 | 2.6 × 1038 | 4.0 × 1038 | 5.7 × 1038 |
384 | 3,9 × 10115 | 8.9 × 1048 | 2.8 × 1050 | 8.9 × 1051 | 2.8 × 1053 | 8.9 × 1054 | 2.8 × 1056 | 8.9 × 1056 | 4.8 × 1057 | 7.4 × 1057 | 1.0 × 1058 |
512 | 1,3 × 10154 | 1.6 × 1068 | 5.2 × 1069 | 1.6 × 1071 | 5.2 × 1072 | 1.6 × 1074 | 5.2 × 1075 | 1.6 × 1076 | 8.8 × 1076 | 1.4 × 1077 | 1.9 × 1077 |
В белых квадратах написано количество входных данных(количество человек в группе), при котором коллизия будет с заданной вероятностью(проводя аналогию с парадоксом, кол-во различных выходных цепочек равно 365).
Сходный математический аппарат используется для оценки популяции рыб в озёрах методом «capture-recapture». Действительно, если каждую пойманную рыбу помечать и отпускать, то вероятность поймать помеченную рыбу будет расти нелинейно (в соответствии с приведённым выше графиком) с ростом количества попыток. Размер популяции грубо может быть оценен как квадрат числа попыток до первой помеченной пойманной рыбы.
Решение задачи в общем виде находит применение во многих разделах математики, например в недетерминированных алгоритмах факторизации. Так, одно из самых простых объяснений ρ-метода Полларда аналогично объяснению парадокса дней рождения: достаточно иметь примерно случайных чисел от 0 до , где — простые, чтобы хотя бы для одной из пар чисел с высокой вероятностью нашёлся , который и будет делителем числа n.
1) Поиск наименьшего n,для которого вероятность p(n) больше заданного p.
2) Поиск наибольшего n,для которого вероятность p(n) меньше заданного p.
Пользуясь выше приведённой формулой, получаем
p | n | n↓ | p(n↓) | n↑ | p(n↑) |
0.01 | 0.14178√365 = 2.70864 | 2 | 0.00274 | 3 | 0.00820 |
0.05 | 0.32029√365 = 6.11916 | 6 | 0.04046 | 7 | 0.05624 |
0.1 | 0.45904√365 = 8.77002 | 8 | 0.07434 | 9 | 0.09462 |
0.2 | 0.66805√365 = 12.76302 | 12 | 0.16702 | 13 | 0.19441 |
0.3 | 0.84460√365 = 16.13607 | 16 | 0.28360 | 17 | 0.31501 |
0.5 | 1.17741√365 = 22.49439 | 22 | 0.47570 | 23 | 0.50730 |
0.7 | 1.55176√365 = 29.64625 | 29 | 0.68097 | 30 | 0.70632 |
0.8 | 1.79412√365 = 34.27666 | 34 | 0.79532 | 35 | 0.81438 |
0.9 | 2.14597√365 = 40.99862 | 40 | 0.89123 | 41 | 0.90315 |
0.95 | 2.44775√365 = 46.76414 | 46 | 0.94825 | 47 | 0.95477 |
0.99 | 3.03485√365 = 57.98081 | 57 | 0.99012 | 58 | 0.99166 |
Пусть в комнате находятся n-1 человек, и дни рождения всех присутствующих в комнате различны. Назовём g(n) вероятность того, что день рождения вошедшего человека совпадает с кем-нибудь из присутствующих в комнате. Требуется найти n, для которого g(n) максимально. Задача сводится к нахождению максимального значения p(n)-p(n-1). Пользуясь выше приведённой формулой для p(n), получаем n=20.
Вернёмся к альтернативной проблеме. Сколько в среднем нужно людей для того, чтобы хотя бы у двух из них совпали дни рождения?
Эта проблема имела отношение к алгоритмам хеширования и была исследована Дональдом Кнутом. Оказывается, что для задачи в общем виде интересующая нас случайная величина имеет математическое ожидание равное
, где
Функция
была исследована Сриниваса Рамануджаном Айенгором, который получил для неё асимптотическое разложение:
при M = 365 имеем среднее число людей равное , немного больше чем число людей, обеспечивающих 50 % вероятность. Как ни удивительно, необходимое число людей равно M + 1 = 366 (у 365 людей дни могут распределиться по каждому из 365 дней года без совпадений), хотя в среднем нужно лишь 25.
Парадокс дней рождений.