A születésnap-paradoxon az a jelenség, miszerint megdöbbentően nagy az elméleti valószínűsége annak, hogy viszonylag kevés, egy szobában tartózkodó személy közt lesz kettő, akiknek a születésnapja azonos hónap azonos sorszámú napjára esik.

Pl. ha egy szobában 23-an vannak, akkor valamivel több, mint 50% az elméletileg számított esélye annak, hogy legalább kettőjüknek ugyanarra a napra esik a születésnapja. Ha legalább 58 ember van a szobában, ugyanennek a valószínűsége több, mint 99%. Ez nem abban az értelemben paradoxon, hogy logikai ellentmondásra jutunk, hanem abban, hogy ellentmond az intuíció által sugalltaknak, a legtöbb ember ugyanis 50%-nál lényegesen alacsonyabbra becsüli a fenti esemény valószínűségét. A probléma felvetése és első alapos vizsgálata valószínűsíthetően Harold Davenport angol matematikustól ered, aki 1927 körül fogalmazta meg.

„Elméletileg számított” valószínűségen azt értjük, hogy a számítás során feltételezzük, hogy minden ember azonos statisztikai eséllyel születik az év bármely hónapjának bármely napján. Ez a hipotézis egyébként hamis. (Pl. az Egyesült Államokban a Harvard kutatójának adatai szerint a hetvenes és kilencvenes évek közt eltelt időben szeptember 16-án született abszolút értelemben [nem átlagosan] a legtöbb csecsemő.)^[1] Ez azonban a számított eredmény meglepő voltát nem érintő körülmény (nem emiatt lesz az eredmény paradox).

A fenti esemény (és a hozzá hasonló paradoxonok) pontos valószínűségének kiszámítása klasszikus probléma, rendszeresen tanítják valószínűségszámítási kurzusok részeként az egyetemeken.

A paradoxon megértéséhez kulcsfontosságú, hogy észrevegyük: noha viszonylag kevés ember van a szobában, már így is nagyon sok párt alkotnak, melyeknél a születésnap-egyezést egyenként vizsgálni kell. 23 ember esetén 23 × 22 / 2 = 253 pár van, mindegyik pár egy lehetséges egyezés. A születésnap-paradoxon azt vizsgálja, hogy bármelyik két embernek a 23-ból megegyezik-e a születésnapja.

A valószínűség közelítő kiszámításához elhanyagolunk pár részletet, így a szökőéveket, a jelenlévők közti ikrek lehetőségét, valamint a különböző születési statisztikákat. Ehelyett feltesszük, hogy ha valakinek nem ismerjük a születésnapját, akkor az a 365 napos év minden napján azonos valószínűséggel születhetett.

Azt keressük, hogy mekkora eséllyel lesz n ember közt legalább kettő, akik ugyanazon a napon születtek. Ha ${\displaystyle n>365}$, akkor ez biztosan teljesülni fog (a skatulyaelv triviális esete), így a keresett valószínűség 1. A továbbiakban feltételezzük, hogy ${\displaystyle n\leq 365}$. Az ötlet a következő: a vizsgált esemény helyett a komplementer esemény bekövetkezési valószínűségét számítjuk ki, azaz hogy mekkora a valószínűsége annak, hogy n emberből mindenki más napon született. Ennek értéke:

${\displaystyle {\overline {p}}={\frac {365}{365}}\cdot {\frac {364}{365}}\cdot {\frac {363}{365}}\cdot {\frac {362}{365}}\cdots {\frac {365-n+1}{365}}}$,

mert mindenki az év 365 napjának valamelyikén született, továbbá ha (tetszőlegesen) sorba állítjuk az embereket, akkor a másodiknak nem lehet ugyanakkor a születésnapja, mint az elsőnek (így a megmaradt 364 nap valamelyikén született), a harmadiknak nem lehet akkor, mint az első kettőnek (így a maradék 363 nap valamelyikén született), és így tovább.

A faktoriális jelölését használva ugyanezt így is felírhatjuk:

${\displaystyle {\overline {p}}={\frac {\frac {365!}{(365-n)!}}{365^{n}}}={\frac {365!}{365^{n}(365-n)!}}}$.

Ez a klasszikus valószínűségi modellből jön ki. A tört számlálójába a „kedvező esetek” száma kerül, ami itt 365 elemnek (az év 365 napjának) n-ed osztályú ismétlés nélküli variációja, vagyis${\displaystyle V_{365}^{n}={\tfrac {365!}{(365-n)!}}}$, a nevezőbe pedig az összes lehetséges eset száma, ami a 365-nek n-ed osztályú ismétléses variációja, vagyis ${\displaystyle V_{365,i}^{n}=365^{n}}$.

Ezek után ${\displaystyle p=1-{\overline {p}}}$ annak a valószínűsége, hogy legalább két embernek egy napra esik a születésnapja. n = 22-re ez az érték kb. 0,4757, míg n = 23-ra kb. 0,5073. Tehát minimum 23 ember kell a teremben legyen ahhoz, hogy legalább 50%-os eséllyel legyen köztük kettő, aki ugyanazaon a napon született.

Ha az a kérdés, hogy milyen valószínűséggel van n-1 emberből legalább az egyiknek ugyanakkor a születésnapja, mint egy kiválasztott embernek, akkor a válasz (szintén komplementer eseménnyel és ismétléses variációval):

