Посчитайте вероятность коллизии хеш-функции

Дана хеш-функция h(x) = x mod p (то есть остаток от целочисленного деления x на p). Для данного n посчитайте вероятность, что для каких-нибудь двух чисел из набора n случайных целых чисел хеш-функция совпадёт. Для каких значений n вероятность будет равна 100%?

Решение

Для начала заметим, что результатом функции могут быть только значения от 0 до p-1, а это означает, что мы можем заменить числа в наборе остатками от их деления на p. Теперь мы можем переформулировать задачу следующим образом: какова вероятность, что в наборе из n целых чисел c возможным значением от 0 до p-1 два числа совпадут. Для решения сначала посчитаем вероятность того, что они все будут различными. Обратимся к формулам комбинаторики: всего наборов может быть pⁿ (количество размещений с повторениями), а наборов, где все числа будут различны (то есть благоприятных исходов), — p ⋅ (p-1) ⋅ (p-2) ⋅ … ⋅ (p-n+1) = p! / (p-n)! (количество размещений). Таким образом, вероятность того, что все числа в наборе будут различны — p! / (pⁿ ⋅ (p-n)!), а значит, вероятность того, что какие-нибудь два из них совпадут — 1 – p!/(pⁿ ⋅ (p-n)!). Осталось ответить на последний вопрос: для каких значений n вероятность станет равна 100%? Очевидно, что для n ≥ p+1. Тогда по принципу Дирихле хотя бы одному значению на интервале 0 .. p-1 будут соответствовать два числа из набора.

Немного истории

Эта задача является обобщением знаменитого парадокса дней рождения, согласно которому в группе из 23 или более человек вероятность того, что день рождения у каких-нибудь двоих из них придется на один день, превышает 50%. Впрочем, парадоксом в классическом смысле этого слова это не является — как видите, мы только что вывели формулу вероятности и даже можем её проверить с помощью длинной арифметики в языке Java.  Если же вы все еще не верите, можете проверить это на своих знакомых, или, например, в комментариях к этой статье — просто напишите дату своего дня рождения.