Введение
Вероятность совпадения дней рождения
В теории вероятностей задача о днях рождения ставит вопрос о вероятности того, что в группе из n случайно выбранных людей хотя бы у двоих совпадет день рождения. Парадокс дней рождения относится к контринтуитивному факту, что для превышения этой вероятности над 50% достаточно всего 23 человек. Парадокс дней рождения – это верификационный парадокс: он кажется неверным на первый взгляд, но на самом деле является истинным. Хотя может показаться удивительным, что для достижения 50% вероятности совпадения дней рождения требуется всего 23 человека, этот результат становится более понятным, если учесть, что сравнение дней рождения будет проводиться между каждой возможной парой людей. С 23 людьми необходимо рассмотреть = 253 пар, что значительно больше половины числа дней в году. Практическое применение задачи о днях рождения включает криптографическую атаку, известную как атака «дня рождения», которая использует эту вероятностную модель для снижения сложности поиска коллизии для хеш-функции, а также для расчета приблизительного риска существования коллизии хешей в заданном наборе данных. Задача обычно приписывается Гарольду Давенпорту около 1927 года, хотя он не опубликовал ее в то время. Давенпорт не заявлял о себе как об открывателе, «потому что не мог поверить, что это не было сформулировано ранее». Первой публикацией версии задачи о днях рождения стала работа Ричарда фон Мизеса в 1939 году.
Обобщение для нескольких типов людей
Основная проблема рассматривает все испытания как относящиеся к одному "типу". Задача о днях рождения была обобщена для рассмотрения произвольного числа типов. В простейшем расширении рассматриваются два типа людей, например, m мужчин и n женщин, и задача сводится к определению вероятности совпадения дня рождения хотя бы у одного мужчины и одной женщины. (Совпадения дней рождения между двумя мужчинами или двумя женщинами не учитываются.) Вероятность отсутствия совпадений дней рождения здесь равна
где и S2 – числа Стерлинга второго рода. Следовательно, искомая вероятность равна 1 − p0. Эта вариация задачи о днях рождения интересна тем, что не существует единственного решения для общего числа людей m + n. Например, обычное значение вероятности 50% достигается как для группы из 32 человек, состоящей из 16 мужчин и 16 женщин, так и для группы из 49 человек, состоящей из 43 женщин и 6 мужчин.
Первый матч
С этим связан вопрос: если люди входят в комнату по одному, кто из них с наибольшей вероятностью окажется первым, у кого день рождения совпадает с днем рождения кого-то, кто уже находится в комнате? То есть, при каком значении n разность p(n) − p(n − 1) достигает максимума? Ответ — 20: если за первое совпадение полагается приз, то лучшая позиция в очереди — двадцатая.
Количество людей, у которых день рождения один
Для любого человека в группе из n человек вероятность того, что у него совпадает день рождения с кем-то еще, равна тому, что описано выше. Ожидаемое количество людей, у которых день рождения совпадает (не уникален), теперь можно легко вычислить, умножив эту вероятность на количество людей (n), то есть:
(Это умножение возможно благодаря линейности математического ожидания индикаторных переменных). Следовательно, ожидаемое количество людей, у которых день рождения не совпадает (уникален), равно:
Аналогичные формулы можно вывести для ожидаемого числа людей, у которых день рождения совпадает с тремя, четырьмя и т.д. другими людьми.
Количество людей до достижения каждого дня рождения
Ожидаемое количество людей, необходимое для того, чтобы все дни рождения были представлены, называется задачей о коллекционере купонов. Оно вычисляется как nHn, где Hn – n-е гармоническое число. Для 365 возможных дат (парадокс дней рождения) ответ равен 2365.
Проблема разделения
Связанная проблема — это проблема разделения, вариант задачи о рюкзаке из области исследования операций. На чашечные весы помещаются некоторые веса; каждый вес — это целое число граммов, случайно выбранное между одним граммом и одним миллионом граммов (одной тонной). Вопрос в том, можно ли обычно (то есть с вероятностью, близкой к 1) перекладывать веса между левой и правой чашами, чтобы уравновесить весы. (Если сумма всех весов — нечетное число граммов, допускается отклонение в один грамм.) Если есть только два или три веса, ответ однозначно отрицательный; хотя некоторые комбинации работают, большинство случайно выбранных комбинаций из трех весов не дают результата. Если весов очень много, ответ однозначно положительный. Вопрос в том, сколько весов достаточно для этого? То есть, какое количество весов делает равновероятными возможность их уравновесить и невозможность этого? Часто интуиция подсказывает, что ответ превышает 100 000. Большинство людей полагают, что он измеряется тысячами или десятками тысяч, в то время как другие считают, что он должен быть хотя бы сотнями. Правильный ответ — 23. Причина в том, что правильным является сравнение с количеством разбиений весов на левую и правую части. Для N весов существует 2^(N–1) различных разбиений, а разность между суммой весов на левой чаше и суммой весов на правой чаше можно рассматривать как новую случайную величину для каждого разбиения. Распределение суммы весов приблизительно гауссово, с пиком в 0 и шириной , так что переход происходит, когда 2^(N–1) приблизительно равно . 2^23 – 1 составляет около 4 миллионов, в то время как ширина распределения — всего 5 миллионов.
В художественной литературе
В романе Артура Кларка "Падение лунной пыли" 1961 года есть эпизод, где главные герои, оказавшиеся запертыми под землей на неопределённый срок, отмечают день рождения и начинают обсуждать справедливость задачи о днях рождения. Как заметил один из пассажиров, физик: "Если в группе больше двадцати четырех человек, вероятность того, что у двух из них совпадает день рождения, превышает 50%". В итоге, среди 22 присутствующих выясняется, что у двух персонажей один и тот же день рождения – 23 мая.