${\displaystyle 1-\left({\frac {364}{365}}\right)^{n-1}}$,

ami n = 23-ra mindössze kb. 0,0586. Ennek az eseménynek a valószínűsége csak akkor éri el az 50%-ot, amikor ${\displaystyle n\geq 254}$, tehát itt már tényleg nagyon sok emberre volna szükség. Ez – a születésnap-paradoxonnal ellentében – nem tűnik különösebben meghökkentőnek.

A születésnap-paradoxon általánosítva értelmezhető hash-függvényekre (hasítófüggvényekre) is: N-bites lenyomatokból (hashértékekből) valószínű ütközés nélkül sajnos nem 2^N, hanem csak kb. 2^N/2 generálható. Ezt használja ki az ún. születésnap-támadás különböző hashfüggvényeken alapuló titkosító algoritmusok ellen.

Így ír önéletrajzában Halmos Pál amerikai magyar matematikus:

„A probléma megközelítésének egyik módja, hogy megfordítva tesszük fel a kérdést: »Legalább hány embernek kell a szobában lennie ahhoz, hogy kevesebb, mint 1/2 valószínűséggel legyen csupa különböző születésnapjuk?« […] a probléma lényegében a következő: találjuk meg a legkisebb n-et, amire

${\displaystyle \prod _{k=0}^{n-1}\left(1-{\frac {k}{365}}\right)<{\frac {1}{2}}.}$

A szorzat felülről becsülhető a következőképpen:${\displaystyle \left({\frac {1}{n}}\sum _{k=0}^{n-1}\left(1-{\frac {k}{365}}\right)\right)^{n}<\left({\frac {1}{n}}\int _{0}^{n}\left(1-{\frac {x}{365}}\right)\,dx\right)^{n}=\left(1-{\frac {n}{730}}\right)^{n}<e^{-n^{2}/730}.}$

Az első felső becslés a mértani és a számtani közepek közötti összefüggésből következik. Ez ismét becsülhető a határozott integrál definícióját felhasználva, amelynek analitikus módon kiszámított értéke pedig ismét felülről becsülhető az 1 ‒ x < e^‒x összefüggést alapul véve. […] Az bizonyítás olyan fontos eszközöket használ fel, amellyel minden matematikát tanulónak illik elsajátítania. Csodálatos példája annak, hogy tisztán gondolkodással mennyi számítástól megkímélhetjük magunkat: az egyenlőtlenségek egy-két perc alatt felírhatók, míg a szorzatok kiszámítása lényegesen több időt venne igénybe, és a hibázás lehetősége is nagyobb lenne, akár papíron-ceruzával, akár számítógéppel végezzük. A számológép hasznos eszköz, de nem segít a probléma mélyebb megértésében, matematikai képességek elsajátításában, sem összetettebb, általánosabb elméletek megalkotásában.”

A fenti érvelésbe sajnos hiba csúszott, szerencsére nem végzetes. A

${\displaystyle \sum _{k=0}^{n-1}\left(1-{k \over 365}\right)<\int _{0}^{n}\left(1-{x \over 365}\right)\,dx}$

egyenlőtlenség ugyanis nem helytálló, amint az számítással egyszerűen ellenőrizhető (az egyenlőtlenség bal és jobb oldalának különbsége ${\displaystyle n/730}$, azaz pozitív). De az érvelés korrigálható. A

${\displaystyle \prod _{k=0}^{n-1}\left(1-{k \over 365}\right)}$

szorzatban az első tényező értéke 1, ezért elhagyható. Innen

${\displaystyle \prod _{k=1}^{n-1}\left(1-{k \over 365}\right)<\left({1 \over n-1}\sum _{k=1}^{n-1}\left(1-{k \over 365}\right)\right)^{n-1}}$

${\displaystyle =\left(1-{n \over 730}\right)^{n-1}<\left(e^{-n/730}\right)^{n-1}=e^{-(n^{2}-n)/730}.}$

ahol az első egyenlőtlenség ismét számtani és mértani közepek egyenlőtlensége, a második pedig az 1 ‒ x < e^‒x összefüggésből következik.

Az utolsó kifejezés értéke akkor és csak akkor kisebb ½-nél, ha

${\displaystyle n^{2}-n>730\ln 2\cong 505{,}997\dots }$

Ez többlettel 506-ra kerekíthető, amellyel az n² ‒ n kifejezés pontosan n = 23 esetén egyenlő.

A születésnap-paradoxon jól szimulálható számítógépes program segítségével. A következő parancs a Ruby programozási nyelv segítségét veszi igénybe:

 puts (1..30).collect {rand(365)+1}.uniq.length

ahol 30 az emberek száma, 365 pedig az egy évbe eső napok száma. Ha az eredmény (szintén egy szám) megegyezik az emberek számával (tehát ez esetben 30-cal), akkor mindenkinek más-más napon van a véletlenül sorsolt születésnapja. Ha kisebb, akkor voltak egyezések (méghozzá pontosan annyi, amennyi a különbség a kiírt és az eredeti szám között).

A következő kódrészlet Perl programozási nyelven íródott. Ez kilistázza azokat a számokat, amelyek a generált számsorban ismétlődnek.

 for (1..23) {$h{int(rand(365)+1)}++};
 for (keys %h) {print $_, ": ", $h{$_}, " times\n" if $h{$_} > 1}

• A paradoxon kísérleti igazolása (angolul)