Ala-asteen luokkakaverillani oli sama syntymäpäivä kuin minulla. Olet luultavasti itsekin ollut samankaltaisessa tilanteessa: jollain tuttavallasi on yhteinen syntymäpäivä sinun tai muun tutun kanssa. Aika lailla joka toisessa koululuokassa on tällainen pari.
Kyyhkyslakkaperiaate
Tätä ilmiötä, syntymäpäiväparadoksia, käytetään usein esimerkkinä todennäköisyyksien epäintuitiivisesta puolesta. Arkijärjellä ajattelisi oikein, että yhden kaverin todennäköisyys samaan syntymäpäivään on $$\frac{1}{365}$$ (anteeksi karkauspäivänä syntyneet — jätän teidät nyt huomiotta yksinkertaisuuden vuoksi!). Edelleen oikein olisi ajatella, että varmasti näin tapahtuu vasta, kun tutkitaan 366 ihmistä.
Jälkimmäistä tapausta kutsutaan kyyhkyslakkaperiaatteeksi: jos on 366 kyyhkystä ja 365 pesäkoloa, on väistämättä ainakin yksi kolo, jossa on kaksi kyyhkystä. Termi tunnetaan englanniksi nimellä pigeonhole principle. Sanalla viitattiin samannimiseen paperien säilytyslaatikkoon, mutta sittemmin kirjaimellinen tulkinta on tullut suositummaksi. Muun muassa ranskankielinen termi säilyttää alkuperäisen merkityksen.
Virhe tapahtuu, kun porukan koko on jotain siltä väliltä. Intuitiivisesti voisi ajatella vaikkapa, että 20 ihmisessä olisi tällainen pari $$\frac{20 - 1}{365}$$ todennäköisyydellä (miinus yksi siksi, että jokaisella on sama syntymäpäivä kuin itsellään). Tämä ei kuitenkaan ota huomioon, että 20 ihmisestä voi muodostaa $$20 \cdot 19 \cdot \frac{1}{2}$$ paria, eikä synttärikolmikon mahdollisuutta, eikä oikein mitään muutakaan.
Käännetään tilanne
Sen sijaan ajatellaan päinvastaista tilannetta: kenelläkään joukosta ei ole sama syntymäpäivä kuin toisella. Katsotaan ihmisiä yksi kerrallaan: ensimmäisellä on 365 vaihtoehtoa syntymäpäiväksi, toisella 364 vaihtoehtoa ja niin edelleen. Tästä saadaan laskettua todennäköisyys sille, ettei yhteisiä juhlapäiviä löydy:
\[ \frac{365}{365} \cdot \frac{364}{365} \cdot \frac{363}{365} \cdot \dots \]
Koska varman asian todennäköisyys on 1, ja "yhteiset kemut on tai sitten niitä ei ole" on ilmeisen varma juttu, saadaan yhteisen syntymäpäivän todennäköisyydeksi $1 - \text{P(ei yhteisiä syntymäpäiviä)}$.
Tästä voidaan laskea, että jo 23 hengen ryhmässä on 50 % todennäköisyys yhteiseen syntymäpäivään. 32 hengen kesken todennäköisyys on jo 75 prosenttia. Synttärikolarit ovatkin yleisempiä kuin heti arvaisi!
Tällä tuloksella on yllättävän paljon vaikutuksia tietojenkäsittelytieteen piirissä. Salasanojen turvalliseen tallentamiseen käytetään menetelmää, joka tiivistää salasanan yhdeksi vakiomittaiseksi luvuksi, josta ei voi johtaa alkuperäistä salasanaa. Koska salasana voi olla pidempi kuin luku, useampi salasana pakkautuu kyyhkyslakkaperiaatteen mukaan samaksi luvuksi. Syntymäpäivien tavoin "törmäyksen" todennäköisyys on varsin suuri.
Koska mahdollisia tiivisteitä on paljon, kahden törmäävän salasanan löytäminen on kuitenkin erittäin vaikeaa. Vuosien varrella on silti poistettu käytöstä algoritmeja, joilla tiivistetyistä salasanoista törmäys olisi löydettävissä realistisessa ajassa tietokoneiden nopeutuessa.
Ei kommentteja:
Lähetä kommentti
Kommentit ovat moderoituja — yritän hyväksyä kommenttisi mahdollisimman pian. Voit kirjoittaa kommenttiin LaTeX-koodia tai yksinkertaista HTML-merkintää: lue lisää Kommentointi-sivulta.