Paradygmat Urodzinowy: Ile Potrzebujesz, Żeby Zdarło Się Coś Jak Losowość?

It's about pairs, not you

The trap most people fall into is imagining the question as "what is the chance someone shares my birthday?" — a small chance, roughly 1 in 365 for each other person. But the birthday paradox asks a different question: what is the chance that any two of n people share a birthday? The number of distinct pairs in a group of n grows like n(n-1)/2, which is quadratic, not linear — with 23 people there are already 253 separate chances for a coincidence, and it only takes one of them to hit.

number of pairs:  C(n,2) = n(n-1)/2
n = 23  ->  23*22/2 = 253 distinct pairs to check for a match

Dokładna formuła

Zamiast bezpośrednio obliczać prawdopodobieństwo dopasowania, znacznie łatwiej jest obliczyć prawdopodobieństwo braku dopasowania i odjąć je od 1. Dodawaj ludzi po kolei: pierwszy może mieć dowolny dzień urodzenia, drugi musi unikać tego pierwszego (364 spośród 365 możliwości), trzeci musi unikać obu poprzednich (363 spośród 365) i tak dalej.

P(no match) = (365/365) * (364/365) * (363/365) * ... * ((365-n+1)/365)
P(match)    = 1 - P(no match)

n = 23  ->  P(match) ~ 50.7%
n = 30  ->  P(match) ~ 70.6%
n = 57  ->  P(match) ~ 99.0%

Dlaczego rośnie tak szybko: przybliżenie wykładnicze

Korzystając z przybliżenia 1 - x ~ e^-x dla każdego czynnika, przekształcamy iloczyn na sumę w potędze, co daje czysty, zamknięty wzór szacunkowy, którego wykładnik skaluje się ze składnią n kwadrat – co dokładnie powoduje, że prawdopodobieństwo rośnie szybciej niż intuicja przewiduje. Ustawiając to przybliżenie na 0,5 i rozwiązując dla n, otrzymujemy n ~ sqrt(2 * 365 * ln 2) ~ 22,99, co prawie idealnie zgadza się z prawdziwym progiem wynoszącym 23.

P(match) ~ 1 - exp( -n(n-1) / (2*365) )
n for 50% chance ~ sqrt(2 * 365 * ln 2) ~ 22.99

Beyond birthdays: hash collisions

The same combinatorics govern birthday attacks on hash functions. A hash with b bits of output has 2^b possible values, and by the same reasoning as above, you expect to find two random inputs that collide after generating on the order of the square root of 2^b samples — not 2^b. This is precisely why cryptographic hash functions need roughly double the output length to resist collision attacks compared with what would be needed to resist a brute-force preimage search, and why 128-bit hashes like MD5 were considered broken for collision resistance long before anyone could realistically search anywhere near its full 2^128 space.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Birthday Paradox i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.