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

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

Парадо́кс дней рожде́ния (англ. birthday problem) — утверждение, гласящее, что если дана группа из 23 или более человек, то вероятность того, что хотя бы у двух из них дни рождения (число и месяц) совпадут, превышает 50 %. Например, если в классе 23 ученика или более, то более вероятно, что у кого-то из одноклассников дни рождения придутся на один день, чем что у каждого будет свой неповторимый день рождения.

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

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

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

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

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

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


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

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

Рассчитаем сначала \bar p(n) — вероятность того, что в группе из n человек дни рождения всех людей будут различными. Если  n > 365 , то в силу принципа Дирихле вероятность \bar p(n) равна нулю. Если же  n \leqslant365 , то будем рассуждать следующим образом. Возьмём наугад одного человека из группы и запомним его день рождения. Затем возьмём наугад второго человека, при этом вероятность того, что у него день рождения не совпадёт с днем рождения первого человека, равна  1 - \frac{1}{365} . Затем возьмём третьего человека; при этом вероятность того, что его день рождения не совпадёт с днями рождения первых двух, равна  1 - \frac{2}{365} . Рассуждая по аналогии, мы дойдём до последнего человека, для которого вероятность несовпадения его дня рождения со всеми предыдущими будет равна  1 - \frac{ n - 1 }{365} . Перемножая все эти вероятности, получаем вероятность того, что все дни рождения в группе будут различными:

 \bar p(n) =  = 1 \cdot \left( 1 - \frac{1}{365} \right) \cdot \left( 1 - \frac{2}{365} \right) \cdot \ldots \cdot \left( 1 - \frac{ n - 1 }{365} \right) =  = { 365 \cdot 364 \cdot \ldots \cdot (365-n+1) \over 365^n } =  = { 365! \over 365^n (365-n)!}.

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

 p(n) = 1 - \bar p(n) .

Значение этой функции превосходит 1/2 при  n = 23 (при этом вероятность совпадения равна примерно 50.73%, а p(22) \approx 47.57%). Список значений 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%

Данную задачу можно переформулировать в терминах классической «задачи о совпадениях». Пусть урна содержит M (в данном случае 365) шаров, занумерованных числами 1; 2; \ldots; M. Производится несколько выборок по n шаров в каждой; изъятые шары возвращаются в урну после каждой выборки; в данном случае, n — количество человек в группе. Выборки считаются упорядоченными (то есть выборки \{1;2;4;6\} и \{4;2;6;1\} считаются различными). Требуется посчитать вероятность события, заключающегося в отсутствии повторений в выборке. Все расчёты аналогичны приведённым выше.

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

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

 n_\mathrm{ total } = 365^{n} .

Общее число строк, в которых буквы не повторяются, составит

 n_\mathrm{ unique } = \frac{365!}{ (365-n)! } .

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

 p(n) = 1 - \frac{ n_\mathrm{ unique } }{ n_\mathrm{ total } } = 1 - \frac{ \frac{365!}{ (365-n)! } }{ 365^{n} }

для  n \leqslant365 и  p(n) = 1 для  n > 365 .

Поскольку

 \frac{ \left( \frac{365!}{ (365-n)! } \right) }{ 365^{n} } = \frac{ 365 \cdot 364 \cdot 363 \cdots (365-n+1) }{ 365^{n} } =  = \frac{365}{365} \frac{364}{365} \frac{363}{365} \cdots \frac{ 365-n+1 }{365} =  = 1 \cdot \left( 1 - \frac{1}{365} \right) \cdot \left( 1 - \frac{2}{365} \right) \cdots \left( 1-\frac{n-1}{365} \right) ,

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

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

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

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

 e^x = 1 + x + \frac{x^2}{2!} + \ldots ,

приведённое выше выражение для  \bar p(n) , можно аппроксимировать следующим образом:

 \bar p(n) \approx 1 \cdot e^{ -1/365 } \cdot e^{ -2/365 } \cdots e^{ -(n-1)/365 } =  = 1 \cdot e^{ -( 1 + 2 + \cdots + ( n - 1 ) )/365 } =  = e^{ -\frac{ n(n-1) }{ 2 \cdot 365 } } .

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

 p(n) = 1 - \bar p(n) \approx 1 - e^{ -\frac{ n(n-1) }{ 2 \cdot 365 } } .
Графики функции p(n) и близкой к ней экспоненциальной функции

Для ещё более грубой аппроксимации можно взять выражение

 p(n) \approx 1-e^{ -\frac{ n^2 }{ 2 \cdot 365 } },

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

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

