Födelsedagsparadoxen: varför 23 personer räcker för en träff

Vid VM 2014 kollade journalister alla 32 trupper. Varje trupp hade exakt 23 spelare, och i 16 av de 32, alltså hälften, hade minst två spelare samma födelsedag. Ingen hade arrangerat det. Det är helt enkelt vad talet 23 gör.

Det är födelsedagsparadoxen: i ett rum med 23 personer är en delad födelsedag mer sannolik än inte. Det finns 365 möjliga födelsedagar och bara 23 personer, så påståendet låter absurt, och den reaktionen är nästan universell. Men resultatet är inget trick, ingen statistisk illusion, och hänger inte på finstilt. Det är ett kort räknande argument, och när du ser vilken räkning intuitionen gör i stället för den rätta, löses paradoxen upp till något som nästan är uppenbart.

Påståendet, formulerat noggrant

Ta 23 personer vars födelsedagar är oberoende och lika sannolika att falla på vilken som helst av 365 dagar, 29 februari lämnar vi åt sidan för tillfället. Påståendet är:

Sannolikheten att minst två av dem har samma födelsedag är 50.7%, något bättre än ett myntkast.

Två detaljer spelar roll. För det första handlar det om att vilka två personer som helst stämmer överens, inte om att träffa en viss person. För det andra betyder "delad födelsedag" samma dag på året, till exempel 14 mars, inte samma dag och år. Båda detaljerna låter små. En av dem är, som vi ska se, hela paradoxen.

Beviset är bara räkning

Den direkta frågan, hur stor sannolikheten är att någon träffar någon, är besvärlig att attackera rakt på, för träffar kan uppstå på många överlappande sätt. Sannolikhetsläran har ett standarddrag för det: räkna ut sannolikheten att ingenting händer, och dra av den från 1. En genomgång från grunden av varför det draget är tillåtet finns i förstå sannolikhet intuitivt.

Det är hela beviset: räkna paren för att se varför en träff är rimlig, multiplicera sedan 23 bråk för att se exakt hur rimlig. Ingen avancerad maskineri, ingenting att ta på tro. Varje steg går att kolla med en kalkylator.

Och kurvan klättrar snabbt vidare. Vid 30 personer är träffsannolikheten 70.6%. Vid 50 personer 97.0%. Vid 70 personer 99.9%: en delad födelsedag är så gott som garanterad, medan 295 dagar på året fortfarande är orörda.

Där intuitionen går fel

Födelsedagsparadoxen lurar människor pålitligt, och den lurar dem på ett specifikt, diagnostiserbart sätt: de svarar på fel fråga.

Hör pusslet, och huvudet byter tyst ut det mot en version med dig i huvudrollen. Vad är oddsen att någon här träffar min födelsedag? Den frågan har verkligen ett litet svar. I ett rum med 23 finns bara 22 andra, var och en träffar dig med sannolikhet $1/365$, och den totala sannolikheten att någon träffar dig ligger runt 6%. Handlade pusslet om din födelsedag skulle skeptikerna ha rätt.

Men pusslet handlar om vilken träff som helst. Du mot var och en av de andra: 22 par. Men också person 2 mot person 3, person 7 mot person 19, och varje annan kombination som inte involverar dig alls: 231 par till, totalt 253. Intuitionen räknar de 22 jämförelser den kan se inifrån och är strukturellt blind för de 231 den inte ingår i. Paradoxen är inte att sannolikhet beter sig konstigt. Den är att ett rum med 23 personer innehåller elva gånger fler jämförelser än någon enskild person upplever.

Det finns ett snyggt sätt att se hur stort det gapet är. För 50% chans att någon träffar just dig räcker 22 andra inte på långa vägar: du behöver 253 personer utöver dig själv. Antalet andra som behövs för att träffa en fast födelsedag är samma som antalet par bland 23 personer. Det är ingen slump, det är de två frågorna som löses av samma aritmetik, och det mäter precis hur mycket inramningen "min födelsedag" underskattar läget.

Det finstilta som gör svaret ärligt

Kalkylen antog 365 lika sannolika födelsedagar och ingen skottdag. Båda antagandena är falska i verkligheten, så det är rimligt att fråga om 50.7% överlever mötet med världen.

