Ohjelmoinnin alkeet

Luku 15: Satunnaisuus

Kun yhdistämme tietokoneen tehokkuuden ja satunnaisuuden, voimme tutkia satunnaisia ilmiöitä ohjelmoinnin avulla. Ideana on simuloida tietokoneella ilmiötä monta kertaa ja kerätä tietoa sen käyttäytymisestä.

Satunnaisluvut

Pythonissa satunnaisuuteen liittyvät työkalut ovat kirjastossa random, joka täytyy ottaa mukaan ohjelman alussa. Usein tarvittava funktio on randint(a,b), joka antaa satunnaisen kokonaisluvun väliltä a...b. Esimerkiksi seuraava ohjelma heittää noppaa arpomalla muuttujaan x satunnaisluvun väliltä 1...6:

from random import *

x = randint(1,6)
print(x)

Aina kun suoritamme tämän ohjelman, se tulostaa jonkin luvun väliltä 1...6. Esimerkiksi jos suoritamme ohjelman kolmesti, se saattaa tulostaa seuraavat luvut:

2

6

5

Nyt meillä on siis käytössämme tapa tuottaa satunnaisia lukuja niin paljon kuin tarvitsemme.

Simulaation toteutus

Tarkastellaan seuraavaksi koetta, jossa heitämme noppaa, kunnes olemme saaneet jokaisen silmäluvun ainakin kerran. Haluamme arvioida, montako kertaa noppaa täytyy heittää keskimäärin, ennen kuin kaikki silmäluvut ovat esiintyneet. Toisin sanoen haluamme laskea, mikä on tarvittavien heittojen määrän odotusarvo.

Esimerkiksi yksi mahdollinen heittosarja on [5,4,3,3,6,1,1,5,6,5,2], joka muodostuu 11 heitosta. Tässä tapauksessa saimme muut silmäluvut melko nopeasti, mutta jouduimme heittämään vielä monta kertaa, ennen kuin saimme puuttuvan silmäluvun 2.

On selvää, että pienin mahdollinen heittosarjan pituus on 6, jos meillä käy todella hyvä tuuri ja jokainen heitto antaa eri silmäluvun. Toisaalta voisi kuvitella, että 100 heiton jälkeen jokainen silmäluku on esiintynyt lähes varmasti. Mutta mikä mahtaa olla keskimäärin tarvittava heittojen määrä?

Voimme tutkia tarvittavaa heittojen määrää tietokoneella toteuttamalla simulaation. Seuraava koodi heittää noppaa, kunnes kaikki silmäluvut ovat esiintyneet:

from random import *

heitot = []
puuttuvat = 6

while puuttuvat > 0:
    x = randint(1,6)
    if x not in heitot:
        puuttuvat -= 1
    heitot.append(x)
print(heitot)
print(len(heitot))

Koodi luo listan heitot, johon tallennetaan heittosarja, sekä muuttujan puuttuvat, jossa on puuttuvien silmälukujen määrä (aluksi 6). Silmukassa koodi heittää noppaa ja vähentää muuttujan puuttuvat arvoa yhdellä, jos tulee silmäluku, jota ei ole saatu aiemmin. Sitten koodi lisää silmäluvun heittosarjaan. Silmukka jatkuu niin kauan, kuin on ainakin yksi puuttuva silmäluku. Lopuksi koodi tulostaa heittosarjan ja sen pituuden.

Voimme nyt kokeeksi suorittaa koodin muutamia kertoja, jolloin se saattaa antaa vaikkapa seuraavat tulokset:

[4, 3, 5, 1, 4, 3, 5, 3, 5, 5, 3, 3, 1, 2, 6]
15

[5, 3, 6, 5, 4, 5, 2, 1]
8

[5, 3, 5, 4, 6, 3, 3, 5, 5, 3, 5, 5, 6, 2, 2, 4, 6, 1]
18

Tässä ensimmäisellä kerralla jouduimme heittämään noppaa 15 kertaa, toisella kerralla 8 kertaa ja kolmannella kerralla 18 kertaa.

Simulaation toistaminen

Jotta saamme hyvän kuvan ilmiöstä, yksittäiset simulaatiot eivät kuitenkaan riitä, vaan meidän täytyy toistaa simulaatiota suuri määrä kertoja ja laskea keskiarvo tuloksista. Tämä onnistuu kätevästi tekemällä silmukka, joka toistaa simulaatiota n kertaa. Seuraava ohjelma toteuttaa tämän:

from random import *

n = 100
s = 0

for i in range(n):
    heitot = []
    puuttuvat = 6
    while puuttuvat > 0:
        x = randint(1,6)
        if x not in heitot:
            puuttuvat -= 1
        heitot.append(x)
    s += len(heitot)

