keskiviikko 22. maaliskuuta 2017

Satunnaislukujen perusteet

Juonenkäänteet ovat kirjaimellisesti satunnaisia.

RAND Corporationin vuoden 1955 hittiteos A Million Random Digits with 100,000 Normal Deviates.
(Michael Sauers/Flickr. CC-BY-NC 2.0.)

Kiitos kaikille satunnaisuuskyselyyn vastanneille! Nyt minulla on edessä erittäin kiinnostava numeronmurskausoperaatio, ja sen tuloksiin pääsemme perjantaina. Sitä odotellessa on hyvä perehtyä siihen, mitä satunnaisuus oikeasti on.

Ensimmäiseksi meidän pitää määritellä satunnaisuus. Sen jälkeen tutustumme tapaan, jolla tietokoneet muodostavat arkisia satunnaislukuja. Lopuksi perehdytään todelliseen satunnaisuuteen. Ehdotan lisäksi paria tapaa mahdollisimman satunnaisten lukujen keksimiseen itse.

Mitä on satunnaisuus?

Jos satunnaisuudelle pitäisi valita synonyymi, sanoisin "ennalta-arvaamattomuus". Jos satunnaisia lukuja laitetaan jonoksi, seuraavaa termiä ei saa pystyä ennustamaan aiempien perusteella. Arvaamisen täytyy olla paras tapa "ennustaa" seuraava luku. Tästä seuraa myös se, että jokaisen halutulla välillä olevan luvun on oltava yhtä todennäköinen — muutenhan kannattaisi aina veikata yleisintä lukua!

Satunnaisluvuilla on paljon käyttökohteita. Kevyemmässä päässä ne toimivat erilaisten pelien ja simulaatioiden taustalla: minkä sienen alla lymyilee mörrimöykky, hyökkääkö asiakas liha- vai maitohyllylle? Vakavammassa päässä niistä jopa riippuu henkiä. Salakirjoitusavainten (ks. Julkisia salaisuuksia) täytyy olla satunnaisia, eikä niitä saa pystyä ennustamaan. Lottoarvonnassa jokaisen pelin on oltava ennalta-arvaamaton, sitä vaatii lakikin.

Näiden perusteella annan kolme ehtoa hyvälle satunnaislukujen luomismenetelmälle:

  1. Jokainen luku on yhtä todennäköinen.
  2. Edellisistä luvuista ei voi ennustaa seuraavaa lukua.
  3. Jono ei saa alkaa toistamaan itseään.

Tarkastellaan nyt muutamaa tapaa luoda satunnaisia lukuja. Sitä varten tarvitsemme satunnaislukugeneraattorin, laitteen joka tuottaa satunnaislukuja halutulla välillä. Meidän tapauksessamme se on harmaa boksi, jossa on yhden numeron (0–9) näyttöruutu ja nappi uuden numeron luomiseen. Muuttelemme ainoastaan boksin sisällä olevaa mekanismia.

Kuva satunnaislukuboksista.

(Saatavilla hyvinvarustelluista rautakaupoista.)

Kokeillaan ensimmäiseksi kaikkein yksinkertaisinta tapaa: laatikon sisällä on rulla, jossa on kaikki numerot nollasta yhdeksään. Napin painaminen pyöräyttää rullaa askeleen eteenpäin.

\[ 0,1,2,3,4,5,6,7,8,9,0,1,\dots \]

Lienee ilmiselvää, että nämä eivät ole satunnaislukuja nähneetkään. Ensimmäinen ehto kyllä täyttyy: mikään numero ei ole muita todennäköisempi. Toisaalta kuvion havaitseminen ei ole kovin vaikeaa...

Tietokoneet astuvat lavalle

Kun tietokoneet tulivat todellisuudeksi 40-luvulla, simulointi oli yksi ensimmäisistä kohteista, joihin niiden raakaa laskuvoimaa sovellettiin. Jotta erilaisia skenaarioita voitaisiin simuloida, tarvittiin luotettava satunnaislukujen lähde, jollaisia ei vielä ollut kehitetty. Alan legenda John von Neumann esitti seuraavan menetelmän:

Ota nelinumeroinen luku ja neliöi se, jotta saat kahdeksannumeroisen luvun. Keskimmäiset neljä numeroa ovat vastaus ja seuraava lähtöarvo.

Esimerkiksi kun lähtöarvo on $1~234$, niin $1~234^2 = 01~522~756$ ja vastaus on $5~227$. Tämän neliö on $27~321~529$, joten seuraava luku on $3215$ ja niin edelleen.

Menetelmä toimii yllättävän hyvin, mutta siinä on kriittinen vika: se jumittuu hyvin helposti pieniin sykleihin — varsinkin, jos luvuksi osuu $0$. Toinen ehto paukkuu pahasti, kun lyhyet syklit tunnetaan. Lisäksi meidän numeromaattimme on vaikeuksissa: mikäli se näyttäisi luvun viimeisen numeron, osa numeroista olisi huomattavasti muita todennäköisempiä. Niin, ja enintään nelinumeroisia lukuja on vain 10000 kappaletta, joten lukujono ei todellakaan ole äärettömän pitkä.

Von Neumannia ei haitannut, että hänen menetelmänsä oli kehno. Hän tiedosti, että pelkästään lukuja pyörittelemällä ei voi luoda mitään oikeasti satunnaista. Itse asiassa hänestä oli hyvä asia, että menetelmä meni metsään ilmeisellä tavalla eikä salakavalasti!

