Fundamentos e o paradoxo do aniversário

Um espaço amostral Ω é o conjunto de resultados possíveis. Um evento é um subconjunto de Ω. Com resultados equiprováveis, P(A) = |A| / |Ω|: probabilidade vira contagem.

P(A ∪ B) = P(A) + P(B) − P(A ∩ B)
P(não A) = 1 − P(A)
Independentes:  P(A ∩ B) = P(A)·P(B)

Paradoxo do aniversário

Quantas pessoas são necessárias para que duas façam aniversário no mesmo dia com probabilidade > 50%? Só 23. É mais fácil calcular o complemento, a chance de todos serem diferentes:

P(sem colisão) = (365/365)·(364/365)·…·((365−n+1)/365) ≈ e^(−n²/(2·365))

Em geral, com N valores possíveis, colisões aparecem por volta de n ≈ √N.

É por isso que um hash de 64 bits começa a colidir perto de 2³² ≈ 4 bilhões de itens, e não de 2⁶⁴. Também é por isso que UUIDv4 usa 122 bits aleatórios.

import random

def simula(n, dias=365, testes=100_000):
    colisoes = 0
    for _ in range(testes):
        vistos = set()
        for _ in range(n):
            d = random.randrange(dias)
            if d in vistos:
                colisoes += 1
                break
            vistos.add(d)
    return colisoes / testes

print(simula(23))   # ≈ 0.507