Arkiajattelussa tieteellinen ymmärtäminen sidotaan helposti determinismiin ja yksinkertaisiin lakeihin. Kuitenkin tieteessä aivan yhtä tärkeää osaa annetaan myös sattumalle ja satunnaisuudelle sekä kompleksisuudelle. Todennäköisyyteen perustuvat arviot ovat aikamme tieteenteon tärkeitä välineitä. Luonnon ja eri ilmiöiden kuvauksissa aikaisempi varmuus on korvattu todennäköisyyksillä. Peruskäsitteissä on siis valtava ero. Normaali ihminen kokee sattuman epäymmärryksenä ja arvailuna. Tieteessä ne kuitenkin tarjoavat tietoa
Tässä jutussa lähestyn aihetta "hyvin tietyltä kantilta".
Tietojenkäsittelytieteessä kun tunnetaan käsite PRNG (pseudo-random number generator). Arkikielessä tässä kohden puhutaan satunnaislukujen generoimisesta. Asia on tärkeä, koska satunnaislukugeneraattoreita käytetään hyväksi esimerkiksi tietokonepeleissä, kun tuotetaan isoja alkulukuja salauksia varten. Tietotekniikassa satunnaisluvut ovat numeroita jotka asettuvat tietylle välille.
Ensin on hyvä miettiä kysymystä "Miten ohjelman satunnaisuuden voi tarkistaa?"
Matematiikassa sattuma ja laki ovat tavallaan toistensa vastinparit. Lainomaisille asioille, kuten suoran yhtälölle tai eksponentiaalisen kasvun kaavalle, on eksakti muoto. Satunnaisuus taas on tavallaan se jämä joka jää jäljelle kun kaikki lait on poistettu. Tämä tarkoittaa sitä että satunnaisluvuille ei ole olemassa mitään kaavaa. Satunnaisuutta joudutaan siksi arvioimaan tilastollisin menetelmin.
Jos kuvitellaan asiaa siten että arvotaan lukuja 1 ja 6 väliltä, kahden kanssa keskiarvo olisi useimmiten 7. Mutta ei aina. Kun lukuja otettaisiin 100, niiden keskiarvon pitäisi olla melko lähellä 7:ää. Sadan tuhannen luvun kanssa keskiarvon pitäisi olla vielä useammin ja vielä lähempänä seitsemää. Tämä ei kuitenkaan ole vielä kovin paljoa. Koska jos toistetaan vaikkapa lukuja 1 ja 6 aina vuoron perään, saadaan keskiarvoksi 7. Jono on kuitenkin kaikkea muuta kuin satunnainen. Siksi luvuilla täytyisi olla myös tasainen jakauma. Eli lukua 1 on yhtä monta kuin 2 ja 3 ja niin edespäin. Ja mitä pidempiä sarjoja tehdään, sitä vähäisempiä ja harvinaisempia erojen jakaumissa pitäisi olla. Tämäkään ei vielä riitä, koska voidaan toistaa jonoa 1,2,3,4,5,6 ja toistaa sitä peräkkäin. Tällöin keskiarvo on 7 ja numeroiden jakauma on tasainen, 1 on yhtä yleinen kuin vaikkapa 4. Jono ei kuitenkaan ole satunnainen. Siksi mukaan tulee myös riippumattomuus. Tämä tarkoittaa sitä että siitä että tiedetään että nyt on luku 1 ei voida sanoa mikä luku oli tätä ennen (ei mikä oli yhden tai mikä oli kymmenen numeroa sitten) tai jälkeen.
Jonon osoittaminen satunnaiseksi onkin hyvin vaikeaa. Voikin olla jokin järjestyksen vihje, joka kertoisi miten asia voitaisiin esittää tiiviimmin. Näin ollen satunnaisuutta tunnistaviin algoritmeihin liittyy erikoinen ominaisuus, joka selviää Ivars Petersonin "Satunnaisuuden viidakot" -kirjasta. Jos jokin satunnaislukujen tuottaja selviää satunnaistesteistä aina, se ei todennäköisesti ole aidosti satunnainen. Koska sattuman ideana on se, että mitä tahansa voi tapahtua, ja satunnaisuuden tunnistin antaa deterministisen vastauksen, kävisi ennen pitkää pakosti niin että joskus sattuma tuottaa jotain jonka ohjelma tunnistaa epäsatunnaiseksi. Ohjelmat siis ikään kuin tunnistavat lain puolelle "todennäköisyyden vuoksi", jolloin kyseessä ei ole satunnaisuuden todistaminen vaan satunnaisuuden arvio.
1: Näin ollen Algoritminen kompleksisuus on hämmentävä lähestymistapa esimerkiksi kasinossa. Siellä käy nimittäin helposti erikoisia. Kun satunnaisuus tunnistetaan merkkijonon kautta, se antaa "deterministisen vastauksen". Siksi käykin helposti niin että epätodennäköinen asia tunnistetaan lainomaiseksi, epäsatunnaiseksi. Sattuma kasinossa kun tuottaa joskus algoritmisesti matalasti kompleksisia tilanteita. Sattuma tuottaa niitä vain harvoin, mutta laki usein. Ongelmana on se, että sattuma tuottaa niitä kuitenkin joskus, niiden syntyminen ei ole mahdottomuus vaan pelkästään epätodennäköistä. Koska kasino yrittää simuloida sattumaa, olisi sen koneiden tulosten annettava tälläisiäkin tuloksia. Muutoin puuttuvia sarjoja voitaisiin käyttää voittotodennäköisyyksien parantamisessa, mikä taas painaisi kasinon kassavirrassa.
Tämän jälkeen siirrytään miettimään nörttimäisesti "Miten satunnaisuutta voi generoida?"
Karkeasti ottaen algoritmisen kompleksisuuden idea sitoutuu pakattavuuteen ja sen vaikeuksiin.
Jos jonkun pitkän numero tai merkkisarjan muistamiseen riittää pieni määrä ohjetta, se ei ole kovin mutkikas. Jos jono on niin epäjärjestyksessä, että mikään sen kirjoittava ohjelma ei ole itse jonoa lyhyempi, sitä pidetään satunnaisena. Näin ollen satunnainen tarkoittaa sitä että jonolla ei ole tiivistä kuvausta. Tähän liittyen Chaitin todisti, että mikään ohjelma ei voi tuottaa itseään kompleksisempaa lukua. Hän kuvasi löydöstä sanoin "Kilon teoria ei voi tuottaa kymmenen kilon teoreemaa sen enempää kuin raskaana oleva viisikymmentäkiloinen nainen ei voi synnyttää satakiloista vauvaa." Chaitin osoitti tilanteen toimivan myös toiseen suuntaan. Ohjelman on mahdotonta osoittaa että jokin ohjelmaa kompleksisempi luku on satunnainen ; Ei siis voida ottaa satunnaisuuden analysoivaa ohjelmaa ja liittää sitä lukuja läpikäyvään algoritmiin ja tulostaa ne sarjat jotka analysaattori tunnistaa kompleksisiksi. Satunnaisuutta saadaan korkeintaan sen verran mitä tällä "ohjelmakombolla" on pituutta. Tätä korkeampaa kompleksisuutta ei voida tarkistaa.
Näin ollen.
Käytännässä PRNG -nimessä olevat kirjaimet PR ovat tärkeät. Tietokoneet eivät arvo aitoa sattumaa vaan arpovat näennäissatunnaislukuja. Näin on pakko tehdä koska tietokoneet ovat deterministisiä koneita. Ne ovat algoritmeja, joilla on pituus.
Generaattorit perustuvat kaavaan johon liitetään jotenkin siemenluku. Tämän jälkeen generaattori näyttää eri luvun. PRNG:ssä sama siemenluku tuottaa aina saman luvun. Lisäksi siemenlukuun liittyy helposti lainomaisuuden mahdollisuus. Ja tavallaan asia menee niinkin että jos siemenluvun kykenee tuottamaan satunnaisesti, on ratkaisu satunnaislukujen saamiseenkin saatu, joten koko PRNG muuttuisi turhaksi. Lisäksi PRNG:illä on ominaisuus jonka mukaan ne tuottavat sarjoja jotka alkavat jossain vaiheessa toistamaan itseään.
1: Petteri Järvisen "Salausmenetelmät" -kirjan mukaan esimerkiksi yleisessä 32 -bittisessä järjestelmässä voi olla 232 erilaista sarjaa. Se on useampi kuin erilaisia lottorivejä. Sen sijaan korttipeleissä tilanne on ongelmallinen, koska 52! on suurempi kuin tuo. Tätä kautta normaalien tietokoneiden pokeriohjelmissa on aina ja väistämättä vain murto -osa erilaisista pakan järjestyksistä. Tämä mahdollistaa periaatteessa sen, että pelejä voidaan hallita kun huomataan että toiset järjestykset toistuvat ja toiset puuttuvat. Tilanne muuttuu vielä huonommaksi, jos siemenluku otetaan vaikkapa päivämäärästä ja kellonajasta, koska silloin siemenluvut ovat luonteeltaan tietynlaisia, eivätkä ne valikoidu kaikkien mahdollisten siemenlukujen joukosta. Tätä kautta satunnaisuuden taso voi olla mainittua pienempi.
Mielenkiintoinen asia onkin se, että satunnainen asia tuottaa helposti ja usein asioita jotka ovat algoritmeille vaikeita. Kuitenkin ero satunnaisen ja säännönmukaisuuden välillä ei ole helppoa tehdä. Algoritmisen kompleksisuuden kohdalla kysymys on siitä kuinka pitkä algoritmi tuottaa jonon, joten kysymys tavallaan tiivistyy siihen "miten monta bittiä pitkä ohjelma on liian pitkä ollakseen laki tai riittävä ollakseen riittävän umpimähkäinen".
Käytännössä joskus kysymys on syötteen pituudesta. Siitä voidaanko sitä pakata pienemmäksi, jolloin voidaan katsoa onko se umpimähkäinen vai ei. Joskus, esimerkiksi kasinoissa, taas kiinnostaa enemmän suurempi kokonaisuus.
Ei kommentteja:
Lähetä kommentti