Simulator til fødselsdagsparadokset | Hvorfor 23 personer er nok til 50 %

Sådan virker det

Klik på scenen for en ny gruppe på 23 personer. De kommer til én ad gangen, og der tegnes en linje for hvert nyt par.
Hold øje med kalenderen: En dag med to fødselsdage lyser op, og beskeden nævner den fælles fødselsdag.
Tryk på Test automatisk for 1.000 grupper, eller på Test alle gruppestørrelser for at se sandsynligheden stige fra 2 til 100 personer.

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, cirka 6 % med 22 andre. Men paradokset spørger, om to vilkårlige personer har samme fødselsdag: A og B, B og C, A og C og så videre. Treogtyve personer danner 23 × 22 / 2 = 253 par, og hvert eneste af dem er en chance for et sammenfald. Antallet af par vokser med kvadratet på gruppens størrelse, så sandsynligheden skyder i vejret.

Udregningen

Det er nemmest at regne sandsynligheden for, at ingen har samme fødselsdag, ud og trække den fra 100 %. Den første person tager en vilkårlig dag. Den anden har sandsynligheden 364/365 for en anden dag, den tredje sandsynligheden 363/365 for at undgå de to første og så videre. For 23 personer: 365/365 × 364/365 × 363/365 × … × 343/365 ≈ 49,3 %. Sandsynligheden for mindst én fælles fødselsdag er så 100 % − 49,3 % = 50,7 %.

Nogen med din fødselsdag

Sandsynligheden for, at nogen i gruppen har samme fødselsdag som dig, vokser meget langsommere: 1 − (364/365)ⁿ⁻¹, fordi kun n − 1 af parrene omfatter dig. Med 23 personer er den 5,9 %, og du skal have 253 andre for at komme over 50 %. Skift spørgsmålet til Nogen har samme fødselsdag som dig for at sammenligne de to kurver.

Fødselsdagsangreb i kryptografi

Paradokset er mere end et festtrick. Inden for it-sikkerhed er det grundlaget for fødselsdagsangrebet: For at finde to input med samme hashværdi, en kollision, skal en angriber bruge langt færre forsøg, end man skulle tro. For en hashfunktion med N mulige værdier bliver en kollision sandsynlig efter cirka √N forsøg i stedet for N. Derfor skal hashværdier og digitale signaturer være så lange, at selv √N forsøg er uden for rækkevidde: For en hashfunktion på 128 bit kræver en kollision omkring 2⁶⁴ forsøg.

Ofte stillede spørgsmål

Hvor mange personer skal der til for at få 50 % chance for en fælles fødselsdag?

23. Så er sandsynligheden 50,7 %. Med 30 personer er den 70,6 %, med 41 personer 90,3 %, med 57 personer 99,0 % og med 70 personer 99,9 %.

Hvorfor kaldes det et paradoks?

Det er ikke en modsigelse, kun en overraskelse: Svaret går imod intuitionen. De fleste gætter på, at man skal bruge omkring halvdelen af 365, cirka 180 personer, fordi de sammenligner alle med sig selv i stedet for med hinanden.

Hvad med den 29. februar og virkelige fødselsdatoer?

Appen regner, ligesom det klassiske problem, med 365 lige sandsynlige dage. Virkelige fødselsdage er ikke helt jævnt fordelt over året, og en ujævn fordeling gør en fælles fødselsdag lidt mere sandsynlig, ikke mindre.

Hvornår er en fælles fødselsdag sikker?

Med 366 personer: Der er kun 365 dage, så ifølge skuffeprincippet må mindst to af 366 personer have samme fødselsdag. Længe inden da er det praktisk talt sikkert: Med 100 personer er sandsynligheden 99,99997 %.

Bliver der uploadet noget?

Nej. Alt beregnes og tegnes på et lærred i din browser. Gem henter et PNG. Rediger åbner billedet i PictorX-editoren.