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

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

Парадо́кс дней рожде́ния — утверждение, гласящее, что если дана группа из 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, то вероятность совпадения дней рождения была бы очень высокой.

Рассчитаем сначала, какова вероятность \bar p(n) того, что в группе из n человек дни рождения всех людей будут различными. Если n>365, то в силу принципа Дирихле вероятность равна нулю. Если же 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,7 %). Вероятности для некоторых значений 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 (в данном случае количество человек в группе), при этом рассматриваемые выборки считаются упорядоченными (то есть выборки \{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}}

для nm\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), можно аппроксимировать следующим образом:

График, показывающий соотношение между точным значением и аппроксимацией 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)\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 %,получим

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

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

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

Найдём наименьшее n,для которого p(n) > 1/2; или, что то же самое,p(n) < 1/2.

Используя разложение экспоненты в ряд Тейлора, получим 1 − x < ex. И следовательно,

\bar p(n) = \prod_{k=1}^{n-1}\left(1-{k \over 365}\right) < \prod_{k=1}^{n-1}\left(e^{-k/365}\right) = e^{-(n(n-1))/(2\times 365)} .

Так как p(n) < 1/2,

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

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

n^2-n > 2\times365\ln 2 \,\! .

Отсюда находим n равно 23.

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

Сравнение вероятностей p (n) и q (n)

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

 q(n) = 1 - \left( \frac{365-1}{365} \right)^n

Подставляя n = 23, получаем q (n) примерно 5,9 %, что лишь немногим лучше одного шанса из 17. Для того, чтобы вероятность совпадения дня рождения с заданным человеком превысила 50 %, число людей в группе должно быть не менее 253. Это число заметно больше, чем половина дней в году (365/2 = 182.5); так происходит из-за того, что у остальных членов группы дни рождения могут совпадать между собой, и это уменьшает вероятность совпадения одного из них с днём рождения заданного человека.

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

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

Задача, представленная парадоксом дней рождения, может быть поставлена в общем виде следующим образом: если даны n равномерно распределённых случайных чисел в диапазоне от 1 до d, то какова вероятность 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

И наоборот, если n(p;d) обозначает количество чисел, принимающих значения от 1 до d,для которого вероятность того, что хотя бы 2 из них совпадают равно p,то

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 количество
различных
выходных
цепочек

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

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

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

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

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

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

n(p;365)\approx \sqrt{2\times 365\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.

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

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

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

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

при M = 365 имеем среднее число людей равное \scriptstyle\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)
  • Ширяев А. Н. Вероятность-1. МЦНМО, 2007. (ISBN 987-5-94057-036-3)
  • Goldberg S. A Direct Attack on a Birthday Problem (англ.) // Mathematical Mathematics Magazine. — May 1976. — В. 49. — С. 130-132.
  • Mosteller F. Understanding the Birthday Problem (англ.) // The Mathematics Teacher. — May 1962. — С. 322-325.
  • Eurobirthdays 2012 года.День рождения проблемы. Практический пример футбольного дня рождения парадокс. (английская версия)