Birthday paradox что это
Наверняка большинство из читающих эту статью сталкивались с тем, что их день рождения не такой уж уникальный, и среди знакомых есть хотя бы один человек, родившийся в этот день. И если вы считаете, что шанс родится в один день со всеми вашими знакомыми равен 1/365, то вы глубоко заблуждаетесь…
Неумолимая математика говорит нам о том, что если в группе 23 знакомых человека, то шансы родиться в один день для двух из них превышают 50% . Этот парадокс называется парадоксом дней рождения, хотя, по большому счету, никаким парадоксом он не является, а называется так только потому, что интуитивно мы чувствуем, что такого быть не может. И только математическое решение показывает нам, что никакого чуда нет.
Итак, с какой вероятностью два человека имеют день рождения в один день? Любой скажет, что это 1/365 (или 0,27%), и это будет абсолютно правильно – но только для двух человек. Или давайте считать по-другому: вероятность того, что дни рождения у них не совпадут, равняется:
Давайте рассмотрим трёх человек. Вероятность того, что день рождения одного человека не совпадет с днями рождения оставшихся двух человек равна:
Аналогично для четырех человек вероятность несовпадения дней рождения у одного из них с другими равна:
Для пяти человек:
То есть, вероятность несовпадения для одного человека определяется формулой
Применение
Парадокс дней рождения — это не просто искусственная задача или любопытный трюк для вечеринок, он имеет множество областей применения в реальном мире. Лично я считаю, что вероятностный анализ, используемый в доказательствах, полезен при анализе других задач, в которых задействована рандомизация. В частности, это относится к области разработки криптографических хэш-функций. Мы посмотрим, как сделанный выше анализ может оказаться довольно полезен при создании хэш-функций с защитой от атак «дней рождения».
Для начала определим, что такое хэш-функция. Хэш-функция — это функция, выполняющая отображение из множества в число в интервале . Функция , определяемая как — пример хэш-функции из . Хэш-функции имеют множество применений, особенно в сочетании с популярной структурой данных «хэш-таблица». Также она используется в криптографии, где применяется специфический тип хэш-функции под названием «крипторафическая хэш-функция».
Одно из множества свойств, которыми должна обладать крипторафическая хэш-функция — стойкость к коллизиям. Должно быть сложно найти два таких , чтобы они образовывали коллизию, т.е. .
Именно на стойкости к коллизиям мы и сосредоточимся. Во-первых, я объясню, почему она является желательным свойством. Для этого мы сначала рассмотрим цифровые подписи.
В прошлом для «подписания» документов люди и организации пользовались подписями и печатями. В последнее время происходит переход к электронным или цифровым подписям. Цифровая подпись должна удовлетворять трём основным свойствам.
- При подписании документа нужна возможность проверить, кто подписал документ.
- После подписания документа никто не должен иметь возможности его подделать.
- Лицо, подписавшее документ, не может в дальнейшем опровергнуть подписание документа.
Допустим, у нас есть документ . Как нам его подписать?
Каждый пользователь/организация имеет уникальный закрытый ключ и открытый ключ . Они используют функцию подписания для подписи документа собственным закрытым ключом. Однако цифровая подпись может подписать только небольшое количество документов. Область определения функции подписи мала. Один из способов решения этой проблемы — создание меньшего документа, представляющего исходный документ, но в гораздо меньшем размере. Чаще всего для этого к большому документу применяется хэш-функция. Хэш-функция используется для отображения его из большого пространства в меньшее, и результат такой операции называется «отпечатком». Подпись использует отпечаток и закрытый ключ для создания подписи. Процедуру можно описать так:
- Получаем закрытый ключ .
- Хэшируем документ и получаем .
- Подписываем при помощи закрытого ключа .
- Отправляем и открытый ключ всем, кто желает подтвердить документ.
Проблема: предположим, что злоумышленник Ева нашла два документа , где — это настоящий договор, а — мошеннический документ, такой, что . Предположим, что Ева заранее знает, что Алиса подпишет только , но не . Перед подписанием к документу применяется криптографическая хэш-функция . Ева подходит к Алисе и просит её подписать документ , воспользовавшись описанной выше последовательностью. Теперь Ева может заявить, что Алиса подписала мошеннический документ , потому что . Алиса никаким образом не сможет доказать, что она не подписывала .
В приведённом выше примере оказалась нестойкой к коллизиям функцией, поэтому Ева смогла найти два входящих набора данных, хэширующихся в то же значение. Ева смогла заявить, что Алиса подписала , хотя на самом деле она подписала только . Это подчёркивает важность стойкости к коллизиям и показывает, почему цифровые подписи уязвимы, если хэш-функция оказывается нестойкой.
Пусть будет хэш-функцией. Допустим, что входные данные случайным образом однородно и независимо хэширутся в любой из элементов .
Задача атаки «дней рождения» — найти наименьшее количество элементов , которое можно хэшировать при помощи , чтобы мы могли найти два элемента , при которых .
При атаке «дней рождения» злоумышленник будет случайным образом подбирать и сохранять пары . Злоумышленник многократно будет выбирать и сохранять эти пары, пока не найдёт двух значений , при которых . Нам нужно определить, сколько раз атакующему нужно повторить эту операцию, пока он не найдёт коллизию.
Для анализа атаки «дней рождения» можно использовать те же принципы, которые мы применяли для парадокса дней рождения. В атаке «дней рождения» обозначает количество дней в году, а аналогична людям, входящим в комнату. Люди хэшируются в их дни рождения, которые могут быть одним из значений . Допустим, нам нужно найти коллизию с вероятностью 99%. Мы должны знать, каково наименьшее , при котором хэш двух значений будет одним днём рождения (в мире хэш-функций это означает, что два входных набора данных хэшируются в одинаковое значение).
Ранее мы показали, что
Мы хотим задать , то есть .
Показанный выше анализ говорит нам, что для получения коллизии в хэш-функции с интервалом размера злоумышленнику нужно однородно и независимо хэшировать приблизительно для почти полной гарантии (вероятности 99%) того, что два элемента хэшируются в одинаковое значение.
Допустим, что мы хотим получать коллизию с вероятностью 50%; тогда нам нужно . Важный вывод здесь заключается в том, что для получения коллизии с вероятностью больше 0,5 нам придётся хэшировать порядка элементов. Это согласуется с нашим предыдущим анализом при , потому что приблизительно равен 23.
Что связывает парадокс дней рождения и уязвимости электронных подписей?
Допустим, я спрошу вас, сколько человек должно быть в комнате, чтобы у двух из них день рождения с вероятностью 50% приходился на один день. Каким будет ответ? Именно это и называется парадоксом дней рождения.
Если в комнате есть 23 человека, то с вероятностью 50% двое из них родились в один день.
В некоторых версиях парадокса делаются ещё более сильные заявления:
Если в комнате 70 человек, то с вероятностью 99% двое из них родились в один день.
Поначалу это казалось мне удивительным и контринтуитивным. Давайте выясним, почему же это правда. Чтобы упростить задачу, мы сделаем следующие допущения:
- Будем считать, что все люди в комнате родились не в високосный год. Мы делаем это допущение, чтобы нам не пришлось анализировать два разных случая.
- В комнате нет близнецов. При наличии пары близнецов решение будет тривиальным.
- Мы предполагаем, что люди рождаются равномерно и случайно. Что это значит? Люди с равной вероятностью могут рождаться в любой день года. Если немного это формализовать, то вероятность рождения в любой выбранный день равна .
- Люди рождаются независимо друг от друга. Это значит, что дата рождения любого человека не влияет на дату рождения другого.
Представим, что в комнате один человек, тогда вероятность его общего дня рождения с кем-то ещё равна 0. Пусть будет исходом, при котором среди людей ни один день рождения не совпадает. Пусть — вероятность того, что среди людей в комнате каждый имеет день рождения в свой день. Аналогично, пусть будет дополнением , т.е. исходом, при котором среди людей два человека имеют одинаковый день рождения.
Допустим, в комнате два человека, A и B. Без утери обобщения просто представим, что человек A родился 1 января. Чтобы у B и A были разные дни рождения, нужно, чтобы B родился в любой день, кроме 1 января. У человека B будет 364 варианта дня рождения.
Представим, что в комнате три человека, A, B и C. Допустим, что человек A родился 1 января, тогда чтобы все они родились в разные дни, человеку B остаётся только 364 дней, как и в предыдущем примере. Так как A и B занимают два дня, человек C может родиться только в 365 — 2 = 363 дня.
Здесь происходит нечто более интересное: предположим, что в комнате уже есть людей. Когда в комнату заходит -тый человек, то чтобы все человек имели разные дни рождения, должны быть истинными два исхода
- Все людей, вошедших в комнату до него, должны иметь разные дни рождения. Какова вероятность этого? .
- -тому человеку нужно иметь отличающийся день рождения от всех других людей в комнате. Какова вероятность этого? .
Теперь вычислим вероятности:
Поскольку мы получили , это будет означать, что вероятность общего дня рождения для двух людей равна
При увеличении вероятность стремится к 1 и достигает её.
Парадокс дней рождений на данных ВКонтакте
Я решил проверить парадокс дней рождений на данных, которые доступны из ВК.
Что такое парадокс дней рождений?
Попробуйте ответить на вопрос: Какое количество людей в комнате необходимо, чтобы у двух людей были одинаковые дни рождения с вероятностью 0.5? (дата и месяц). Парадокс дней рождений отвечает на этот вопрос.
Для того, чтобы решить задачу стоит выделить несколько предпосылок:
- В модели не будет 29 февраля => в модели 365 дней в году
- Каждый из 365 дней равновероятен.
Большинство людей интуитивно отвечают на вопрос задачи: 180. Выглядит логично, 180 человек необходимо для того, чтобы иметь вероятность 0.5 одинаковых дней рождений(всего же 365 дней). Примерна такая интуиция у всех, кто никогда не слышал про парадокс дней рождений. Правильный ответ на самом деле сильно меньше 180, и даже 150, и даже 100: 23.
Необходим как минимум 1 совпадающий день рождения — поэтому я могу найти вероятность, отсутствия совпадающих дней рождений:
.
Идея такая: я беру первого человека и запоминаю его день рождения, далее второго и вычисляю вероятность, что его день рождения не совпадает с днем рождения первого; далее третьего и его вычисляю вероятность, что его день рождение не совпадет с днями рождения первого и второго.
Решая уравнение, получается, что необходимо 23 человека и вероятность совпадающих дней рождений будет 0.5073, при 100 людях, вероятность равна 0.9999.
Посмотрим парадокс на данных ВК?
В теории у нас при 23 людях вероятность совпадающих дней рождений 0.5073, при 50 людях 0.97, а при 100 0.99. Проверим это через VK API.
1. Выбираю большое сообщество в ВК. Я решил взять группу MDK во Вконтакте…
В начале я создаю csv файл с колонками, которые мне необходимы.
Логинюсь в ВК через API и задаю необходимый мне паблик
Начинаем парсить ВКонтакте, их API позволяет запарсить только 1000 юзеров, поэтому создаю цикл.
В теории мы предполагали, что дни рождения равновероятны, а что происходит на практике? Построю гистограмму дней рождений.
Дни рождения по месяцам не являются равновероятнотными событиями, что в целом достаточно логично — это всего лишь предпосылка для решения проблемы дней рождений. Очевидно, что будут наблюдаться различные сезонные являения, для различных локаций. Почему-то июль наиболее популярный месяц для дня рождения подписчиков МДК.
Эмпирически оценю вероятность того, что в группе из 50 произвольных людей найдутся хотя бы двое с одинаковым днём рождения. Для этого я написал цикл, в ходе которого из таблички происходит подвыборка из 50 строк. Для этих 50 строк внутри условия я проверил совпадение дней рождений. Если совпало, то я запомнил это в переменную счётчик, которую я впоследствии, чтобы получить вероятность, поделю на длину цикла.
Вероятность получается в районе 0.97, что совпадает с теоретическими данными.
Вывод
Интересно было посмотреть, как теория соотносится с эмпирикой и в данном случае данные подтверждают теорию. Стоит отметить, что результат репрезентативен, так как выборка достаточно большая — 20000 человек.
Парадокс дней рождений: разбираю на пальцах
Представьте, что вы находитесь в группе из 30 человек. Как вы считаете, велики ли шансы того, у кого-либо в этой группе совпадут дни рождения (ДР)? Казалось бы, вероятность небольшая, ведь в году 365 или 366 дней, то есть вариантов для рождения более чем в 10 раз больше, чем самих участников.
Но давайте вспомним школьные годы: практически в каждом классе была, как минимум, одна пара людей, празднующих свое появление на свет в один день. В чем же тут дело? Давайте разберемся.
Ключевой момент в том, что нужно посчитать количество пар дат рождения, которые могут быть образованы.
Например, вы со всеми остальными можете создать 29 пар. Но это только с вами. А сколько всего можно образовать пар из 30-ти человек, как это посчитать?
Выстроим всю группу в ряд. У нас есть 30 способов взять первого человека.
После этого остается еще 29 человек для выбора в пару первому. Итого 30*29 = 870 вариантов пар из 30-ти человек.
Но, постойте-ка! Если первый раз мы взяли Машу, а к ней в пару Игоря - то это одна пара из нашего списка. Но если в следующий раз мы возьмем первым Игоря, а в пару к ней Машу - такая пара тоже будет иметь место быть, и зачтется в наш перечень вариантов. Но ведь для нашего случая это все одна и та же пара! Неважно, в каком порядке в нее вошли люди! Поэтому, нам надо поделить на 2 наши 870 вариантов, чтобы получить корректное для нас число пар. Делим: 870 / 2 = 435 .
Итак, 435 пар. Какова вероятность, что в любой отдельно взятой паре дни рождения не совпадут? Скорее всего не совпадут: 364 к 365. Ведь есть 364 варианта родиться в день, отличный от партнера по паре.
А какова вероятность что такое "несовпадение" будет наблюдаться в 435 случаях подряд? Тут работает закон умножения:
Нужно сделать такое перемножение дроби 364/365 самой на себя 435 раз.
Что же получается? Приблизительно 0,3. То есть, с такой вероятностью (30%) мы получим группу из 30 человек, в которой ни у кого не будет ДР в один и тот же день!
Выходит, что ситуация, когда хоть одно совпадение будет иметь место быть, получится с вероятностью 1 - 0,3 = 0,7 = 70%.
Как правило, классы в школе около 30 человек. И поэтому, в большинстве случаев, имеется два именинника в один день!
Ставьте лайк, если знаете хоть одного человека, у которого день рождения в один день с вашим!
Если понравился парадокс, то посмотрите разбор еще одного, куда более неочевидного: парадокс девочки и мальчика простыми словами .
Более сложная задача
Допустим, мы хотим обобщить эту задачу до случая, когда есть людей и возможных дней рождения. Имея , можем ли мы определить вероятность того, что два человека будут иметь общий день рождения?
Можно использовать такую же систему: у нас будет исход , обозначающий все людей, родившихся в разные дни. В случае с одним человеком ничего не меняется
В случае, когда есть два человека, обозначим их как A и B. Чтобы человек B родился в другой день, человек B должен иметь день рождения среди других вариантов.
В случае с тремя людьми человек B должен иметь день рождения, отличающийся от дня рождения A. У человека C должен быть день, отличающийся от дней рождения A и B.
В общем случае для любого мы можем использовать ту же рекурсивную формулу, что и в предыдущем разделе:
Допустим, если мы хотим найти выражение в замкнутой форме для , то мы разложим выражение
Аппроксимацией этого результата является . Хотя мы и можем найти более приближенные границы, это даёт нам достаточную аппроксимацию. Единственное тождество, которое мы использовали в этой аппроксимации:
В абстрактном виде парадокс дней рождения имеет множество применений в компьютерных вычислениях. В частности, он используется в хэшировании, которое само по себе имеет множество применений. Выводы, сделанные в этой задаче, являются ключевыми для анализа вероятности хэширования двух элементов в один ключ. Эту задачу можно ещё более обобщить до вероятностной задачи мячей и корзин (balls and bins problem), которую мы оставим для другого поста.
Читайте также: