zadachi_ds: Парадокс дней рождения

Условие

В классе 23 человека. Какова вероятность, что у двоих совпадают дни рождения? Сколько нужно человек, чтобы вероятность превысила 50%? Сколько — для 99%?

(Считайте, что дни рождения независимы и равномерно распределены по 365 дням; 29 февраля игнорируем.)

Решение

Подход — через дополнение

Проще считать вероятность, что все дни разные, и взять 1 − P(все разные).

P(все разные) = 365! / (365^n · (365 − n)!)
              = (365/365) · (364/365) · (363/365) · ... · ((365−n+1)/365)

Для n = 23

import math
n, days = 23, 365
p_distinct = math.prod((days - i) / days for i in range(n))
print(1 - p_distinct)            # ≈ 0.5073

→ ≈ 50.7% уже при 23 людях. Это и есть «парадокс».

Почему «парадокс»

Интуитивно кажется: «дней 365, людей всего 23 — какая там вероятность?». Но мы считаем не «совпадение с фиксированной датой», а «есть какая-то пара». Количество пар = C(23, 2) = 253, и каждая пара совпадает с вероятностью 1/365.

Простое (но неточное) приближение через линейность:

P ≈ C(n, 2) / 365 = n(n-1) / 730
n = 23 → 253/730 ≈ 0.347   (грубо)

Точная формула выше.

Точные пороги

def p_birthday(n, days=365):
    return 1 - math.prod((days - i) / days for i in range(n))
 
# найти минимальное n для p > threshold
for n in range(1, 100):
    if p_birthday(n) > 0.99:
        print(f"n = {n}, p = {p_birthday(n):.4f}")
        break
# n = 57, p = 0.9901

Приближение

Для не очень больших n:

P ≈ 1 − exp(−n(n-1) / (2·365))

Проверка: n=23 → 1 − exp(−253/730) = 1 − exp(−0.347) ≈ 0.293 — заметное расхождение с точным 0.507. Приближение неплохое для small n, но при n ≈ 23 уже не очень.

Применение в DS / IT

• Хэш-коллизии: для k-битных хэшей коллизия с вероятностью 50% при n ≈ √(2^k) объектах. Для 64-bit hash — √2^64 ≈ 4 млрд → надо быть осторожным.
• A/B-тест IDs: 2 эксперимента с k-значными ID — вероятность коллизии = birthday paradox.
• Bot detection: вероятность совпадения user-agent + IP в большой пуле.

# вероятность коллизии для 32-bit hash и n объектов
def p_hash_collision(n, bits=32):
    return 1 - math.exp(-n*(n-1) / (2 * 2**bits))
print(p_hash_collision(77163, 32))      # ≈ 0.5

Подводные камни

1. «29 февраля + неравномерность по сезонам»: реальное распределение чуть неравномерно (зима, септ). Парадокс это усиливает (не ослабляет): P(совпадения) растёт.
2. «Конкретная дата» vs «любая пара»: P(хотя бы один в группе из 23 родился 1 января) ≈ 1 − (364/365)^23 ≈ 0.061. Совсем другая задача.
3. Зависимости (близнецы): двое в одной семье — заведомо совпадение. В реальном классе влияет.
4. Высокая P не означает «в каждом классе»: 50.7% — означает «чаще, чем в половине классов из 23 человек». В конкретном — может не быть.
5. math.prod появился в Python 3.8; до — через reduce(mul, ...).

Эталонный ответ

P(n=23) = 1 - Π_{i=0..22} (365-i)/365 ≈ 0.507

• 50% превышается при n = 23.
• 99% — при n = 57.

Парадокс: интуиция думает «совпадение с фиксированной датой», тогда как считается «любая пара». Количество пар растёт как n²/2, отсюда такой быстрый рост вероятности.

Применение в IT: hash collisions (p ≈ 50% при n ≈ √(2 · M) для M-возможных ключей).