Födelsedagsparadoxen

Paradoxen

Fråga folk hur många gäster ett kalas behöver innan två av dem troligen fyller år samma dag, så svarar de flesta ungefär 180, hälften av 365. Det rätta svaret är 23: då är sannolikheten 50,7 %. Med 57 gäster är den 99 %. Den kallas paradox, inte för att den är motsägelsefull, utan för att den går så starkt emot vår intuition.

Varför intuitionen sviker

I ett rum resonerar vi omedvetet utifrån oss själva: hur stor är sannolikheten att någon fyller år samma dag som jag? Med 365 dagar är den sannolikheten liten. Men paradoxen handlar om alla möjliga par i rummet, inte om en träff med en viss person: A och B, B och C, A och C och så vidare. Med 23 personer kan man bilda 253 olika par, och vart och ett av dem kan ha samma födelsedag.

Antalet par växer med kvadraten

n personer bildar n × (n − 1) / 2 par: 10 personer bildar 45 par, 23 bildar 253, 57 bildar 1 596 och 100 bildar 4 950. Varje par har samma födelsedag med sannolikheten 1/365, så 253 par ger i genomsnitt 253/365 ≈ 0,69 par med gemensam födelsedag. Om gruppen fördubblas blir paren ungefär fyra gånger så många, och därför skjuter sannolikheten för en gemensam födelsedag i höjden.

Uträkningen steg för steg

Det enklaste sättet är att räkna ut sannolikheten att ingen har samma födelsedag och dra bort den från 100 %. Den första personen tar vilken dag som helst. Den andra personen har sannolikheten 364/365 att inte ha samma födelsedag. Den tredje har sannolikheten 363/365 att skilja sig från de två första, och så vidare. För 23 personer:

365/365 × 364/365 × 363/365 × … × 343/365 ≈ 49,3 %

Eftersom sannolikheten att alla har olika födelsedagar är 49,3 % har motsatsen, minst en gemensam födelsedag, sannolikheten 100 % − 49,3 % = 50,7 %.

Någon med din födelsedag

Sannolikheten att någon har samma födelsedag som du är en annan fråga. Var och en av de andra n − 1 personerna missar din födelsedag med sannolikheten 364/365, så sannolikheten att någon har den är 1 − (364/365)ⁿ⁻¹. Med 23 personer är det bara 5,9 %, och det krävs 253 andra innan den passerar 50 %. Bara 22 av de 253 paren i en grupp på 23 innehåller dig.

Kvadratrotsregeln och födelsedagsattacker

För N lika sannolika värden blir en upprepning trolig efter ungefär 1,2 × √N dragningar: √365 ≈ 19, och 1,2 × 19 ≈ 23. Det spelar stor roll inom datasäkerhet. Angripare använder födelsedagsattacker för att hitta två indata med samma kryptografiska hashvärde, en kollision, till exempel för att förfalska en digital signatur. Tack vare födelsedagsparadoxen behöver de betydligt färre försök än intuitionen säger: ungefär 2⁶⁴ för en hashfunktion på 128 bitar i stället för 2¹²⁸. Därför har moderna hashfunktioner som SHA-256 långa utdata.

Utforska det i PictorX

Öppna Födelsedagsparadoxen, så bildar en grupp på 23 personer en cirkel, en person i taget. Varje nykomling drar en linje till alla som redan finns där, och bildtexten räknar paren. Deras födelsedagar faller ner i en kalender, och en dag med två eller fler lyser upp. Nedanför står uträkningen för gruppstorleken bredvid andelen testade grupper som hade en gemensam födelsedag, och diagrammet visar sannolikheten för varje gruppstorlek, både för två godtyckliga personer och för någon med din födelsedag. Lägg till personer en i taget, välj 2 till 366 personer, testa upp till 100 000 grupper med upp till 10 000 i sekunden, eller testa alla gruppstorlekar och se punkterna rita kurvan.