Вероятность того, что у двух людей дни рождения не совпадают, равна 364/365. В группе из  n человек  C( n, 2 ) = \frac{ n(n-1) }{2} пар. Поэтому вероятность  \bar p(n) при условии независимости этих событий может быть приближена числом

 \left( \frac{364}{365} \right)^{ C(n,2) } .

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

 p(n) \approx 1 - \left( \frac{364}{365} \right)^{ C(n,2) } .

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

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

 \mathrm{Poi} \left( \frac{ C(23,2) }{365} \right) = \mathrm{Poi} \left( \frac{253}{365} \right) \approx \mathrm{Poi}(0{,}693\,2)
 \mathbb{P}(\{X>0\}) = 1 - \mathbb{P}(\{X=0\}) = 1 - e^{ -0{,}693\,2 } = 1 - 0{,}499\,998 = 0{,}500\,002 .

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

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

 n \approx \frac{1}{2} + \sqrt{ \frac{1}{4} - 2 \cdot 365 \cdot \ln(0.5) } = 22.9999 .

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

 \bar p(n) = 1 - p(n) = \prod_{ k=1 }^{ n-1 } \left( 1 - { \frac{k}{365} } \right) .

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

 p(n) > \frac{1}{2}

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

 \bar p(n) < \frac{1}{2} .

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

 \bar p_{approx}(n) = \prod_{ k=1 }^{ n-1 } \left( e^{ \frac{-k}{365} } \right) = e^{ \frac{ -n(n-1) }{ 2 \cdot 365 } } .

Подставив  \bar p_{approx}(n) вместо  \bar p(n) в выражение  \bar p(n) < \frac{1}{2}, получим:

 e^{ \frac{ -n(n-1) }{ 2 \cdot 365 } } < \frac{1}{2} .

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

 n^2 - n > 2 \cdot 365 \cdot \ln 2 \,\! .

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

n = 23.

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

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

 q(n) = 1 - \left( \frac{ 365-1 }{365} \right)^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(n;d) = \begin{cases} 1 - \prod_{ k=1 }^{ n-1 } \left( 1 - { k \over d } \right) & n \le d \\ 1 & n > d \end{cases} ;
 p(n;d) \approx 1 - e^{ -( n(n-1) )/2d } ;
 q(n;d) = 1 - \left( \frac{ d-1 }{d} \right)^n .

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

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

Решение:

 n(p;d) \approx \sqrt{ 2d \cdot \ln \left( { 1 \over 1 - p } \right) } .

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

Выше парадокс дней рождения был представлен для одного «типа» людей. Можно обобщить задачу, введя несколько «типов», например, разделив людей на мужчин (m) и женщин (n). Подсчитаем вероятность того, что хотя бы у одной женщины и у одного мужчины совпадают дни рождения (совпадение дней рождения у двух женщин или у двух мужчин не учитываются):

 p_0 = 1 - \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 и 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». Действительно, если каждую пойманную рыбу помечать и отпускать, то вероятность поймать помеченную рыбу будет расти нелинейно (в соответствии с приведённым выше графиком) с ростом количества попыток. Размер популяции грубо может быть оценён как квадрат числа попыток, совершаемых до вылавливания первой помеченной рыбы.

Решение задачи в общем виде находит применение во многих разделах математики, например, в недетерминированных алгоритмах факторизации. Так, одно из самых простых объяснений ρ-метода Полларда аналогично объяснению парадокса дней рождения: достаточно иметь примерно \sqrt{p} случайных чисел от 0 до  n = p q ~, где p < q ~ — простые, чтобы хотя бы для одной из пар чисел с высокой вероятностью нашёлся \gcd \left( |x-y|, n \right) > 1 , который и будет делителем числа n.

Обратные задачи[править | править вики-текст]

  1. Поиск наименьшего n, для которого вероятность p(n) больше заданного p.
  1. Поиск наибольшего n, для которого вероятность p(n) меньше заданного p.

Пользуясь выше приведённой формулой, получаем

 n(p;365) \approx \sqrt{ 2 \cdot 365 \cdot \ln \left( { 1 \over 1 - p } \right) } .
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.

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

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

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

 \overline{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}{ 135 M } + \cdots .

При M = 365 среднее число людей равно

 \overline{n} \, = \, 1 + Q(M) \approx 24.61658 .

Это число немного больше, чем число людей, обеспечивающих вероятность 50%. Как ни удивительно, необходимое число людей равно M + 1 = 366 (у 365 людей дни рождения могут распределиться по каждому из 365 дней года без совпадений), хотя в среднем нужно лишь 25.

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

Ссылки[править | править вики-текст]

Литература[править | править вики-текст]

  • John G. Kemeny, J. Laurie Snell, and Gerald Thompson Introduction to Finite Mathematics . The first edition, 1957.(русский перевод: Кемени Дж., Снелл Дж., Томпсон Дж. Введение в конечную математику. Издательство иностранной литературы, 1963 г., 488 стр.)
  • Секей Г. Парадоксы в теории вероятностей и математической статистике. РХД, 2003. (ISBN 5-93972-150-8).
  • Козлов М. В. Элементы теории вероятностей в примерах и задачах. МГУ, 1990. (ISBN 5-211-00312-8).
  • Goldberg S. A Direct Attack on a Birthday Problem (англ.) // Mathematical Mathematics Magazine. — May 1976. — Fasc. 49. — P. 130-132..
  • Mosteller F. Understanding the Birthday Problem (англ.) // The Mathematics Teacher. — May 1962. — P. 322-325..