Tietokoneet tykkäävät rajatun kokoisista luvuista, ja rajatun kokoisia lukuja on, yllätys yllätys, rajattu määrä. Yksikään tietokone ei voi täyttää ehtoa 3, vaan lukujonon on pakko joskus alkaa alusta. Ongelmana onkin kehittää tapa, jolla kaksi ensimmäistä ehtoa toteutuvat.

Kellotauluratkaisu

Lukuteorian ehkä kiinnostavin juttu on kongruenssi eli kellotaululaskenta. Pikakertauksena se perustuu siihen, että luvut "pyörähtävät ympäri" tietyn pisteen jälkeen kuten kellotaululla tai klassisessa matkamittarissa. Kellotaululle mainittu kohta on 12, matkamittarille vaikkapa miljoona kilometriä.

Seuraava menetelmä käy läpi kaikki kellotaulun luvut satunnaisessa järjestyksessä, mutta alkaa sitten toistaa itseään. Se ei ole ongelma, kun kellotaulu on paljon laajempi kuin haluttu lukualue. Meidän yhden numeron laitteemme voisi käyttää vaikkapa kellotaulua, jonka koko on 1000. Vakiot täytyy valita sopivalla tavalla[1], ja kaavaksi saadaan esimerkiksi

\[ X = 771Y + 23 \mod 1000, \]

jossa $Y$ on edellinen luku. Jos aloitetaan luvulla $Y=1$, ensimmäinen $X = 771 \cdot 1 + 23 = 794$. Seuraava luku on $771 \cdot 794 + 23 = 612~197$, jonka jakojäännös tuhannella jaettaessa on $197$. Tätä jatkuu, kunnes ollaan taas luvussa $1$.

Tämä menetelmä toimii itse asiassa kohtalaisen hyvin. Jokainen viimeinen numero on yhtä todennäköinen, ja vain viimeisiä numeroita tarkastelemalla on vaikea päätellä seuraavaa lukua. Meidän satunnaisboksimme voisi siis hyvinkin käyttää tätä menetelmää. En salakirjoittaisi sillä yhtään mitään tai perustaisi kasinoa sen pohjalle, mutta muihin peleihin ja simulaatioihin se olisi riittävä. Todellisessa toteutuksessa kellotaulu sovitaan niin isoksi kuin tietokoneelle sopii, jotta toistoa ei tapahtuisi käytännössä koskaan.

Syvemmässä tarkastelussa tässäkin menetelmässä ilmenee ongelmia, mutta yleiseen käyttöön parempia tekniikoita ilmestyi vasta 90-luvun lopulla. Paremmatkaan tekniikat eivät kelpaa aivan tiukan täydelliseen satunnaisuuteen, kuten von Neumann totesi. Kaikkiin nykyisiin tarpeisiin ne ovat kuitenkin riittävän luotettavia.

Mistä saadaan todellista satunnaisuutta?

Jos erilaiset laskukaavat eivät kelpaa, satunnaisuutta kannattaa etsiä mittaamalla. Yksi tapa on virittää radio tyhjälle taajuudelle ja nauhoittaa kohinaa. Kohina riippuu niin monesta tekijästä (muut radioasemat, säätila, ohiajavat autot, ympäristön pienet säteilymäärät jne.), että sitä on käytännössä mahdotonta ennustaa. Kun sen muuttaa luvuiksi ja muokkaa tasaisesti jakautuneeksi, kaikki ehdot täyttyvät. Fysiikan laeista seuraa, että kohinaa ei voi ennustaa täydellisesti.

Mistä sitten löytää omaan tarpeeseen satunnaislukuja? Mikäli käytössäsi on nettiyhteys, Random.org tarjoaa ilmakehäkohinaa useassa kätevässä muodossa. Monesta laskimesta (myös puhelimissa) löytyy toiminto satunnaislukujen luomiseen.

Joidenkin lukujen desimaalit ovat nykytietämyksellä täysin sattumanvaraisia. Mikäli sinulla on uskomaton muisti tai lunttilappu, $\pi$ tai $e$ ovat hyviä valintoja. Varsinkin ensimmäistä on käytetty hyvänä satunnaislukujen lähteenä. Esimerkiksi vanhemmasta MAOL-taulukoiden versiosta löytyy tuhat desimaalia juurikin siihen tarkoitukseen (tai maailmankaikkeusmittaluokan hienomekaniikkaan).

Jos yksi pienehkö luku riittää, oma tapani on vilkaista kellon minuuttiviisaria ja laskea jakojäännös vaihtoehtojen määrällä jaettaessa. Esimerkiksi jos pitää valita kolmesta vaihtoehdosta ja kello on 12.42, lasken $42 = 3 \cdot 13 + 0$ ja valitsen nollannen eli ensimmäisen vaihtoehdon. Tämä tosin vaatii hieman päässälaskuharrastusta!

Tietenkään ei sovi unohtaa klassista nopan tai kolikon heittoa. Miten ikinä luvut valitsetkaan, saat luultavasti parempia tuloksia kuin keksimällä "satunnaisia" lukuja. Ihmiset kun eivät ole kovin satunnaisia, mutta se on ensi kerran juttu...

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.