Simulointi 7-puolisen nopan simulointi 5-puolisesta nopasta

A.S.: Jep, ilmeisesti ’nopan’ yksikkö on ’die’. 😉

Internetissä on liikkunut hankala ohjelmointitehtävä, joka, kuten olet saattanut arvata yrittämästäni pragmaattisesta otsikosta, voidaan formalisoida seuraavasti:

Suoritetaan funktio, joka palauttaa yhdenmukaisesti satunnaisen luvun väliltä 1-5 (mukaan lukien), suunnittele funktio, joka palauttaa yhdenmukaisesti satunnaisen luvun väliltä 1-7 (mukaan lukien).

Jos algoritmien ja tilastotieteen leikkauspiste on sinun juttusi, kokeile rohkeasti! Lisähaasteena on tehdä algoritmistasi ajallisesti rajattu. Huomasin tämän olevan hauska harjoitus, vain tajutakseni, että tässä on perustavanlaatuisia rajoituksia.

Tietysti kuutio tarkoittaa tässä täydellisen tasaista satunnaisgeneraattoria, joka on olemassa vain teoriassa. Reaalimaailman noppia säätelevät luonnonlait ja ympäristön epätäydellisyydet niin, että ne ovat vain approksimaatio (vaikkakin hyvä) tästä abstraktista mallista.

Rajaton ratkaisu

Katsotaanpa rajaton algoritmien perhe. Luodaksemme satunnaisgeneraattorin, jolla on vähintään 7 lopputulosta, meidän on heitettävä viisisivuista noppaa vähintään kaksi kertaa. Kahdesti heittämällä saadaan 5^2=25 mahdollista tulosta, ja vaikka tämä ei ole 7:n kerroin, voimme jakaa ensimmäiset 21 tulosta seitsemään yhtä suureen ryhmään, joiden koko on 3. Jos päädymme kuitenkin johonkin jäljellä olevista neljästä tuloksesta, menettely on aloitettava uudelleen. Emme voi yksinkertaisesti määrittää mitä tahansa näistä neljästä epäonnisesta lopputilanteesta jollekin ulostulolle, sillä tämä sotkee tasaisen satunnaisuuden ominaisuuden.

Yllä olevassa kaaviossa ympyrät edustavat ohjelmamme ”tiloja”, ja niiden sisällä oleva teksti on heittokuution viimeisin arvo. Vihreät laatikot edustavat sitten tulostetta, jonka annamme riippuen lopputilasta (= sen jälkeen, kun olemme heittäneet noppaa kahdesti). 84 % ajasta saamme tuloksen kahden heiton jälkeen ja algoritmi päättyy. Kuten näet, silmukka on läsnä ja tekee algoritmista rajoittamattoman. Tämä tarkoittaa, että jokaisella kokonaisluvulla, olipa se kuinka suuri tahansa, on pieni mutta nollasta poikkeava todennäköisyys sille, että heittojen kokonaismäärä ylittää kyseisen määrän yhden lähtöarvon laskemiseksi. Reaaliaikaiset sovellukset, joilla on tiukat aikavaatimukset, eivät siis tule kysymykseen, ellet ole valmis tekemään kompromisseja algoritmin tilastollisen tarkkuuden suhteen.

Tämän ratkaisun muunnos heittää aluksi enintään kolme noppaa ennen uudelleenkäynnistystä: tämä luo 5^3=125 lopputilaa, ja voimme määrittää niistä korkeintaan 119 seitsemään yhtä suureen ryhmään 17. Nyt on 95,2 % todennäköisyys lopettaa enintään kolmen heiton jälkeen. Huomaa, että joudumme heittämään keskimäärin vähemmän kertoja kuin aiemmin (280/119 ≈ 2,35 vs. 50/21 ≈ 2,38), koska useimmiten voimme jo kahden ensimmäisen heiton jälkeen oikotietä ja liittää nämä välitilat suoraan tulokseen. Tämä keskimääräinen heittomäärä laskee koko ajan, kun jatkamme trendiä.

Jos olet perehtynyt informaatioteoriaan, niin mieti, että yksi heitto viisisivuisella nopalla (= rand5) tuottaa log2(5) ≈ 2,32 bittiä informaatiota, ja yksi heitto seitsenpuolisella nopalla (= rand7) tuottaa log2(7) ≈ 2,81 bittiä informaatiota. Osoittautuu, että rajatapauksessa tarvitsemme vain log(7)/log(5) ≈ 1,21 rand5-kutsua jokaista rand7-arvoa kohden, jonka haluamme saada. Tarkka toteutus, joka toimii mielivaltaisesti lähellä tätä raja-arvoa, on melko monimutkainen ja tämän artikkelin soveltamisalan ulkopuolella. Meidän olisi tallennettava tilatietoa useiden rand7-kutsujen välissä, ja mieleeni tuleva algoritmi on edelleen rajoittamaton paitsi ajallisesti myös muistin suhteen. Pyydän teitä mielelläni ilmoittamaan minulle menetelmän, joka ratkaisee tämän jälkimmäisen ongelman!

Rajoitettu ratkaisu

Ei ole olemassa rajattua algoritmia, joka laskee täydellisen yhdenmukaisen satunnaisarvon väliltä 1 ja 7, kun satunnaisgeneraattorille annetaan vain väliltä 1 ja 5. Tarkastellaan yllä olevaa rajoittamattomien ratkaisujen perhettä. Kuten olen vihjannut, jokaisessa pisteessä on aina tietty määrä ”jäljelle jääviä” tiloja (jotka vaihtelevat välillä 1-6), jotka aiheuttavat algoritmin uudelleenkäynnistyksen. Tämä johtuu siitä, että 5 ja 7 ovat alkulukuja, eikä mikään 5:n potenssi voi koskaan olla 7:n kerrannainen. Vaikka olisi kuinka houkuttelevaa käyttää Fermat’n pientä teoreemaa, tällaiset yritykset johtavat off-by-one-virheisiin, koska peruslukuteoria tekee rajoitetun ratkaisun tässä perheessä mahdottomaksi.

Voit oikeutetusti huomauttaa, että lopputilojen määrä ei ole aina potenssi 5:stä, esimerkiksi tapauksessa ”enintään kolme heittoa”, jossa voimme oikaista jo kahden heiton jälkeen. Ehkä voisimme järjestää tilakaavion niin, että syntyy rajattu algoritmi, jossa on vaihtelevan pituisia polkuja ja 7n lopputilaa? Mieti kuitenkin seuraavaa:

1. Nämä lopputilat eivät ole yhtä todennäköisiä, koska kaikki polut eivät ole yhtä pitkiä (= rand5-kutsujen määrä).
2. Voisimme hyvin helposti laajentaa puun niin, että jokaisesta polusta tulee yhtä pitkä, kutsumalla rand5:tä turhaan sopivan monta kertaa aina kun olemme ennenaikaisessa lopputilassa. Nyt lopputilojen määrästä tulee taas 5:n potenssi, ja kaikki lopputilat ovat yhtä todennäköisiä.

Tämä ei tietenkään ole muodollinen todiste, mutta toivon antaneeni sinulle jonkinlaisen intuition ongelmasta. Kuten näemme, joskus ongelma voi tuntua hyvin realistiselta, kunnes sitten törmää tällaisiin matemaattisiin tosiasioihin. Pystytkö tämän analyysin jälkeen keksimään, onko mahdollista simuloida 8-puolista noppaa alkaen 4-puolisesta nopasta?