Меню Главная Случайная статья Настройки Парадокс дней рождения Материал из https://ru.wikipedia.org Парадокс дней рождения — утверждение, состоящее в том, что в группе, состоящей из 23 или более человек, вероятность совпадения дней рождения (число и месяц) хотя бы у двух людей превышает 50 %. Например, если в классе 23 ученика или более, то более вероятно то, что у какой-то пары одноклассников дни рождения придутся на один день, чем то, что у каждого будет свой неповторимый день рождения[1]. Впервые эта задача была рассмотрена Рихардом Мизесом в 1939 году[2][3]. Для 57 и более человек вероятность такого совпадения превышает 99 %, хотя 100 % она достигает, согласно принципу Дирихле, только тогда, когда в группе не менее 367 человек (ровно на единицу больше, чем число дней в високосном году; с учётом високосных лет). Такое утверждение может показаться неочевидным, так как вероятность совпадения дней рождения двух человек с любым днём в году ${\displaystyle ({\tfrac {1}{365}}=0{,}27\,\%)}$, умноженная на число человек в группе (23), даёт лишь ${\displaystyle {\tfrac {1}{365}}\times 23=6{,}3\,\%}$. Это рассуждение неверно, так как число возможных пар ${\displaystyle ({\tfrac {23\times 22}{2}}=253)}$ значительно превышает число человек в группе (253 > 23). Таким образом, утверждение не является парадоксом в строгом научном смысле: логического противоречия в нём нет, а парадокс заключается лишь в различиях между интуитивным восприятием ситуации человеком и результатами математического расчёта. Содержание 1 Интуитивное восприятие 2 Расчёт вероятности 2.1 Альтернативный метод 3 Аппроксимации 3.1 Экспоненциальная функция 3.2 Пуассоновское приближение 4 Расчёт количества человек, при котором вероятность составляет 50 % 5 Родившиеся в один день с заданным человеком 6 Обобщения 6.1 Совпадение дискретных случайных величин 6.2 Несколько типов людей 6.3 Близкие дни рождения 7 Применение 8 Обратные задачи 8.1 Наилучшая позиция 8.2 Среднее число людей 9 См. также 10 Примечания 11 Литература 12 Ссылки Интуитивное восприятие В группе из 23 человек вероятность совпадения дней рождения у двух человек столь высока, потому что рассматривается вероятность совпадения дней рождения у любых двух человек в группе. Эта вероятность определяется количеством пар людей, которые можно составить из 23 человек. Так как порядок людей в парах не имеет значения, общее число таких пар равно числу сочетаний из 23 по 2, то есть (23 22) / 2 = 253 пары. В формулировке парадокса речь идёт именно о совпадении дней рождения у каких-либо двух членов группы. Одно из распространённых заблуждений состоит в том, что этот случай путают с другим случаем, на первый взгляд похожим, когда из группы выбирается один человек и оценивается вероятность того, что день рождения каких-либо других членов группы совпадёт с днём рождения выбранного человека. В последнем случае вероятность совпадения значительно ниже. Расчёт вероятности Требуется определить вероятность того, что в группе из n человек как минимум у двух из них дни рождения совпадут. Пусть дни рождения распределены равномерно, то есть примем, что: в году 365 дней (нет високосных лет); в группе нет людей, заведомо родившихся в один день (например, близнецов); рождаемость не зависит от дня недели, времени года и других факторов. В действительности это не совсем так — в частности, в некоторых странах из-за особенностей работы больниц больше детей рождается в определённые дни недели. Однако неравномерность распределения может лишь увеличить вероятность совпадения дней рождения, но не уменьшить: если бы все люди рождались только в 3 дня из 365, то вероятность совпадения дней рождения была бы очень высокой. Рассчитаем сначала ${\displaystyle {\bar {p}}(n)}$ — вероятность того, что в группе из ${\displaystyle n}$ человек дни рождения всех людей будут различными. Если ${\displaystyle n>365}$, то в силу принципа Дирихле вероятность ${\displaystyle {\bar {p}}(n)}$ равна нулю. Если же ${\displaystyle n\leqslant 365}$, то будем рассуждать следующим образом. Возьмём наугад одного человека из группы и запомним его день рождения. Затем возьмём наугад второго человека, при этом вероятность того, что у него день рождения не совпадёт с днем рождения первого человека, равна ${\displaystyle 1-{\frac {1}{365}}}$. Затем возьмём третьего человека; при этом вероятность того, что его день рождения не совпадёт с днём рождения одного из первых двух, равна ${\displaystyle 1-{\frac {2}{365}}}$. Рассуждая по аналогии, мы дойдём до последнего человека, для которого вероятность несовпадения его дня рождения со всеми предыдущими будет равна ${\displaystyle 1-{\frac {n-1}{365}}}$. Перемножая все эти вероятности, получаем вероятность того, что все дни рождения в группе будут различными: ${\displaystyle {\bar {p}}(n)=}$ ${\displaystyle 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)=}$ ${\displaystyle {365\cdot 364\cdot \ldots \cdot (365-n+1) \over 365^{n}}=}$ ${\displaystyle {365! \over 365^{n}(365-n)!}.}$ Тогда вероятность того, что хотя бы у двух человек из n дни рождения совпадут, равна ${\displaystyle p(n)=1-{\bar {p}}(n).}$ Значение этой функции превосходит 1/2 при ${\displaystyle n=23}$, при этом вероятность совпадения равна примерно 50,73 %, а ${\displaystyle 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 71073)  100 % 350 (1 310131)  100 % 367 100 % Данную задачу можно переформулировать в терминах классической «задачи о совпадениях». Пусть: урна содержит ${\displaystyle M}$ шаров (в данном случае ${\displaystyle M}$ — количество дней в году, принятое равным 365 дням); шары пронумерованных числами 1, 2, …, ${\displaystyle M}$; производится несколько выборок по n шаров из урны (в данном случае n — количество человек в группе); изъятые шары возвращаются в урну после каждой выборки; выборки считаются упорядоченными, то есть выборки ${\displaystyle \{1,2,4,6\}}$ и ${\displaystyle \{4,2,6,1\}}$ считаются различными. Требуется посчитать вероятность события, заключающегося в отсутствии повторений в выборке. Все расчёты аналогичны приведённым выше. Альтернативный метод Вероятность совпадения дней рождения у двух человек, входящих в группу из n людей, можно также рассчитать с использованием формул комбинаторики[4]. Представим, что каждый день года — это одна буква в алфавите, и алфавит состоит из 365 букв. Дни рождения n человек могут быть представлены строкой, состоящей из n букв такого алфавита. По формуле Хартли, количество возможных строк равно ${\displaystyle n_{\text{total}}=365^{n}.}$ Количество возможных строк, в которых буквы не повторяются (размещение из 365 по n), составит ${\displaystyle n_{\text{unique}}={\frac {365!}{(365-n)!}}.}$ Если строки выбираются случайно (с равномерным распределением), вероятность выбора строки, в которой хотя бы две буквы совпадут, равна ${\displaystyle p(n)=1-{\frac {n_{\text{unique}}}{n_{\text{total}}}}=1-{\frac {\frac {365!}{(365-n)!}}{365^{n}}}}$ при ${\displaystyle n\leqslant 365}$ и ${\displaystyle p(n)=1}$ при ${\displaystyle n>365}$. Таким образом, ${\displaystyle {\frac {\left({\frac {365!}{(365-n)!}}\right)}{365^{n}}}={\frac {365\cdot 364\cdot 363\cdots (365-n+1)}{365^{n}}}={}}$${\displaystyle {\frac {365}{365}}\cdot {\frac {364}{365}}\cdot {\frac {363}{365}}\cdots {\frac {365-n+1}{365}}={}}$${\displaystyle 1\cdot \left(1-{\frac {1}{365}}\right)\cdot \left(1-{\frac {2}{365}}\right)\cdots \left(1-{\frac {n-1}{365}}\right),}$ а это выражение эквивалентно представленному выше. Также общее количество возможных строк можно рассчитать по формуле комбинаторики количества размещений с повторениями А(повт)n/365 = 365n. Аппроксимации Экспоненциальная функция Используя разложение экспоненциальной функции в ряд Тейлора ${\displaystyle e^{x}=1+x+{\frac {x^{2}}{2!}}+\ldots ,}$ приведённое выше выражение для ${\displaystyle {\bar {p}}(n)}$ можно аппроксимировать следующим образом: ${\displaystyle {\bar {p}}(n)\approx 1\cdot e^{-1/365}\cdot e^{-2/365}\cdots e^{-(n-1)/365}=}$ ${\displaystyle 1\cdot e^{-(1+2+\cdots +(n-1))/365}=}$ ${\displaystyle e^{-{\frac {n(n-1)}{2\cdot 365}}}.}$ Следовательно: ${\displaystyle p(n)=1-{\bar {p}}(n)\approx 1-e^{-{\frac {n(n-1)}{2\cdot 365}}}.}$ Заметим, что упрощённая аппроксимация ${\displaystyle p(n)\approx 1-e^{-{\frac {n^{2}}{2\cdot 365}}},}$ как видно по графику, также даёт достаточную точность. Приведём ещё одну аппроксимацию. Вероятность того, что у двух людей дни рождения не совпадают, равна 364/365. В группе из ${\displaystyle n}$ человек ${\displaystyle C(n,2)={\frac {n(n-1)}{2}}}$ пар. Поэтому вероятность ${\displaystyle {\bar {p}}(n)}$ при условии независимости этих событий может быть приближена числом ${\displaystyle \left({\frac {364}{365}}\right)^{C(n,2)}.}$ Отсюда получаем приближение для искомой вероятности p(n): ${\displaystyle p(n)\approx 1-\left({\frac {364}{365}}\right)^{C(n,2)}.}$ Пуассоновское приближение Используя приближение Пуассона для бинома, исходя из предыдущего приближения для ${\displaystyle p(n)}$, получим чуть больше 50 %: ${\displaystyle \operatorname {Poi} \left({\frac {C(23,2)}{365}}\right)=\operatorname {Poi} \left({\frac {253}{365}}\right)\approx \operatorname {Poi} (0{,}693\,2);}$ ${\displaystyle \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.}$ Расчёт количества человек, при котором вероятность составляет 50 % Из приведённой ранее формулы ${\displaystyle p(n)=1-{\bar {p}}(n)\approx 1-e^{-{\frac {n(n-1)}{2\cdot 365}}}}$ выразим n. Затем вместо p(n) подставим 50 % (0,5). В результате получим: ${\displaystyle n\approx {\frac {1}{2}}+{\sqrt {{\frac {1}{4}}-2\cdot 365\cdot \ln 0{,}5}}=22{,}9999.}$ Существует ещё один способ оценки n при вероятности 50 %. Согласно доказанному выше: ${\displaystyle {\bar {p}}(n)=1-p(n)=\prod _{k=1}^{n-1}\left(1-{\frac {k}{365}}\right).}$ Найдём наименьшее n, при котором ${\displaystyle p(n)>{\frac {1}{2}}}$ или, что то же самое, ${\displaystyle {\bar {p}}(n)<{\frac {1}{2}}.}$ Воспользуемся приведённой выше аппроксимацией функции ${\displaystyle {\bar {p}}(n)}$ экспоненциальной функцией: ${\displaystyle {\bar {p}}_{\text{approx}}(n)=\prod _{k=1}^{n-1}e^{\frac {-k}{365}}=e^{\frac {-n(n-1)}{2\cdot 365}}.}$ Подставив ${\displaystyle {\bar {p}}_{\text{approx}}(n)}$ вместо ${\displaystyle {\bar {p}}(n)}$ в выражение ${\displaystyle {\bar {p}}(n)<{\frac {1}{2}}}$, получим ${\displaystyle e^{\frac {-n(n-1)}{2\cdot 365}}<{\frac {1}{2}}.}$ Решая относительно n, получим ${\displaystyle n^{2}-n>2\cdot 365\cdot \ln 2.}$ Отсюда найдём n и округлим до целого: n = 23. Родившиеся в один день с заданным человеком Сравним вероятность p(n) с вероятностью того, что в группе из n человек день рождения какого-либо человека из группы совпадёт с днём рождения некоторого заранее выбранного человека, не принадлежащего группе. Эта вероятность равна ${\displaystyle q(n)=1-\left({\frac {365-1}{365}}\right)^{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 ) — вероятность того, что совпадут хотя бы два числа из заданных. Если рассуждать таким же образом, как описано выше, можно получить общие решения: ${\displaystyle p(n;d)={\begin{cases}1-\prod _{k=1}^{n-1}\left(1-{k \over d}\right)&n\leq d\\1&n>d\end{cases}};}$ ${\displaystyle p(n;d)\approx 1-e^{-(n(n-1))/2d};}$ ${\displaystyle q(n;d)=1-\left({\frac {d-1}{d}}\right)^{n}.}$ Обратная задача: дана p — вероятность того, что совпадают хотя бы два случайных числа; известно, что случайные числа распределены равномерно в диапазоне от 1 до d; найти n(p;d) — количество случайных чисел. Решение: ${\displaystyle n(p;d)\approx {\sqrt {2d\cdot \ln \left({1 \over 1-p}\right)}}.}$ Несколько типов людей Выше парадокс дней рождения был представлен для одного «типа» людей. Можно обобщить задачу, введя несколько «типов», например, разделив людей на мужчин (m) и женщин (n). Подсчитаем вероятность того, что хотя бы у одной женщины и у одного мужчины совпадают дни рождения (совпадение дней рождения у двух женщин или у двух мужчин не учитываются): ${\displaystyle 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) 1018 1015 1012 109 106 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» («поймать — поймать снова»). Действительно, если каждую пойманную рыбу помечать и отпускать, то вероятность поймать помеченную рыбу будет расти нелинейно (в соответствии с приведённым выше графиком) с ростом количества попыток. Размер популяции грубо может быть оценён как квадрат числа попыток, совершаемых до вылавливания первой помеченной рыбы. Решение задачи в общем виде находит применение во многих разделах математики, например, в недетерминированных алгоритмах факторизации. Так, одно из самых простых объяснений -метода Полларда аналогично объяснению парадокса дней рождения: достаточно иметь примерно ${\displaystyle {\sqrt {p}}}$ случайных чисел от 0 до ${\displaystyle n=pq}$, где ${\displaystyle p<q}$ — простые, чтобы хотя бы для одной из пар чисел с высокой вероятностью нашёлся ${\displaystyle \gcd \left(|x-y|,n\right)>1}$, который и будет делителем числа n. Обратные задачи Поиск наименьшего числа n, при котором вероятность p(n) больше заданного числа p. Поиск наибольшего числа n, при котором вероятность p(n) меньше заданного числа p. Пользуясь формулой, приведённой выше, получаем: ${\displaystyle 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,14178365 = 2,70864 2 0,00274 3 0,00820 0,05 0,32029365 = 6,11916 6 0,04046 7 0,05624 0,1 0,45904365 = 8,77002 8 0,07434 9 0,09462 0,2 0,66805365 = 12,76302 12 0,16702 13 0,19441 0,3 0,84460365 = 16,13607 16 0,28360 17 0,31501 0,5 1,17741365 = 22,49439 22 0,47570 23 0,50730 0,7 1,55176365 = 29,64625 29 0,68097 30 0,70632 0,8 1,79412365 = 34,27666 34 0,79532 35 0,81438 0,9 2,14597365 = 40,99862 40 0,89123 41 0,90315 0,95 2,44775365 = 46,76414 46 0,94825 47 0,95477 0,99 3,03485365 = 57,98081 57 0,99012 58 0,99166 Наилучшая позиция Пусть в комнате находятся n - 1 человек, и их дни рождения различны. Пусть g(n) — вероятность того, что день рождения вошедшего человека совпадает с днём рождения коголибо из присутствующих в комнате. Требуется найти значение n, при котором значение функции g(n) максимально. Решение сводится к нахождению максимального значения выражения p(n) - p(n-1). Используя приведённую выше формулу для p(n), получим n = 20. Среднее число людей Рассмотрим другую задачу. Сколько в среднем нужно людей для того, чтобы хотя бы у двух из них совпали дни рождения? Эта проблема имела отношение к алгоритмам хеширования и была исследована Дональдом Кнутом. Оказывается, что интересующая нас случайная величина имеет математическое ожидание, равное ${\displaystyle {\overline {n}}\,=\,1+Q(M),}$ где ${\displaystyle Q(M)=\sum _{k=1}^{M}{\frac {M!}{(M-k)!M^{k}}}.}$ Функция ${\displaystyle 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}}}}$ была исследована Рамануджаном. Он же получил для этой функции следующее асимптотическое разложение: ${\displaystyle Q(M)\sim {\sqrt {\frac {\pi M}{2}}}-{\frac {1}{3}}+{\frac {1}{12}}{\sqrt {\frac {\pi }{2M}}}-{\frac {4}{135M}}+\cdots .}$ При M = 365 среднее число людей равно ${\displaystyle {\overline {n}}\,=\,1+Q(M)\approx 24,61658.}$ Это число немного больше, чем число людей, обеспечивающих вероятность 50 %. Как ни удивительно, необходимое число людей равно M + 1 = 366 (у 365 людей дни рождения могут распределиться по каждому из 365 дней года без совпадений), хотя в среднем нужно лишь 25. См. также Задача о письмах Закон больших чисел Примечания Мазур, 2017, с. 116. Мазур, 2017, с. 119. Миронкин В. О., Чухно А. Б. Об одном обобщении парадокса «дней рождения» . Дата обращения: 30 марта 2020. Архивировано 9 июля 2020 года. Мазур, 2017, с. 117. Литература Кемени Дж., Снелл Дж., Томпсон Дж. Введение в конечную математику = Introduction to Finite Mathematics. — Издательство иностранной литературы, 1963. — 488 с. 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. Ссылки Парадоксы теории вероятностей. Сравнительный обзор алгоритмов PGP. Парадокс «дней рождения» и стойкость криптографии. Eurobirthdays 2012 года (англ.). Практический пример.