See on masintõlge; originaalartikkel on inglise keeles. Loe originaali
Kaksümmend kolm inimest ja kokkulangevus, mida tuleks oodata
Kaksümmend kolm inimest moodustavad 253 paari. Keegi ei arvuta kunagi arvu 253 ja see ongi ainus põhjus, miks vastus tundub vale.
Kui asetada ruumi 23 inimest, on tõenäosus, et kahel neist on sama sünnipäev, 50,7%. 70 inimese korral on see 99,9%.
Peaaegu kõik pakuvad liiga suure arvu ja põhjus seisneb selles, et küsitakse vale küsimus. Intinktiivselt mõeldakse iseendast: milline on tõenäosus, et kellelgi siin on sama sünnipäev mis minu oma? See on palju harvem sündmus ja selleks, et see ületaks poole piiri, oleks vaja umbes 253 inimest.
Tegelik küsimus puudutab aga suvalist inimpaari. Ja paaridest ei ole puudust.
Paaride, mitte inimeste loendamine
Kaksümmend kolm inimest moodustavad 23 × 22 ÷ 2 = 253 eraldiseisvat paari. Igal paaril on 1 võimalus 365-st kattuda. Paaride arv kasvab inimeste arvu ruuduga, seega ruumis viibijate arvu kahekordistamine neljakordistab kokkulangevuse võimalusi.
Täpne arvutus käib vastupidises suunas — tõenäosus, et mitte kahelgi inimesel ei lange sünnipäev kokku, mis on 23 teguri puhul 365/365 × 364/365 × 363/365 × …, andes tulemuseks 0,493. Üks miinus see tulemus on 0,507.
Mäletamist vääriv üldreegel
Kui võimalusi on N võrdtõenäolist, on enne kordumise muutumist tõenäolisemaks kui mitte vaja umbes √N tõmbamist. Sünnipäevade puhul on √365 ≈ 19 ja konstant tuleb umbes 1,18 × √N ≈ 22,5. Piisavalt lähedal arvule 23.
Ruutjuur, mitte pool. Just selles arvus inimesed eksivad, ning seda suunas, mis paneb ootama kokkulangevuste harvemat esinemist kui need tegelikult on.
Kus see lakkab olemast lihtsalt peotrikk
Räsikollisioonid. Tuhande pesaga räsitabelis ei hakka kollisioonid tekkima alles tuhande kirje lähedale jõudmisel. Need hakkavad tekkima umbes kolmekümne juures. Seetõttu hoolitsevad räsitabelite teostused kollisioonide haldamise eest juba päris esimesest sisestamisest alates ning seetõttu ütleb pelgalt täiteteguri mõõtmine vähe selle kohta, mitut kontrolli otsing vajab. Tööriist Hash Table näitab, et kollisioonid ilmuvad palju varem kui oodatud.
Krüptograafia. Siin määrabki ruutjuur turvaparameetri. Kahe sama 64-bitise räsiga erineva dokumendi leidmiseks ei ole vaja 2⁶⁴ katset; vaja on umbes 2³² — ligikaudu neli miljardit, mis on mõne minuti töö. See on sünnipäevarünnak ning seepärast peab räsifunktsioon, mis on mõeldud pakkuma n bitikohalist kollisioonikindlust, andma väljundiks 2n bitti. See on põhjus, miks 128-bitiseid räsisid peetakse pakkuvaks 64 bitti kollisioonikindlust ega loeta allkirjastamiseks enam vastuvõetavaks.
Kokkulangevuste tõlgendamine. Iga piisavalt suur andmestik sisaldab silmatorkavaid kokkulangevusi ning nende arv skaleerub paaride, mitte kirjete arvuga. Kaks linnaelanikku, kes võidavad loteriil, haigusjuhtude kobar ühel tänaval, kaks sarnaselt kõlavat laulu: suure skaala korral muutuvad need peaaegu paratamatuseks ning igaühe käsitlemine eraldiseisvalt ebatõenäolisena on sama aritmeetiline eksimus, mida tehakse inimeste ja sünnipäevade puhul.
Õige küsimus ei ole kunagi "kui ebatõenäoline on see konkreetne kokkulangevus?". See on "kui palju oli võimalusi mõne sellist tüüpi kokkulangevuse tekkeks?". Need kaks arvu erinevad kordaja võrra, mis kasvab ruutvõrdeliselt, ning sellest piisab enam kui küllalt, et muuta hämmastus ootuspärasuseks.
Kaks vastuväidet, millele mõlemale tasub vastata
"Sünnipäevad ei ole ühtlaselt jaotunud." Ei ole tõesti — põhjapoolkeral on rohkem sünde hilissuvel, vähem 25. detsembril ja 29. veebruaril ning nädalavahetustel on esilekutsutud sünnituste tõttu märgatav langus. Kuid ebaühtlus muudab kattumised alati tõenäolisemaks, mitte kunagi vähem tõenäoliseks: koondumine koondab inimesed vähematele efektiivsetele päevadele. Seetõttu on ühtlase jaotuse eeldus konservatiivne ning 23 on pigem kerge ülehinnang.
"Kaksikud ja koos tulnud inimesed." Tegelikud ruumid ei ole juhuslikud valimid. Ruumis, kus viibivad õed-vennad või vanuselise piirmäära järgi valitud kooliklass, esineb korrelatsioone, mida mudel ei arvesta. Arvutus on algtasemeks sõltumatute katsete puhul ning seal, kus katsed ei ole sõltumatud, vajab kaitsmist just sõltumatus, mitte aritmeetika.
Meelespidamist vääriv versioon
Kui on N võrdtõenäolist kategooriat ja tehakse k tõmbamist, on kollisiooniga paaride eeldatav arv umbes k²/2N. Seades selle võrdseks ühega, saadakse k ≈ √(2N) — see sama ruutjuur, mis saadakse tõenäosuste asemel eeldatavate kollisioonide loendamise teel ja mida on peast lihtsam arvutada.
Tuhande räsi pesa puhul: √2000 ≈ 45, seega oodake esimest kollisiooni kuskil neljakümnetes. 32-bitise kontrollsumma puhul: 2¹⁶ = 65,536 elementi, mille logifail saavutab ühe pärastlõunaga. 365 päeva puhul: 27, mis on piisavalt lähedal arvule 23, et hinnangut tasub usaldada.
Harjumuseks peaks saama ruutjuure poole pöördumine alati, kui kuulete küsimust "kui suur on duplikaadi tõenäosus", ning märkmine, et vastus saabub palju varem, kui ruumi suurus eeldaks. Tööriist Birthday Paradox kujutab seda kõverat ning selle järsus umbes 20 kuni 30 inimese juures on see osa, mida ei anna sõnadega edasi anda.