Парадокс дней рождения

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Парадо́кс дней рожде́ния. В группе, состоящей из 23 или более человек, вероятность совпадения дней рождения (число и месяц) хотя бы у двух людей превышает 50 %. Например, если в классе 23 ученика или более, то более вероятно то, что у какой-то пары одноклассников дни рождения придутся на один день, чем то, что у каждого будет свой неповторимый день рождения[1]. Впервые эта задача была рассмотрена Рихардом Мизесом в 1939 году[2][3].

Для 57 и более человек вероятность такого совпадения превышает 99 %, хотя 100 % она достигает, согласно принципу Дирихле (здравому смыслу), только тогда, когда в группе не менее 367 человек (ровно на 1 больше, чем число дней в високосном году; с учётом високосных лет).

Такое утверждение может показаться неочевидным, так как вероятность совпадения дней рождения двух человек с любым днём в году (1/365 = 0,27 %), умноженная на число человек в группе (23), даёт лишь (1/365)×23 = 6,3 %. Это рассуждение неверно, так как число возможных пар (( 23 × 22 )/2 = 253) значительно превышает число человек в группе (253 > 23). Таким образом, утверждение не является парадоксом в строгом научном смысле: логического противоречия в нём нет, а парадокс заключается лишь в различиях между интуитивным восприятием ситуации человеком и результатами математического расчёта.

График зависимости вероятности совпадения дней рождения хотя бы у двух человек от количества людей

Интуитивное восприятие[править | править код]

В группе из 23 человек вероятность совпадения дней рождения у двух человек столь высока, потому что рассматривается вероятность совпадения дней рождения у любых двух человек в группе. Эта вероятность определяется количеством пар людей, которые можно составить из 23 человек. Так как порядок людей в парах не имеет значения, общее число таких пар равно числу сочетаний из 23 по 2, то есть ( 23 × 22 )/2 = 253 пары.

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

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

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

Пусть дни рождения распределены равномерно, то есть примем, что:

В действительности это не совсем так. Кроме того, в некоторых странах из-за особенностей работы больниц больше детей рождается в определённые дни недели. Однако неравномерность распределения может лишь увеличить вероятность совпадения дней рождения, но не уменьшить: если бы все люди рождались только в 3 дня из 365, то вероятность совпадения дней рождения была бы очень высокой.

Рассчитаем сначала  — вероятность того, что в группе из человек дни рождения всех людей будут различными. Если , то в силу принципа Дирихле вероятность равна нулю. Если же , то будем рассуждать следующим образом. Возьмём наугад одного человека из группы и запомним его день рождения. Затем возьмём наугад второго человека, при этом вероятность того, что у него день рождения не совпадёт с днем рождения первого человека, равна . Затем возьмём третьего человека; при этом вероятность того, что его день рождения не совпадёт с днями рождения первых двух, равна . Рассуждая по аналогии, мы дойдём до последнего человека, для которого вероятность несовпадения его дня рождения со всеми предыдущими будет равна . Перемножая все эти вероятности, получаем вероятность того, что все дни рождения в группе будут различными:

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

Значение этой функции превосходит 1/2 при , при этом вероятность совпадения равна примерно 50,73 %, а . Список значений n и соответствующих им вероятностей приведён в следующей таблице.

n p(n)
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 дням);
  • шары пронумерованных числами 1, 2, …, ;
  • производится несколько выборок по n шаров из урны (в данном случае n — количество человек в группе);
  • изъятые шары возвращаются в урну после каждой выборки;
  • выборки считаются упорядоченными, то есть выборки и считаются различными.

Требуется посчитать вероятность события, заключающегося в отсутствии повторений в выборке. Все расчёты аналогичны приведённым выше.

Альтернативный метод[править | править код]

Вероятность совпадения дней рождения у двух человек, входящих в группу из n людей, можно также рассчитать с использованием формул комбинаторики[4]. Представим, что каждый день года — это одна буква в алфавите, и алфавит состоит из 365 букв. Дни рождения n человек могут быть представлены строкой, состоящей из n букв такого алфавита. По формуле Хартли, количество возможных строк равно

Количество возможных строк, в которых буквы не повторяются (размещение из 365 по n), составит

Если строки выбираются случайно (с равномерным распределением), вероятность выбора строки, в которой хотя бы две буквы совпадут, равна

при и
при .

Поскольку

а это выражение эквивалентно представленному выше.

Аппроксимации[править | править код]

Экспоненциальная функция[править | править код]

Используя разложение экспоненциальной функции в ряд Тейлора

