De verjaardagsparadox: waarom 23 mensen genoeg zijn voor een treffer

Bij het WK van 2014 checkten journalisten alle 32 selecties. Elke selectie had precies 23 spelers, en in 16 van de 32, de helft dus, hadden minstens twee spelers dezelfde verjaardag. Niemand had dat geregeld. Het is simpelweg wat het getal 23 doet.

Dat is de verjaardagsparadox: in een kamer met 23 mensen is een gedeelde verjaardag waarschijnlijker dan niet. Er zijn 365 mogelijke verjaardagen en maar 23 mensen, de bewering klinkt dus absurd, en die reactie is bijna universeel. Maar het resultaat is geen truc, geen statistische illusie, en hangt niet van kleine lettertjes af. Het is een kort telargument, en zodra je ziet welke telling de intuïtie in plaats van de juiste uitvoert, lost de paradox op tot iets dat bijna vanzelfsprekend is.

De bewering, zorgvuldig geformuleerd

Neem 23 mensen van wie de verjaardagen onafhankelijk zijn en met gelijke kans op elk van de 365 dagen vallen, 29 februari laten we voorlopig weg. De bewering luidt:

De kans dat minstens twee van hen op dezelfde dag jarig zijn is 50.7%, iets beter dan een muntworp.

Twee details doen ertoe. Ten eerste gaat het erom dat willekeurig welke twee mensen overeenkomen, niet om het treffen van één bepaalde persoon. Ten tweede betekent "gedeelde verjaardag" dezelfde dag in het jaar, bijvoorbeeld 14 maart, niet dezelfde dag én hetzelfde jaar. Beide details klinken bijkomstig. Een ervan is, zoals we zullen zien, de hele paradox.

Het bewijs is gewoon tellen

De directe vraag, hoe groot de kans is dat iemand iemand treft, is lastig frontaal aan te vallen, omdat treffers op veel overlappende manieren kunnen ontstaan. De kansrekening heeft daar een standaardzet voor: bereken de kans dat er niets gebeurt, en trek die van 1 af. Waarom die zet mag, legt van de grond af waarschijnlijkheid intuïtief begrijpen uit.

Dat is het hele bewijs: tel de paren om te zien waarom een treffer aannemelijk is, vermenigvuldig daarna 23 breuken om te zien hoe aannemelijk precies. Geen zware machinerie, niets dat je op geloof moet aannemen. Elke stap is met een rekenmachine te controleren.

En de curve klimt snel verder. Bij 30 mensen is de trefferkans 70.6%. Bij 50 mensen 97.0%. Bij 70 mensen 99.9%: een gedeelde verjaardag is zo goed als gegarandeerd, terwijl 295 dagen van het jaar nog onaangeroerd zijn.

Waar de intuïtie misgaat

De verjaardagsparadox fopt mensen betrouwbaar, en ze fopt hen op één specifieke, diagnoseerbare manier: ze beantwoorden de verkeerde vraag.

Hoor de puzzel, en je hoofd vervangt hem stilletjes door een versie met jou in de hoofdrol. Wat is de kans dat iemand hier mijn verjaardag treft? Die vraag heeft écht een klein antwoord. In een kamer met 23 zijn er maar 22 anderen, elk treft jou met kans $1/365$, en de totale kans dat iemand jou treft ligt rond de 6%. Ging de puzzel over jouw verjaardag, dan hadden de sceptici gelijk.

Maar de puzzel gaat over willekeurig welke treffer. Jij tegen elk van de anderen: 22 paren. Maar ook persoon 2 tegen persoon 3, persoon 7 tegen persoon 19, en elke andere combinatie waar jij helemaal niet in zit: 231 extra paren, in totaal 253. Intuïtie telt de 22 vergelijkingen die ze van binnenuit kan zien, en is structureel blind voor de 231 waar ze geen deel van uitmaakt. De paradox is niet dat kansrekening zich vreemd gedraagt. Het is dat een kamer met 23 mensen elf keer meer vergelijkingen bevat dan één persoon ervaart.

Er is een nette manier om te zien hoe groot dat gat is. Voor 50% kans dat iemand juist jou treft, zijn 22 anderen bij lange na niet genoeg: je hebt 253 mensen naast jezelf nodig. Het aantal anderen dat je nodig hebt om één vaste verjaardag te treffen is hetzelfde als het aantal paren onder 23 mensen. Dat is geen toeval, het zijn de twee vragen die door dezelfde rekenkunde worden opgelost, en het meet precies hoezeer het kader "mijn verjaardag" de situatie onderschat.

De kleine lettertjes die het antwoord eerlijk maken

De berekening nam 365 even waarschijnlijke verjaardagen aan en geen schrikkeldag. Beide aannames zijn in de echte wereld onjuist, dus het is redelijk te vragen of de 50.7% het contact met de realiteit overleeft.

