Fødselsdagsparadokset

Paradokset

Spørg folk, hvor mange gæster der skal til en fest, før to af dem sandsynligvis har fødselsdag samme dag, og de fleste vil sige omkring 180, halvdelen af 365. Det rigtige svar er 23: Så er sandsynligheden 50,7 %. Med 57 gæster er den 99 %. Det kaldes et paradoks, ikke fordi det er selvmodsigende, men fordi det strider så stærkt mod vores intuition.

Hvorfor intuitionen svigter

I et rum ræsonnerer vi ubevidst ud fra os selv: Hvad er sandsynligheden for, at nogen har samme fødselsdag som mig? Med 365 dage er den sandsynlighed lille. Men paradokset handler om alle mulige par i rummet, ikke om et sammenfald med én bestemt person: A og B, B og C, A og C og så videre. Med 23 personer kan man danne 253 forskellige par, og hvert af dem kan have samme fødselsdag.

Antallet af par vokser med kvadratet

n personer danner n × (n − 1) / 2 par: 10 personer danner 45 par, 23 danner 253, 57 danner 1.596, og 100 danner 4.950. Hvert par har samme fødselsdag med sandsynligheden 1/365, så 253 par giver i gennemsnit 253/365 ≈ 0,69 par med fælles fødselsdag. Fordobler man gruppen, bliver der cirka fire gange så mange par, og derfor skyder sandsynligheden for en fælles fødselsdag i vejret.

Udregningen trin for trin

Den nemmeste vej er at regne sandsynligheden for, at ingen har samme fødselsdag, ud og trække den fra 100 %. Den første person lægger beslag på en vilkårlig dag. Den anden person har sandsynligheden 364/365 for ikke at have samme fødselsdag. Den tredje har sandsynligheden 363/365 for at adskille sig fra de to første og så videre. For 23 personer:

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

Da sandsynligheden for, at alle har forskellig fødselsdag, er 49,3 %, har det modsatte, mindst én fælles fødselsdag, sandsynligheden 100 % − 49,3 % = 50,7 %.

Nogen med din fødselsdag

Sandsynligheden for, at nogen har samme fødselsdag som dig, er et andet spørgsmål. Hver af de andre n − 1 personer rammer forbi din fødselsdag med sandsynligheden 364/365, så sandsynligheden for, at nogen har den, er 1 − (364/365)ⁿ⁻¹. Med 23 personer er det kun 5,9 %, og du skal have 253 andre, før den kommer over 50 %. Kun 22 af de 253 par i en gruppe på 23 omfatter dig.

Kvadratrodsreglen og fødselsdagsangreb

For N lige sandsynlige værdier bliver en gentagelse sandsynlig efter cirka 1,2 × √N trækninger: √365 ≈ 19, og 1,2 × 19 ≈ 23. Det har stor betydning inden for it-sikkerhed. Angribere bruger fødselsdagsangreb til at finde to input med samme kryptografiske hashværdi, en kollision, for eksempel for at forfalske en digital signatur. Takket være fødselsdagsparadokset skal de bruge langt færre forsøg, end intuitionen siger: omkring 2⁶⁴ for en hashfunktion på 128 bit i stedet for 2¹²⁸. Derfor har moderne hashfunktioner som SHA-256 lange output.

Udforsk det i PictorX

Åbn Fødselsdagsparadokset, så dannes en gruppe på 23 personer i en cirkel, én person ad gangen. Hver nykommer trækker en linje til alle, der allerede er der, og billedteksten tæller parrene. Deres fødselsdage falder ned i en kalender, og en dag med to eller flere lyser op. Nedenunder står udregningen for gruppestørrelsen ved siden af andelen af testede grupper med en fælles fødselsdag, og diagrammet viser sandsynligheden for hver gruppestørrelse, både for to vilkårlige personer og for nogen med din fødselsdag. Tilføj personer én ad gangen, vælg 2 til 366 personer, test op til 100.000 grupper med op til 10.000 i sekundet, eller test alle gruppestørrelser, og se punkterne tegne kurven.