print(s/n)

Ohjelman alussa n määrittää, montako kertaa simulaatio toistetaan (tässä 100 kertaa), ja s on kaikkien tulosten summa. Sitten ohjelma toistaa simulaation n kertaa ja laskee lopuksi keskimääräisen heittojen määrän jakamalla tulosten summan n:llä.

Nyt voimme vain suorittaa ohjelman ja saada arvion tarvittavien heittojen määrästä. Pystymme vaikuttamaan arvion tarkkuuteen muuttamalla n:n arvoa. Seuraava taulukko näyttää tuloksia joillakin arvoilla:

toistokerrat (n)	heittojen määrän arvio (s/n)
10	12.6
100	14.61
1000	14.41
10000	14.6266
100000	14.70495

Vaikuttaa siis siltä, että meidän täytyy heittää keskimäärin 14–15 kertaa, ennen kuin olemme saaneet jokaisen silmäluvun ainakin kerran.

Mitä suurempi n on, sitä luottavaisempia voimme olla, että arvio on lähellä totuutta. Toisaalta mitä suurempi n on, sitä kauemmin ohjelman suoritus kestää. Meidän täytyy siis löytää sopiva tasapaino sen suhteen, miten tarkan tuloksen haluamme ja kauanko olemme valmiita odottamaan.

Entä kuinka kaukana arvio on todellisuudesta? Todennäköisyyslaskennalla on mahdollista laskea, että tarkka odotusarvo on 14.7, mikä on lähellä simulaation antamaa tulosta. Näin on yleensäkin: saamme hyvän kuvan satunnaisilmiön luonteesta toistamalla sitä tietokoneella tarpeeksi monta kertaa.

---

Tehtävä 1 Ratkaisematon

Kirjaudu sisään ratkoaksesi tehtäviä.

Seuraava tilasto näyttää tulokset simulaatiossa, jossa kolikkoa on heitetty 100 kertaa:

47 53

Tämä tarkoittaa, että kruuna tuli 47 kertaa ja klaava tuli 53 kertaa.

Toteuta vastaava simulaatio, jossa kolikkoa heitetään 1000 kertaa.

Kirjoita ohjelma tähän:

---

Tehtävä 2 Ratkaisematon

Kirjaudu sisään ratkoaksesi tehtäviä.

Seuraava tilasto näyttää tulokset simulaatiossa, jossa noppaa on heitetty 100 kertaa:

14 12 18 23 14 19

Tämä tarkoittaa, että silmäluku 1 tuli 14 kertaa, silmäluku 2 tuli 12 kertaa, jne.

Toteuta vastaava simulaatio, jossa noppaa heitetään 1000 kertaa.

Kirjoita ohjelma tähän:

---

Tehtävä 3 Ratkaisematon

Kirjaudu sisään ratkoaksesi tehtäviä.

Tehtäväsi on arvioida simulaation avulla, mikä on keskimääräinen silmälukujen summa, kun heität noppaa kolme kertaa. Esimerkiksi jos silmäluvut ovat [4,3,6], summa on 13.

Tee ohjelma, joka tulostaa arvion, mikä on keskimääräinen summa.

Kirjoita ohjelma tähän:

---

Tehtävä 4 Ratkaisematon

Kirjaudu sisään ratkoaksesi tehtäviä.

Tarkastellaan tilannetta, jossa arvotaan kaksi kokonaislukua väliltä 1...100. Kuinka suuri on keskimäärin suurempi näistä luvuista? Esimerkiksi jos luvut ovat [43,78], suurempi luvuista on 78.

Tee ohjelma, joka tulostaa arvion, kuinka suuri on keskimäärin suurempi luvuista.

Kirjoita ohjelma tähän:

---

Tehtävä 5 Ratkaisematon

Kirjaudu sisään ratkoaksesi tehtäviä.

Tarkastellaan tilannetta, jossa arvotaan kaksi kokonaislukua väliltä 1...100. Kuinka suuri on keskimäärin näiden lukujen ero? Esimerkiksi jos luvut ovat [43,78], niiden ero on 35.

Tee ohjelma, joka tulostaa arvion, kuinka suuri lukujen ero on keskimäärin.

Kirjoita ohjelma tähän:

---

Tehtävä 6 Ratkaisematon

Kirjaudu sisään ratkoaksesi tehtäviä.

Tehtäväsi on arvioida simulaation avulla, montako kertaa sinun tulee heittää noppaa keskimäärin, kunnes olet saanut peräkkäin kolme samaa silmälukua.

Tee ohjelma, joka tulostaa arvion, montako heittoa tarvitaan keskimäärin.

Kirjoita ohjelma tähän:

---