Парадокс дней рожденияПарадокс дней рождения — утверждение, что если дана группа из 23 или более человек, то вероятность того, что хотя бы у двух из них дни рождения (число и месяц) совпадут, превышает 50 %. Для группы из 60 или более человек вероятность совпадения дней рождения хотя бы у двух её членов составляет более 99 %, хотя 100 % она достигает, когда в группе не менее 366 человек (с учётом високосных лет — 367). Такое утверждение может показаться противоречащим здравому смыслу, так как вероятность одному родиться в определённый день года довольно мала, а вероятность того, что двое родились в один и тот же день — ещё меньше, но является верным в соответствии с теорией вероятностей. Таким образом, оно не является парадоксом в строгом научном смысле — логического противоречия в нём нет, а парадокс заключается лишь в различиях между интуитивным восприятием ситуации человеком и результатами математического расчёта.
С точки зрения здравого смыслаОдин из способов понять на интуитивном уровне, почему в группе из 23 человек вероятность совпадения дней рождения у двух человек столь высока, состоит в осознании следующего факта: поскольку рассматривается вероятность совпадения дней рождения у любых двух человек в группе, то эта вероятность определяется количеством пар людей, которые можно составить из 23 человек. Так как порядок людей в парах не имеет значения, то общее число таких пар равно числу сочетаний из 23 по 2, то есть 23 × 22/2 = 253 пары. Посмотрев на это число, легко понять, что при рассмотрении 253 пар людей вероятность совпадения дней рождения хотя бы у одной пары будет достаточно высокой. Ключевым моментом здесь является то, что утверждение парадокса дней рождения говорит именно о совпадении дней рождения у каких-либо двух членов группы. Одно из распространённых заблуждений состоит в том, что этот случай путают с другим - похожим, на первый взгляд, - случаем, когда из группы выбирается один человек и оценивается вероятность того, что у кого-либо из других членов группы день рождения совпадёт с днем рождения выбранного человека. В последнем случае вероятность совпадения значительно ниже (см. далее). Расчёт вероятностиВ данном примере для расчёта вероятности того, что в группе из n человек как минимум у двух дни рождения совпадут, примем, что дни рождения распределены равномерно, т.е. нет високосных лет, близнецов, рождаемость не зависит от дня недели, времени года и других факторов. В действительности, это не совсем так — обычно летом рождается больше детей; кроме того, в некоторых странах из-за особенностей работы больниц больше детей рождается в определённые дни недели. Однако неравномерность распределения может лишь увеличить вероятность совпадения дней рождения, но не уменьшить — даже интуитивно понятно, что если бы все люди рождались только в 3 дня из 365, то вероятность совпадения дней рождения была бы очень высокой. Рассчитаем сначала, какова вероятность p (n) того, что в группе из n человек дни рождения всех людей будут различными. Если n > 365, то в силу принципа Дирихле вероятность равна нулю. Если же n ≤ 365, то будем рассуждать следующим образом. Возьмём наугад одного человека из группы и запомним его день рождения. Затем возьмём наугад второго человека, при этом вероятность того, что у него день рождения не совпадёт с днем рождения первого человека, равна 1 - 1/365. Затем возьмём третьего человека, при этом вероятность того, что его день рождения не совпадёт с днями рождения первых двух, равна 1 - 2/365. Рассуждая по аналогии, мы дойдём до последнего человека, для которого вероятность несовпадения его дня рождения со всеми предыдущими будет равна 1 - (n - 1)/365. Перемножая все эти вероятности, получаем вероятность того, что все дни рождения в группе будут различными: Тогда вероятность того, что хотя бы у двух человек из n дни рождения совпадут, равна Значение этой функции превосходит 1/2 при n = 23 (при этом вероятность совпадения равна примерно 50.7%). Вероятности для некоторых значений n иллюстрируются следущей таблицей:
Альтернативный метод расчётаВероятность совпадения дней рождения в группе можно также рассчитать с использованием формул комбинаторики. Представим, что каждый день года - это одна буква в алфавите из 365 букв. Дни рождения n человек могут быть представлены строкой, состоящей из n букв такого алфавита. Общее число таких строк равно Общее число строк, в которых буквы не повторяются, составит Тогда, если строки выбираются случайно (с равномерным распределением), то вероятность выбрать строку, в которой хотя бы две буквы совпадут, равна для n ≤ 365 и p (n) = 1 для n > 365. Поскольку то это выражение эквивалентно представленному выше. АппроксимацииИспользуя разложение экспоненциальной функции в ряд Тейлора приведённое выше выражение, дающее значение p (n), можно аппроксимировать следующим образом:
График, показывающий соотношение между точным значением и аппроксимацией p (n)
Следовательно, Для ещё более грубой аппроксимации можно взять выражение которое, как показывает график, всё ещё даёт достаточную точность. Родившиеся в один день с заданным человеком
Сравнение вероятностей p (n) и q (n)
Интересно сравнить вероятность p (n) с вероятностью того, что в группе из n человек у кого-либо день рождения совпадет с днём рождения некоторого заранее выбранного человека. Эта вероятность равна Подставляя n = 22, получаем q (n) примерно 5.9 %, что лишь немногим лучше одного шанса из 17. Для того, чтобы вероятность совпадения дня рождения с заданным человеком превысила 50 %, число людей в группе должно быть не менее 253. Это число заметно больше, чем половина дней в году (365/2 = 182.5); так происходит из-за того, что у остальных членов группы дни рождения могут совпадать между собой, и это уменьшает вероятность совпадения одного из них с днём рождения заданного человека. Задача в общем видеЗадача, представленная парадоксом дней рождения, может быть поставлена в общем виде следующим образом: если даны n равномерно распределённых случайных чисел в диапазоне от 1 до d, то какова вероятность p (n ; d) того, что хотя бы два из этих чисел совпадут ? Рассуждая таким же образом, как описано выше, можно получить общие решения: ПриложенияПарадокс дней рождения в более общем смысле применим к хэш-функциям: если хэш-функция генерирует N-битное значение, то число элементов, которые можно обработать без высокой вероятности получения коллизии (то есть возврата одинакового значения функции для двух разных элементов), равно не 2N, а только около 2N/2. Как следствие, небольшое число коллизий хэш-функций в практических приложениях возникает неизбежно. Этот эффект используется в «атаке дня рождения» (birthday attack) на криптографические хэш-функции. Сходный математический аппарат используется для оценки популяции рыб в озёрах методом «capture-recapture». Действительно, если каждую пойманную рыбу помечать и отпускать, то вероятность поймать помеченную рыбу будет расти нелинейно (в соответствии с приведённым выше графиком) с ростом количества попыток. Размер популяции грубо может быть оценен как квадрат числа попыток до первой помеченной пойманной рыбы. Решение задачи в общем виде находит применение во многих разделах математики, например в недетерминированных алгоритмах факторизации. Так, одно из самых простых объяснений ρ-метода Полларда аналогично объяснению парадокса дней рождения: достаточно иметь примерно случайных чисел от 0 до n = pq, где p < q — простые, чтобы хотя бы для одной из пар чисел с высокой вероятностью нашёлся , который и будет делителем числа n. Близкие дни рожденияДругое обобщение парадокса дней рождения состоит в постановке задачи о том, сколько человек нужно для того, чтобы вероятность наличия в группе людей, дни рождения которых различаются не более чем на один день (или на два, три дня и так далее), превысила 50 %. Эта задача более сложная, при её решении используется принцип включения-исключения. Результат (опять-таки в предположении, что дни рождения распределены равномерно) получается следующим:
Таким образом, вероятность того, что даже в группе из 6 людей дни рождения хотя бы у двух будут различаться не более чем на неделю, превышает 50 %. См. также
Литература
|