23 personer. I et rom på bare 23 personer er det 50-50 sjanse for at minst to personer har samme bursdag. I et rom på 75 er det 99,9% sjanse for at minst to personer stemmer overens.
Legg ned kalkulatoren og høygaffelen, jeg snakker ikke kjetteri. Bursdagsparadokset er rart, kontraintuitivt og helt sant. Det er bare et «paradoks» fordi hjernen vår ikke kan håndtere eksponenters sammensatte kraft. Vi forventer at sannsynlighetene er lineære og bare vurderer scenariene vi er involvert i (begge feilaktige antagelser, forresten).
La oss se hvorfor paradokset skjer og hvordan det fungerer.
Oppgave 1: Eksponenter er ikke intuitive
Vi har lært oss selv matematikk og statistikk, men la oss ikke unge oss selv: det er ikke naturlig.
Her er et eksempel: Hva er sjansen for å få 10 hoder på rad når du vender mynter? Den utrente hjernen tror kanskje slik:
«Vel, å få ett hode er 50% sjanse. Å få to hoder er dobbelt så vanskelig, så en sjanse på 25%. Å få ti hoder er sannsynligvis ti ganger vanskeligere … så omtrent 50% / 10 eller en sjanse på 5%. ”
Og der sitter vi, selvtilfreds som en feil på et teppe. Ingen terningbobler.
Men selv etter trening blir vi fanget igjen. Med 5% rente vil vi doble pengene våre i løpet av 14 år, snarere enn den «forventede» 20. Trodde du naturlig nok Regelen på 72 når du lærte om renter? Sannsynligvis ikke. Å forstå sammensatt eksponentiell vekst med våre lineære hjerner er vanskelig.
Oppgave 2: Mennesker er litt egoistiske
Ta en titt på nyhetene. Legg merke til hvor mye av de negative nyhetene er resultatet av å handle uten å vurdere andre. Jeg er en optimist og har håp for menneskeheten, men det er en egen diskusjon :).
I et rom på 23, tenker du på de 22 sammenligningene der bursdagen din blir sammenlignet med andres? Sannsynligvis.
Tenker du på de 231 sammenligningene der noen som ikke er deg blir sjekket mot noen andre som ikke er deg? Er du klar over at det er så mange? Sannsynligvis ikke.
Det faktum at vi forsømmer de ti ganger så mange sammenligninger som ikke inkluderer oss, hjelper oss å forstå hvorfor «paradokset» kan skje.
Ok, greit, mennesker er forferdelige: Vis meg matematikken!
q spørsmålet: Hva er sjansene for at to personer deler bursdag i en gruppe på 23?
Visst, vi kan liste opp parene og telle alle måtene de kan matche. Men det er vanskelig: det kan være 1, 2, 3 eller til og med 23 kamper!
Det er som å spørre «Hva er sjansen for å få ett eller flere hoder i 23 myntslipp?» Det er så mange muligheter: hoder på første kast, eller tredje, eller det siste, eller 1. og 3., 2. og 21. osv.
Hvordan løser vi myntproblemet? Vend det rundt (Få det? Få det?). I stedet for å telle hver vei for å få hoder, finn sjansen for å få alle haler, vårt «problemscenario».
Hvis det er 1% sjanse for å få alle haler (mer som .5 ^ 23 men jobber med meg her), det er 99% sjanse for å ha minst ett hode. Jeg vet ikke om det er 1 hode eller 2 eller 15 eller 23: vi har hoder, og det er det som betyr noe. Hvis vi trekker sjansen for et problemscenario fra 1, sitter vi igjen med sannsynligheten for et godt scenario.
Det samme prinsippet gjelder for bursdager. I stedet for å finne alle måtene vi samsvarer med, finn sjansen for at alle er forskjellige, «problemscenariet». Vi tar deretter motsatt sannsynlighet og får sjansen for en kamp. Det kan være 1 kamp, eller 2 eller 20, men noen matchet, noe som vi trenger å finne.
Forklaring: Counting Pairs (Approximate Formula)
Med 23 personer har vi 253 par:
(Pensle på kombinasjoner og permutasjoner hvis du vil).
Sjansen for at to personer har forskjellige bursdager er:
Fornuftig, ikke sant? Når man sammenligner en persons bursdag med en annen, vant de ikke 364 av 365 scenarier. .
Men å gjøre 253 sammenligninger og ha dem alle forskjellige er som å få hoder 253 ganger på rad – du måtte unngå «haler» hver gang. La oss få en omtrentlig løsning ved å late som bursdagssammenligning er som myntklipp. (Se vedlegg A for nøyaktig beregning.)
Vi bruker eksponenter for å finne sannsynligheten:
Sjansen vår for å få en eneste glipp er ganske høy (99,7260%), men når du tar sjansen hundrevis av ganger, faller sjansen for å holde den strikken oppe. Rask.
Sjansen for at vi finner en kamp er: 1 – 49,95% = 50,05%, eller litt over halvparten! Hvis du vil finne sannsynligheten for en kamp for et hvilket som helst antall personer, er formelen:
Interaktivt eksempel
Jeg trodde ikke vi trengte bare 23 personer. Matematikken ordner seg, men er den ekte?
Du satser.Prøv eksemplet nedenfor: Velg et antall ting (365), et antall personer (23) og kjør noen få prøveversjoner. Du ser den teoretiske kampen og den faktiske kampen din når du kjører prøveperioden. Fortsett, klikk på knappen (eller se hele siden).
Etter hvert som du kjører flere og flere forsøk (fortsett å klikke!), Bør den faktiske sannsynligheten nærme seg den teoretiske.
Eksempler og takeaways
Her er noen leksjoner fra bursdagsparadokset:
- $ \ sqrt {n} $ er omtrent det antallet du trenger for å ha 50% sjanse for matche med n gjenstander. $ \ sqrt {365} $ er omtrent 20. Dette spiller inn i kryptografi for bursdagsangrepet.
- Selv om det er 2128 (1e38) GUID-er, har vi bare 264 (1e19) å bruke før 50% sjanse for kollisjon. Og 50% er veldig, veldig høyt.
- Du trenger bare 13 personer som velger bokstaver i alfabetet for å ha 95% sjanse for en kamp. Prøv det over (personer = 13, gjenstander = 26).
- Eksponensiell vekst reduserer raskt sjansen for å plukke unike gjenstander (det øker sjansene for en kamp). Husk: eksponenter er ikke-intuitive og mennesker er egoistiske!
Etter å ha tenkt mye på det, klikker endelig bursdagsparadokset med meg. Men jeg sjekker fortsatt det interaktive eksemplet bare for å være sikker.
Vedlegg A: Gjentatt multiplikasjonsforklaring (eksakt formel)
Husker du hvordan vi antok bursdager er uavhengige? Det er de ikke.
Hvis person A og person B samsvarer, og person B og C samsvarer, vet vi at A og C også må matche. Resultatet av å matche A og C avhenger av resultatene med B, så sannsynlighetene er ikke uavhengige. (Hvis A og C virkelig er uavhengige, vil A og C ha 1/365 sjanse til å matche, men vi vet at det er en 100% garantert kamp.)
Når vi teller par, behandlet vi bursdagskamper som myntklipp, multiplisert den samme sannsynligheten om og om igjen. Denne antagelsen er ikke helt sant, men den er god nok for et lite antall mennesker (23) sammenlignet med utvalgsstørrelsen (365). Det er usannsynlig at flere personer stemmer overens og ødelegger uavhengigheten, så det er en god tilnærming.
Det er usannsynlig, men det kan skje. La oss finne ut de virkelige sjansene for at hver person velger et annet tall:
Multiplikasjonen ser ganske stygg ut:
Men det er en snarvei vi kan ta. Når x er nær 0, blir en grov førsteordens Taylor-tilnærming for $ e ^ x $ er:
så
Ved hjelp av vår praktiske snarvei kan vi omskrive den store ligningen til:
Å legge til 1 til 22 er (22 * 23) / 2 så vi får:
Phew. Denne tilnærmingen er veldig nær, plugg inn dine egne tall nedenfor:
Bra nok for myndighetsarbeid, som de sier. Hvis du forenkler formelen litt og bytter i n mot 23, får du:
og
Vedlegg B: Den generelle bursdagsformelen
La oss generalisere formelen til å plukke n personer fra T totalt antall elementer (i stedet for 365) :
Hvis vi velger en sannsynlighet (som 50% sjanse for en kamp) og løser for n:
Voila! Hvis du tar $ \ sqrt {T} $ varer (17% mer hvis du vil være kresen), har du omtrent 50-50 sjanse for å få en kamp. Hvis du plugger inn andre tall, kan du løse andre sannsynligheter:
Husk at m er ønsket sjanse for en kamp ( det er lett å bli forvirret, jeg gjorde det selv). Hvis du vil ha 90% sjanse for å matche bursdager, plugger du m = 90% og T = 365 inn i ligningen og ser at du trenger 41 personer.
Wikipedia har enda flere detaljer for å tilfredsstille din indre nerd. Gå videre og nyt.
Andre innlegg i denne serien
- En kort introduksjon til sannsynlighet & Statistikk
- En intuitiv (og kort) forklaring på Bayes «teorem
- Forstå Bayes teorem med forhold
- Forstå Monty Hall-problemet
- Hvordan analysere data ved hjelp av Gjennomsnitt
- Forstå bursdagsparadokset