приведённое выше выражение для можно аппроксимировать следующим образом:

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

Графики функции p(n) и близкой к ней функции аппроксимации

Заметим, что и упрощенная аппроксимация

как видно по графику, всё ещё даёт достаточную точность.

Приведём ещё одну аппроксимацию.

Вероятность того, что у двух людей дни рождения не совпадают, равна 364/365. В группе из человек  пар. Поэтому вероятность при условии независимости этих событий может быть приближена числом

Следовательно, получаем приближение для искомой вероятности p(n):

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

Используя приближение Пуассона для бинома, исходя из предыдущего приближения для , получим чуть больше 50 %:

Расчёт количества человек, при котором вероятность составляет 50 %[править | править код]

Из приведённой ранее формулы для p(n)[какой?] выразим n. Затем вместо p(n) подставим 50 % (0,5). В результате получим:

Существует ещё один способ оценки n при вероятности 50 %. Согласно доказанному выше:

Найдём наименьшее n, при котором

или, что то же самое:

Воспользуемся приведённой выше аппроксимацией функции  экспоненциальной функцией:

Подставив вместо в выражение , получим:

Решая относительно n, получим:

Отсюда найдём n и округлим до целого:

n = 23.

Родившиеся в один день с заданным человеком[править | править код]

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

Сравнение графиков функций p(n) и q(n).
  • Ось абсцисс: количество человек n.
  • Ось ординат: вероятность.
  • p(n) — вероятность того, что в группе из n человек как минимум у двух из них дни рождения совпадут.
  • q(n) — вероятностью того, что в группе из n человек день рождения какого‑либо человека из группы совпадёт с днём рождения некоторого заранее выбранного человека, не принадлежащего группе.
  • Подставляя n = 23, получаем q(n) ≈ 6,12 %. Для того, чтобы вероятность q(n) превысила 50 %, число людей в группе должно быть не менее 253 (q(252) ≈ 49,91 %; q(253) ≈ 50,05 %). Это число больше, чем половина дней в году (365/2 = 182,5); так происходит из-за того, что у остальных членов группы дни рождения могут совпадать между собой, и это уменьшает вероятность q(n).

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

    Совпадение дискретных случайных величин[править | править код]

    Описанная задача может быть сформулирована в общем виде:

    • даны случайные числа;
    • случайные числа распределены равномерно в диапазоне от 1 до d;
    • n — количество случайных чисел;
    • определить p( n ; d ) — вероятность того, что совпадут хотя бы два числа из заданных.

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

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

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

    Решение:

    Несколько типов людей[править | править код]

    Вероятность совпадения дня рождения хотя бы у одного мужчины и у одной женщины

    Выше парадокс дней рождения был представлен для одного «типа» людей. Можно обобщить задачу, введя несколько «типов», например, разделив людей на мужчин (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 Количество различных выходных цепочек (2N) Вероятность хотя бы одной коллизии (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 × 10⁴ 7,7 × 10⁴ 1,1 × 10⁵
    64 1,8 × 1019 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⁹
    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.
    1. Поиск наибольшего числа 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.

    См. также[править | править код]

    Примечания[править | править код]

    1. Мазур, 2017, с. 116.
    2. Мазур, 2017, с. 119.
    3. Миронкин В. О., Чухно А. Б. Об одном обобщении парадокса «дней рождения». Дата обращения 30 марта 2020.
    4. Мазур, 2017, с. 117.

    Литература[править | править код]

    • Кемени Дж., Снелл Дж., Томпсон Дж. Введение в конечную математику = Introduction to Finite Mathematics. — Издательство иностранной литературы, 1963. — 488 с.
    • Козлов М. В. Элементы теории вероятностей в примерах и задачах. — МГУ, 1990 год. — ISBN 5-211-00312-8.
    • Мазур, Джозеф. Задача о дне рождения // Игра случая. Математика и мифология совпадения. — Альпина нон-фикшн, 2017. — С. 116—123. — 292 с. — ISBN 978-5-91671-636-8.
    • Секей Г. Парадоксы в теории вероятностей и математической статистике. — РХД, 2003 год. — ISBN 5-93972-150-8.
    • Ширяев А. Н. Вероятность-1. — МЦНМО, 2007 год. — ISBN 978-5-94057-036-3.
    • Goldberg S. A Direct Attack on a Birthday Problem (англ.) // Mathematical Mathematics Magazine. — Май 1976 года. — Iss. 49. — P. 130—132.
    • Mosteller F. Understanding the Birthday Problem (англ.) // The Mathematics Teacher. — Май 1962 года. — P. 322—325.

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