Русская Википедия:Парадокс дней рождения
Парадо́кс дней рожде́ния — утверждение, состоящее в том, что в группе, состоящей из 23 или более человек, вероятность совпадения дней рождения (число и месяц) хотя бы у двух людей превышает 50 %. Например, если в классе 23 ученика или более, то более вероятно то, что у какой-то пары одноклассников дни рождения придутся на один день, чем то, что у каждого будет свой неповторимый день рожденияШаблон:Sfn. Впервые эта задача была рассмотрена Рихардом Мизесом в 1939 годуШаблон:Sfn[1].
Для 57 и более человек вероятность такого совпадения превышает 99 %, хотя 100 % она достигает, согласно принципу Дирихле (здравому смыслу), только тогда, когда в группе не менее 367 человек (ровно на 1 больше, чем число дней в високосном году; с учётом високосных лет).
Такое утверждение может показаться неочевидным, так как вероятность совпадения дней рождения двух человек с любым днём в году <math>(\tfrac{1}{365} = 0{,}27\,\%)</math>, умноженная на число человек в группе (23), даёт лишь <math>\tfrac{1}{365} \times 23 = 6{,}3\,\%</math>. Это рассуждение неверно, так как число возможных пар <math>(\tfrac{23 \times 22}{2} = 253)</math> значительно превышает число человек в группе (253 > 23). Таким образом, утверждение не является парадоксом в строгом научном смысле: логического противоречия в нём нет, а парадокс заключается лишь в различиях между интуитивным восприятием ситуации человеком и результатами математического расчёта.
Интуитивное восприятие
В группе из 23 человек вероятность совпадения дней рождения у двух человек столь высока, потому что рассматривается вероятность совпадения дней рождения у любых двух человек в группе. Эта вероятность определяется количеством пар людей, которые можно составить из 23 человек. Так как порядок людей в парах не имеет значения, общее число таких пар равно числу сочетаний из 23 по 2, то есть (23 × 22) / 2 = 253 пары.
В формулировке парадокса речь идёт именно о совпадении дней рождения у каких-либо двух членов группы. Одно из распространённых заблуждений состоит в том, что этот случай путают с другим случаем, на первый взгляд похожим, когда из группы выбирается один человек и оценивается вероятность того, что день рождения каких-либо других членов группы совпадёт с днём рождения выбранного человека. В последнем случае вероятность совпадения значительно ниже.
Расчёт вероятности
Требуется определить вероятность того, что в группе из n человек как минимум у двух из них дни рождения совпадут.
Пусть дни рождения распределены равномерно, то есть примем, что:
- в году 365 дней (нет високосных лет);
- в группе нет людей, заведомо родившихся в один день (например, близнецов);
- рождаемость не зависит от дня недели, времени года и других факторов.
В действительности это не совсем так — в частности, в некоторых странах из-за особенностей работы больниц больше детей рождается в определённые дни недели. Однако неравномерность распределения может лишь увеличить вероятность совпадения дней рождения, но не уменьшить: если бы все люди рождались только в 3 дня из 365, то вероятность совпадения дней рождения была бы очень высокой.
Рассчитаем сначала <math>\bar p(n)</math> — вероятность того, что в группе из <math>n</math> человек дни рождения всех людей будут различными. Если <math> n > 365 </math>, то в силу принципа Дирихле вероятность <math>\bar p(n)</math> равна нулю. Если же <math> n \leqslant 365 </math>, то будем рассуждать следующим образом. Возьмём наугад одного человека из группы и запомним его день рождения. Затем возьмём наугад второго человека, при этом вероятность того, что у него день рождения не совпадёт с днем рождения первого человека, равна <math> 1 - \frac{1}{365} </math>. Затем возьмём третьего человека; при этом вероятность того, что его день рождения не совпадёт с днем рождения одного из первых двух, равна <math> 1 - \frac{2}{365} </math>. Рассуждая по аналогии, мы дойдём до последнего человека, для которого вероятность несовпадения его дня рождения со всеми предыдущими будет равна <math> 1 - \frac{ n - 1 }{365} </math>. Перемножая все эти вероятности, получаем вероятность того, что все дни рождения в группе будут различными:
- <math> \bar p(n) = </math> <math> 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) = </math> <math> { 365 \cdot 364 \cdot \ldots \cdot (365-n+1) \over 365^{n}} = </math> <math> { 365! \over 365^{n} (365-n)! } . </math>
Тогда вероятность того, что хотя бы у двух человек из n дни рождения совпадут, равна
- <math> p(n) = 1 - \bar p(n) .</math>
Значение этой функции превосходит 1/2 при <math> n = 23 </math>, при этом вероятность совпадения равна примерно 50,73 %, а <math>p(22) \approx 47,57 \%</math>. Список значений 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 % |
Данную задачу можно переформулировать в терминах классической «задачи о совпадениях». Пусть:
- урна содержит <math>M</math> шаров (в данном случае <math>M</math> — количество дней в году, принятое равным 365 дням);
- шары пронумерованных числами 1, 2, …, <math>M</math>;
- производится несколько выборок по n шаров из урны (в данном случае n — количество человек в группе);
- изъятые шары возвращаются в урну после каждой выборки;
- выборки считаются упорядоченными, то есть выборки <math>\{ 1, 2, 4, 6 \}</math> и <math>\{ 4, 2, 6, 1 \}</math> считаются различными.
Требуется посчитать вероятность события, заключающегося в отсутствии повторений в выборке. Все расчёты аналогичны приведённым выше.
Альтернативный метод
Вероятность совпадения дней рождения у двух человек, входящих в группу из n людей, можно также рассчитать с использованием формул комбинаторикиШаблон:Sfn. Представим, что каждый день года — это одна буква в алфавите, и алфавит состоит из 365 букв. Дни рождения n человек могут быть представлены строкой, состоящей из n букв такого алфавита. По формуле Хартли, количество возможных строк равно
- <math>n_\text{total} = 365^n.</math>
Количество возможных строк, в которых буквы не повторяются (размещение из 365 по n), составит
- <math>n_\text{unique} = \frac{365!}{(365 - n)!}.</math>
Если строки выбираются случайно (с равномерным распределением), вероятность выбора строки, в которой хотя бы две буквы совпадут, равна
- <math> p(n) = 1 - \frac{n_\text{unique}}{n_\text{total}} = 1 - \frac{\frac{365!}{(365 - n)!}}{365^n}</math> при <math>n \leqslant 365</math> и
- <math>p(n) = 1</math> при <math>n > 365</math>.
Таким образом,
- <math>
\frac{\left(\frac{365!}{(365 - n)!}\right)}{365^n} =
\frac{365 \cdot 364 \cdot 363 \cdots (365 - n + 1)}{365^n} = {}</math><math>
\frac{365}{365} \cdot \frac{364}{365} \cdot \frac{363}{365} \cdots \frac{365 - n + 1}{365} = {}</math><math>
1 \cdot \left(1 - \frac{1}{365}\right) \cdot \left(1 - \frac{2}{365}\right) \cdots \left(1 - \frac{n - 1}{365}\right),
</math>
а это выражение эквивалентно представленному выше.
Также общее количество возможных строк можно рассчитать по формуле комбинаторики количества размещений с повторениями А(повт) n/365 = 365n.
Аппроксимации
Экспоненциальная функция
Используя разложение экспоненциальной функции в ряд Тейлора
- <math> e^x = 1 + x + \frac{x^2}{2!} + \ldots , </math>
приведённое выше выражение для <math> \bar p(n) </math> можно аппроксимировать следующим образом:
- <math> \bar p(n) \approx 1 \cdot e^{ -1/365 } \cdot e^{ -2/365 } \cdots e^{ -(n-1)/365 } = </math> <math> 1 \cdot e^{ -( 1 + 2 + \cdots + ( n - 1 ) )/365 } = </math> <math> e^{ -\frac{ n(n-1) }{ 2 \cdot 365 } } . </math>
Следовательно:
- <math> p(n) = 1 - \bar p(n) \approx 1 - e^{ -\frac{ n(n-1) }{ 2 \cdot 365 } } . </math>
Заметим, что и упрощенная аппроксимация
- <math> p(n) \approx 1-e^{ -\frac{ n^2 }{ 2 \cdot 365 } },</math>
как видно по графику, всё ещё даёт достаточную точность.
Приведём ещё одну аппроксимацию.
Вероятность того, что у двух людей дни рождения не совпадают, равна 364/365. В группе из <math> n </math> человек <math> C( n, 2 ) = \frac{ n(n-1) }{2} </math> пар. Поэтому вероятность <math> \bar p(n) </math> при условии независимости этих событий может быть приближена числом
- <math> \left( \frac{364}{365} \right)^{ C(n,2) } . </math>
Следовательно, получаем приближение для искомой вероятности p(n):
- <math> p(n) \approx 1 - \left( \frac{364}{365} \right)^{ C(n,2) } . </math>
Пуассоновское приближение
Используя приближение Пуассона для бинома, исходя из предыдущего приближения для <math> p(n) </math>, получим чуть больше 50 %:
- <math> \operatorname{Poi} \left( \frac{ C(23,2) }{365} \right) = \operatorname{Poi} \left( \frac{253}{365} \right) \approx \operatorname{Poi}( 0{,} 693\, 2 ) ; </math>
- <math> \mathbb{P} \left( \{ X>0 \} \right) = 1 - \mathbb{P} \left( \{X=0\} \right) = 1 - e^{ -0{,}693\,2 } = 1 - 0{,}499\,998 = 0{,}500\,002 . </math>
Расчёт количества человек, при котором вероятность составляет 50 %
Из приведённой ранее формулы <math> p(n) = 1 - \bar p(n) \approx 1 - e^{ -\frac{ n(n-1) }{ 2 \cdot 365 } } </math> выразим n. Затем вместо p(n) подставим 50 % (0,5). В результате получим:
- <math>n \approx \frac{1}{2} + \sqrt{\frac{1}{4} - 2 \cdot 365 \cdot \ln 0{,}5} = 22{,}9999.</math>
Существует ещё один способ оценки n при вероятности 50 %. Согласно доказанному выше:
- <math>\bar p(n) = 1 - p(n) = \prod_{k=1}^{n-1} \left(1 - \frac{k}{365}\right).</math>
Найдём наименьшее n, при котором
- <math>p(n) > \frac{1}{2}</math>
или, что то же самое,
- <math>\bar p(n) < \frac{1}{2}.</math>
Воспользуемся приведённой выше аппроксимацией функции <math>\bar p(n)</math> экспоненциальной функцией:
- <math>\bar p_\text{approx}(n) = \prod_{k=1}^{n-1} e^{\frac{-k}{365}} = e^{\frac{-n(n - 1)}{2 \cdot 365}}.</math>
Подставив <math>\bar p_\text{approx}(n)</math> вместо <math>\bar p(n)</math> в выражение <math>\bar p(n) < \frac{1}{2}</math>, получим
- <math>e^{\frac{-n(n - 1)}{2 \cdot 365}} < \frac{1}{2}.</math>
Решая относительно n, получим
- <math>n^2 - n > 2 \cdot 365 \cdot \ln 2.</math>
Отсюда найдём n и округлим до целого:
- n = 23.
Родившиеся в один день с заданным человеком
Сравним вероятность p(n) с вероятностью того, что в группе из n человек день рождения какого-либо человека из группы совпадёт с днём рождения некоторого заранее выбранного человека, не принадлежащего группе. Эта вероятность равна
- <math>q(n) = 1 - \left(\frac{365 - 1}{365}\right)^n.</math>
Ось абсцисс: количество человек 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). Если выразиться точнее, то это происходит из-за того, что при сложении вероятностей совпадений мы каждый раз вычитаем вероятность совместного появления этих событий, так как события являются совместными и вероятность их совместного появления при сложении учтена дважды. P(A + B) = P(A) + P(B) − P(AB) и т. д с каждым добавлением нового слагаемого.
Обобщения
Совпадение дискретных случайных величин
Описанная задача может быть сформулирована в общем виде:
- даны случайные числа;
- случайные числа распределены равномерно в диапазоне от 1 до d;
- n — количество случайных чисел;
- определить p( n ; d ) — вероятность того, что совпадут хотя бы два числа из заданных.
Если рассуждать таким же образом, как описано выше, можно получить общие решения:
- <math> 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} ; </math>
- <math> p(n;d) \approx 1 - e^{ -( n(n-1) )/2d } ; </math>
- <math> q(n;d) = 1 - \left( \frac{ d-1 }{d} \right)^n . </math>
Обратная задача:
- дана p — вероятность того, что совпадают хотя бы два случайных числа;
- известно, что случайные числа распределены равномерно в диапазоне от 1 до d;
- найти n(p;d) — количество случайных чисел.
Решение:
- <math> n(p;d) \approx \sqrt{ 2d \cdot \ln \left( { 1 \over 1 - p } \right) } . </math>
Несколько типов людей
Выше парадокс дней рождения был представлен для одного «типа» людей. Можно обобщить задачу, введя несколько «типов», например, разделив людей на мужчин (m) и женщин (n). Подсчитаем вероятность того, что хотя бы у одной женщины и у одного мужчины совпадают дни рождения (совпадение дней рождения у двух женщин или у двух мужчин не учитываются):
- <math> 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 ) , </math>
где 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» («поймать — поймать снова»). Действительно, если каждую пойманную рыбу помечать и отпускать, то вероятность поймать помеченную рыбу будет расти нелинейно (в соответствии с приведённым выше графиком) с ростом количества попыток. Размер популяции грубо может быть оценён как квадрат числа попыток, совершаемых до вылавливания первой помеченной рыбы.
Решение задачи в общем виде находит применение во многих разделах математики, например, в недетерминированных алгоритмах факторизации. Так, одно из самых простых объяснений ρ-метода Полларда аналогично объяснению парадокса дней рождения: достаточно иметь примерно <math>\sqrt{p}</math> случайных чисел от 0 до <math> n = p q </math>, где <math>p < q </math> — простые, чтобы хотя бы для одной из пар чисел с высокой вероятностью нашёлся <math>\gcd \left( |x-y|, n \right) > 1 </math>, который и будет делителем числа n.
Обратные задачи
- Поиск наименьшего числа n, при котором вероятность p(n) больше заданного числа p.
- Поиск наибольшего числа n, при котором вероятность p(n) меньше заданного числа p.
Пользуясь формулой, приведённой выше, получаем:
- <math> n(p;365) \approx \sqrt{ 2 \cdot 365 \cdot \ln \left( { 1 \over 1 - p } \right) } . </math>
| 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.
Среднее число людей
Рассмотрим другую задачу. Сколько в среднем нужно людей для того, чтобы хотя бы у двух из них совпали дни рождения?
Эта проблема имела отношение к алгоритмам хеширования и была исследована Дональдом Кнутом. Оказывается, что интересующая нас случайная величина имеет математическое ожидание, равное
- <math> \overline{n} \, = \, 1 + Q(M) , </math>
где
- <math> Q(M) = \sum_{ k=1 }^{M} \frac{ M! }{ (M-k)! M^k } . </math>
Функция
- <math> 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} }</math>
была исследована Рамануджаном. Он же получил для этой функции следующее асимптотическое разложение:
- <math> Q(M) \sim \sqrt{ \frac{ \pi M }{2} } - \frac{1}{3} + \frac{1}{12} \sqrt{ \frac{\pi}{2M} } - \frac{4}{ 135 M } + \cdots . </math>
При M = 365 среднее число людей равно
- <math> \overline{n} \, = \, 1 + Q(M) \approx 24,61658. </math>
Это число немного больше, чем число людей, обеспечивающих вероятность 50 %. Как ни удивительно, необходимое число людей равно M + 1 = 366 (у 365 людей дни рождения могут распределиться по каждому из 365 дней года без совпадений), хотя в среднем нужно лишь 25.
См. также
Примечания
Литература
Ссылки
- Парадоксы теории вероятностей.
- Сравнительный обзор алгоритмов PGP. Парадокс «дней рождения» и стойкость криптографии.
- Eurobirthdays 2012 годаШаблон:Ref-en. Практический пример.
.png){kind=link}
