Вероятность в комбинаторных задачах: парадокс дней рождения — как считать?
Классическая задача: какова вероятность, что среди k человек у двоих совпадёт день рождения (из n=365 дней)? Интуиция говорит «маленькая», но ответ якобы превышает 50% уже при 23 людях. Как это правильно посчитать комбинаторно и почему интуиция врёт?
2 ответа
Считай вероятность ПРОТИВОПОЛОЖНОГО события — что все дни рождения РАЗНЫЕ — это проще, потом вычти из 1.
P(все разные) = (n/n)·((n−1)/n)·((n−2)/n)·...·((n−k+1)/n) = A(n,k)/n^k,
где A(n,k) — размещения (первый человек любой из n, второй из оставшихся n−1, и т.д.). Тогда P(есть совпадение) = 1 − A(n,k)/n^k.
double birthdayCollision(int n, int k) {
if (k > n) return 1.0; // по Дирихле совпадение неизбежно
double pAllDifferent = 1.0;
for (int i = 0; i < k; i++)
pAllDifferent *= (double)(n - i) / n;
return 1.0 - pAllDifferent;
}
// birthdayCollision(365, 23) ≈ 0.5073
Сложность O(k). Интуиция врёт, потому что мы подсознательно считаем «совпадение с МОИМ днём рождения», а пар людей — C(k,2), и при k=23 это уже 253 пары, каждая со своим шансом совпасть. Растёт квадратично по числу людей — отсюда «парадокс».
Быстрая оценка: вероятность хотя бы одного совпадения ≈ 1 − e^{−k(k−1)/(2n)} (приближение через C(k,2) пар и (1+x)≈e^x). Из неё видно, что порог 50% достигается примерно при k ≈ 1.177·√n. Эта же математика — основа «парадокса дней рождения» в хешировании: коллизия в хеш-таблице/при поиске хеш-столкновений ожидается уже на √n элементах, а не n.