Dat doet ze, en de realiteit helpt zelfs. 29 februari als zeldzame 366e dag toevoegen duwt de kans een haartje omlaag, veel te weinig om de drempel van 23 af te bewegen. Ongelijk verdeelde verjaardagen duwen de andere kant op: echte geboortegegevens tonen seizoenspieken, bepaalde maanden zijn betrouwbaar voller dan andere. Elke zulke ongelijkheid maakt botsingen waarschijnlijker, want kans op populaire dagen bundelen is precies waar botsingen van leven. Het gelijkverdeelde model is de hardst denkbare setting voor de paradox, en het haalt de 50% toch.

Bij die robuustheid loont het om even stil te staan, want het is het tegenovergestelde van hoe paradoxachtige puzzels zich meestal gedragen. Het Monty Hall-probleem bijvoorbeeld is berucht gevoelig voor zijn kleine lettertjes: verander wat de presentator weet, en het antwoord verandert. De verjaardagsparadox is het stevige broertje. Elke realistische afwijking van de leerboek-aannames duwt de kans omhoog, de verrassing overleeft dus elke haarkloverij.

Van feesttruc tot het kraken van hashfuncties

De verjaardagsparadox zou haar plaats verdienen als feestweddenschap, maar ze heeft ook een serieus beroep. In de cryptografie bepaalt ze de prijs van het vinden van botsingen, en een hele aanvalsstrategie is ernaar genoemd.

Een hashfunctie perst elke invoer samen tot een vingerafdruk van vaste grootte, en beveiliging hangt er vaak van af dat niemand twee verschillende invoeren met dezelfde vingerafdruk vindt. Stel dat de vingerafdrukken 128 bits zijn, dan zijn er 2 tot de macht 128 mogelijkheden, een astronomisch groot getal. Een invoer raden die één specifieke vingerafdruk raakt kost inderdaad in de orde van 2 tot de macht 128 pogingen, hopeloos voor altijd. Maar een aanvaller die gewoon een of andere botsing wil, twee willekeurige invoeren die overeenkomen, speelt het verjaardagsspel: genereer willekeurige invoeren, en volgens de wortelregel is een botsing te verwachten na grofweg 2 tot de macht 64 pogingen. Dat is de birthday-aanval, en 2 tot de 64 is een groot getal maar geen veilig getal; vastberaden aanvallers hebben het overschreden.

De paradox, met andere woorden, halveert de effectieve sterkte van een hash, gemeten in bits. Daarom gebruiken cryptografen die 128 bits botsingsweerstand willen hashes met 256-bits uitvoer: de wortel van 2 tot de 256 is 2 tot de 128, waardoor zelfs de verjaardagsafkorting buiten bereik blijft. Een patroon dat bepaalt hoeveel mensen je op een feest uitnodigt, bepaalt ook hoeveel bits je bankverbinding beschermen, en het is beide keren dezelfde berekening.

Probeer het, want het kost niets

Net als de beste kansresultaten is dit goedkoop te testen. Elke groep van ongeveer 25 mensen werkt: een klas, een kantoorverdieping, een teamlijst, een gastenlijst van een bruiloft. Vraag ieders verjaardag en kijk naar de treffer. Eén groep bewijst uiteraard niets, de ene of de andere kant op. De bewering is 50.7%, geen zekerheid, dus de weddenschap verliest bijna de helft van de keren.

De overtuigende versie is herhaling. Sportselecties zijn hiervoor ideaal, daarom blijft het WK in artikelen over de verjaardagsparadox opduiken: selecties van 23 zijn het experiment op precies de drempelgrootte, vooraf samengesteld en openbaar. Check tien selecties en je mag treffers in ongeveer vijf verwachten. Of simuleer het: een paar regels code die 23 willekeurige getallen van 1 tot 365 toewijzen en op herhalingen controleren, tienduizend keer gedraaid, landen binnen een fractie van een procent van 0.507. Het argument met 23 breuken doet een precieze voorspelling, de wereld blijft ermee instemmen, en er zijn weinig snellere manieren om kansrekening voelbaar echt te laten worden.

De zen ervan

De verjaardagsparadox blijft hangen omdat het een perfecte miniatuur is van een algemeen faalpatroon. Intuïtie beoordeelt situaties vanuit één gezichtspunt, het jouwe, en in combinatorische situaties zit dat ene gezichtspunt er een factor naast die met de menigte meegroeit. Er is niets mis met toeval. De fout zit volledig in welke vraag stilletjes wordt beantwoord.

En het middel is hetzelfde als altijd in de kansrekening: weiger te gokken, en tel. Tel de paren en de aannemelijkheid verschijnt. Vermenigvuldig de breuken en het exacte getal valt eruit. Dezelfde telling duikt daarna onveranderd op in het ontwerp van cryptografische systemen, en dat is de stille les van het hele onderwerp: een kansargument weet niet of het voor een caféweddenschap of voor de beveiliging van het internet wordt gebruikt.

Drieëntwintig mensen. Tweehonderddrieënvijftig kansen. De kamer was nooit zo leeg als hij eruitzag.