Det gör den, och verkligheten hjälper till och med. Att lägga till 29 februari som en sällsynt 366:e dag knuffar sannolikheten en aning nedåt, långt för lite för att flytta tröskeln från 23. Ojämna födelsedagar knuffar åt andra hållet: riktiga födelsedata visar säsongstoppar, vissa månader är pålitligt mer fulla än andra. All sådan ojämnhet gör krockar mer sannolika, för att bunta sannolikhet på populära dagar är precis vad krockar livnär sig på. Den jämna modellen är den hårdast tänkbara miljön för paradoxen, och den klarar 50% ändå.

Den robustheten är värd en paus, för den är motsatsen till hur paradoxdoftande pussel brukar bete sig. Monty Hall-problemet till exempel är ökänt känsligt för sitt finstilta: ändra vad programledaren vet, och svaret ändras. Födelsedagsparadoxen är det stadiga syskonet. Varje realistisk avvikelse från läroboksantagandena knuffar sannolikheten uppåt, så överraskningen överlever varje hårklyveri.

Från partytrick till att knäcka hashfunktioner

Födelsedagsparadoxen skulle förtjäna sin plats som ett partyvad, men den har också ett seriöst jobb. I kryptografi sätter den priset på att hitta krockar, och en hel attackstrategi är uppkallad efter den.

En hashfunktion klämmer ihop valfri indata till ett fingeravtryck av fast storlek, och säkerhet beror ofta på att ingen hittar två olika indata med samma fingeravtryck. Anta att fingeravtrycken är 128 bitar, då finns det 2 upphöjt till 128 möjligheter, ett astronomiskt stort tal. Att gissa en indata som träffar ett visst fingeravtryck tar verkligen i storleksordningen 2 upphöjt till 128 försök, hopplöst för alltid. Men en angripare som bara vill ha någon krock, vilka två indata som helst som stämmer, spelar födelsedagsspelet: generera slumpmässiga indata, och enligt kvadratrotsregeln väntas en krock efter ungefär 2 upphöjt till 64 försök. Det är birthday-attacken, och 2 till 64 är ett stort tal men inte ett säkert; beslutsamma angripare har passerat det.

Paradoxen, med andra ord, halverar den effektiva styrkan hos en hash, mätt i bitar. Därför använder kryptografer som vill ha 128 bitars krockmotstånd hashar med 256-bitars utdata: kvadratroten av 2 till 256 är 2 till 128, vilket sätter även födelsedagsgenvägen utom räckhåll. Ett mönster som avgör hur många du bjuder till ett kalas avgör också hur många bitar som skyddar din bankuppkoppling, och det är samma kalkyl båda gångerna.

Testa det, för det kostar ingenting

Som de bästa sannolikhetsresultaten är det här billigt att testa. Vilken grupp på ungefär 25 personer som helst fungerar: ett klassrum, ett kontorsplan, en trupplista, en bröllopsgästlista. Fråga allas födelsedag och se efter träffen. En enda grupp bevisar förstås ingenting åt något håll. Påståendet är 50.7%, inte säkerhet, så vadet förlorar nästan hälften av gångerna.

Den övertygande versionen är upprepning. Idrottstrupper är ideala för det, vilket är varför VM dyker upp i artiklar om födelsedagsparadoxen: trupper på 23 är experimentet på exakt tröskelstorleken, färdigställda och offentliga. Kolla tio trupper och du bör vänta dig träffar i ungefär fem. Eller simulera: några rader kod som tilldelar 23 slumptal från 1 till 365 och letar efter upprepningar, körda tiotusen gånger, landar inom en bråkdel av en procent från 0.507. Argumentet med 23 bråk gör en precis prediktion, världen fortsätter att hålla med, och det finns få snabbare sätt att känna hur sannolikhet blir verklig.

Zenen i det

Födelsedagsparadoxen består för att den är en perfekt miniatyr av ett allmänt felsätt. Intuition utvärderar situationer från en enda synvinkel, din, och i kombinatoriska situationer ligger den enda synvinkeln fel med en faktor som växer med folksamlingen. Inget med slump missköter sig. Felet sitter helt i vilken fråga som tyst besvaras.

Och botemedlet är detsamma som alltid i sannolikhet: vägra gissa, och räkna. Räkna paren och rimligheten syns. Multiplicera bråken och det exakta talet ramlar ut. Samma räkning dyker sedan upp oförändrad i konstruktionen av kryptosystem, och det är den tysta lärdomen i hela ämnet: ett sannolikhetsargument vet inte om det används för ett barvad eller för att säkra internet.

Tjugotre personer. Tvåhundrafemtiotre chanser. Rummet var aldrig så tomt som det såg ut.