KOT MODELI MARKOVSKIH VERIG

UNIVERZA V LJUBLJANI PEDAGOˇ SKA FAKULTETA

TEJA FRANKO

PREPROSTE NAMIZNE IGRE

KOT MODELI MARKOVSKIH VERIG

DIPLOMSKO DELO

LJUBLJANA, 2017

UNIVERZA V LJUBLJANI PEDAGOˇ SKA FAKULTETA

Dvopredmetni uˇ citelj: matematika - raˇ cunalniˇstvo

TEJA FRANKO

Mentor: doc. dr. BOˇ STJAN KUZMAN

PREPROSTE NAMIZNE IGRE

KOT MODELI MARKOVSKIH VERIG

DIPLOMSKO DELO

LJUBLJANA, 2017

Posebna zahvala gre mentorju, doc. dr. Boˇstjanu Kuzmanu, za nasvete, po- trpeˇzljivost, strokovno pomoˇc in ˇcas, ki ga je posvetil nastajanju tega diplom- skega dela.

Rada bi se zahvalila druˇzini, ki me je v ˇcasu ˇstudija in nastajanja diplomskega dela spodbujala in podpirala. Zahvalila bi se tudi prijateljem, ki so mi ta ˇcas stali ob strani.

Povzetek

Markovske verige so matematiˇcni model za nakljuˇcno prehajanje med razliˇcnimi moˇznimi stanji z vnaprej znanimi verjetnostmi prehoda. Glede na ˇstevilo moˇznih stanj loˇcimo diskretne in zvezne markovske verige. Markovske ve- rige s konˇcnim ˇstevilom stanj lahko uˇcinkovito obravnavamo z orodji linearne algebre. Naj bo S = {s₁, s₂, . . . , s_n} konˇcna mnoˇzica stanj neke markovske verige. Verjetnost prehoda iz stanja s_i v stanje s_j oznaˇcimo sp_ij in sestavimo prehodno matriko P velikosti n ×n. Dobljena matrika je (vrstiˇcno) stoha- stiˇcna matrika. Posebne algebrske lastnosti stohastiˇcnih matrik omogoˇcajo napovedovanje obnaˇsanja markovskih verig po doloˇcenem ˇstevilu korakov. S pomoˇcjo markovskih verig lahko na nekoliko poenostavljen naˇcin obravnavamo tudi razliˇcne enostavnejˇse matematiˇcne probleme iz verjetnosti in preproste na- mizne igre, kot so Hi Ho Cherry O, Kaˇce in lestve, Monopoly.

Kljuˇcne besede: verjetnost, markovska veriga, markovska lastnost, prehodna matrika, prehodna verjetnost, namizne igre

Abstract

Markov chains are a mathematical model for random passing between states with pre-known transition probabilities. Depending on the number of possible states, we know dicrete and continuous - time markov chains. Markov chains with a finite number of states can be effectively considered with linear algebra tools. LetS ={s₁, s₂, . . . , s_n}be the finite set of states of a markov chain. The transition probability between states s_i and s_j, denoted by p_ij, gives us the transition matrixP of sizen×n. Matrix obtained like this is a (row) stochastic matrix. Special algebraic properties of stochastic matrices allow us to predict the behaviour of Markov chains after a certain number of steps. With the help of knowing Markov chains, various simpler mathematical problems and simple board games, such as Hi Ho Cherry O, Snakes and ladders, Monopoly, can be dealt with.

Key words: probability, Markov chain, Markov property, transition matrix, transition probability, board games

Kazalo

1 Uvod 1

2 Matematiˇcne osnove 2

2.1 Dogodki, verjetnost in pogojna verjetnost . . . 2

2.2 Linearna algebra . . . 9

3 Markovske verige s konˇcno stanji 12 3.1 Sluˇcajni procesi in markovska lastnost . . . 12

3.2 Prehodne matrike in diagrami markovskih verig . . . 14

3.3 Potenca matrike in enakost Chapmana in Kolmogorova . . . 17

4 Namizne igre in markovske verige 21 4.1 Preprosti sprehodi do cilja . . . 21

4.2 Hi Ho Cherry O . . . 23

4.2.1 Pravila igre . . . 23

4.2.2 Matematiˇcni opis igre . . . 24

4.3 Druge igre . . . 27

4.3.1 Kaˇce in lestve . . . 27

4.3.2 Monopoly . . . 29

Slike

1 Digraf . . . 15

2 Enostaven graf . . . 16

3 Diagram markovske verige, ki ustreza nakljuˇcnemu sprehodu po grafu . . . 16

4 Markovska lastnost v Chapman - Kolmogorovi enakosti . . . 18

5 Prikaz igralne ploˇsˇce za n= 3 . . . 21

6 Namizna igra Hi Ho Cherry O . . . 23

8 Verjetnostir_k za k∈ {1,2, . . . ,40}. . . 25

7 Verjetnostip_k za k∈ {1,2, . . . ,40} . . . 26

9 Diagram prehodov za igro Hi Ho Cherry O . . . 27

10 Primer igralne ploˇsˇce za igro Kaˇce in lestve . . . 28

11 Primer igralne ploˇsˇce za igro Monopoly . . . 29

Tabele

2 Verjetnosti, da vk korakih pridemo na cilj pri igri Hi Ho Cherry O . . . 25

3 Povpreˇcno ˇstevilo potez glede na ˇstevilo igralcev . . . 29

1 Uvod

Markovske verige so matematiˇcni model za nakljuˇcno prehajanje med razliˇcnimi moˇznimi stanji z vnaprej znanimi verjetnostmi prehoda. Poimenovane so po ruskem matematiku Andreyu Markovu, ki je tovrstne modele razvil v zaˇcetku 20. stoletja v povezavi z jezikoslovjem, ˇze pred njim pa so jih ˇstudirali tudi drugi matematiki. Glede na ˇstevilo moˇznih stanj loˇcimo markovske verige s konˇcnim, ˇstevnim ali neˇstevno mnoˇzico stanj, glede na ˇcasovne intervale po- mikanja med stanji pa markovske verige v zveznem ali diskretnem ˇcasu. Za obravnavo so najpreprostejˇse markovske verige s konˇcnim ˇstevilom stanj, ki jih lahko uˇcinkovito obravnavamo z orodji linearne algebre in teorije grafov.

Durret (2009) pomembnost markovskih verig poveˇze z dvema dejstvoma:

(i) z markovskimi verigami lahko opiˇsemo veliko fiziˇcnih, bioloˇskih, ekonom- skih in socialnih fenomenov,

(ii) obstaja dobro razvita teorija, ki nam dovoljuje izraˇcune.

V nalogi bomo predstavili osnove teorije markovskih verig in si ogledali kako z njeno pomoˇcjo odgovorimo na razliˇcna vpraˇsanja, s katerimi se lahko sreˇcamo pri igranju preprostih namiznih iger s kocko, ki so odvisne od nakljuˇcij. Ena takih iger je denimo otroˇska igra Hi Ho Cherry Oh, ki jo bomo natanˇcneje predstavili v zakljuˇcnem delu naloge skupaj s ˇse nekaterimi drugimi igrami.

To je uˇcencem zanimivo, saj so igre motivacijsko sredstvo za uˇcenje verjetno- sti, ˇceprav se pogosto izkaˇze, da so na videz enostavna vpraˇsanja matematiˇcno prezahtevna v vsakdanjih ˇsolskih situacijah. Pri namizni igri Hi Ho Cherry O denimo zmaga tisti igralec, ki prvi napolni vedro z desetimi ˇceˇsnjami glede na korake, ki jih doloˇca nakljuˇcno vrtenje kolesa. Zanima nas recimo, kolikˇsna je verjetnost, da napolnimo vedro in kolikˇsno je povpreˇcno ˇstevilo krogov, da se igra zakljuˇci.

Na nekatera tovrstna vpraˇsanja lahko odgovorimo s pomoˇcjo markovskih ve- rig, kar si bomo pogledali v ˇcetrtem poglavju tega diplomskega dela. Delno bi na ta vpraˇsanja lahko odgovorili ˇze s srednjeˇsolsko matematiko z uporabo pogojne verjetnosti, vendar je uˇcinkovito uporabljati orodja linearne algebre, ki raˇcune bistveno poenostavijo in olajˇsajo analizo limitnih primerov.

Uvodu sledi poglavje, v katerem ponovimo osnove verjetnosti in linearne alge- bre, ki ju bomo potrebovali za matematiˇcno korekten opis teorije markovskih verig. V tretjem poglavju predstavimo osnovne pojme in izreke te teorije sku- paj z zgledi, v zakljuˇcnem poglavju pa predstavimo nekaj preprostih primerov namiznih iger v kontekstu markovskih verig.

1

2 Matematiˇ cne osnove

V tem razdelku so zbrane definicije osnovnih pojmov in nekaj izrekov s po- droˇcja verjetnosti in linearne algebre, ki so potrebni za razumevanje tega di- plomskega dela. Za laˇzje razumevanje je navedenih tudi nekaj primerov, ki so izbrani tako, da se bomo nanje navezovali tudi kasneje pri obravnavi marko- vskih verig. V razdelku 2.1 izhajamo iz literature [6] in [14], v razdelku 2.2 pa iz literature [10], [11] in [12].

2.1 Dogodki, verjetnost in pogojna verjetnost

V nalogi pojem verjetnost razumemo kot matematiˇcno verjetnost, torej kot funkcijo iz prostora dogodkov nekega poskusa v mnoˇzico realnih ˇstevil, ki zadoˇsˇca trem aksiomom Kolmogorova (imenovanim po ruskem matematiku Andreyu Nikolaevich Kolmogorovu (1903-1987)).

Definicija. Naj boS poljubna mnoˇzica, ki jo bomo imenovali prostor izidovin naj bo P(S) njena potenˇcna mnoˇzica, ki jo bomo imenovali prostor dogodkov (oziroma algebra dogodkov). Vsako podmnoˇzico A⊆S imenujemo dogodek.

Definicija. Naj bosta A, B ⊆S dogodka nekega poskusa, ki imata prostor iz- idov S. Tedaj pravimo, da je A poddogodek dogodka B, ˇce velja A ⊆ B. Dogodku A∪B pravimo unija ali vsota dogodkov A in B, dogodku A∩B pa presek ali produkt dogodkov A in B. Pravimo, da sta dogodka A in B dis- junktnaoziroma nezdruˇzljiva, ˇce je njun produkt nemogoˇc dogodek, to pomeni, ˇce velja A∩B = ∅. Dogodku S\A, ki ga oznaˇcimo z A, pravimo¯ nasprotni dogodek dogodka A.

Definicija. Imamo poskus, katerega prostor izidov je S. Verjetnost(tudi ver- jetnostna funkcija), katere prostor izidov je S, je vsaka preslikava P :P(S)→ R, ki zadoˇsˇca trem aksiomom:

(i) P(A)≥0 za vse dogodke A⊆S.

(ii) P(S) = 1.

(iii) Za vsako ˇstevno neskonˇcno druˇzino {A_n : n ∈ N} paroma disjunktnih dogodkov A_n ⊆ S, A_i ∩ A_j = ∅ za vse i, j ∈ N, i 6= j, velja, da je verjetnost njihove unije enaka vsoti njihovih verjetnosti, torej velja

P(

∞

[

n=1

A_n) =

∞

X

n=1

P(A_n).

Tretjemu aksiomu pravimo ˇstevna aditivnost.

Definicija. Imejmo nek poskus, za katerega je podan prostor izidov S in ver- jetnost P na S. Tedaj je par (S, P) verjetnostni prostor.

2

Opomba. V sploˇsnem se verjetnostni prostor obiˇcajno definira kot trojica (S, F, P), kjer druˇzina mnoˇzic F ⊆ P(S), ki predstavlja algebro dogodkov, ustreza zahtevam za tako imenovano σ - algebro. V naˇsi nalogi bomo ves ˇcas privzeli, da je F =P(S), ker nam to zadoˇsˇca za naˇso obravnavo.

Bralec se bo spomnil, da za verjetnost veljajo naslednje osnovne lastnosti, katerih dokaz se najde med drugim tudi v srednjeˇsolskih uˇcbenikih.

Trditev 2.1. Naj bo P verjetnost na prostoru izidov S nekega poskusa in naj bosta A in B poljubna dogodka. Tedaj velja:

(i) 0≤P(A)≤1.

(ii) P( ¯A) = 1−P(A).

(iii) P(B \A) =P(B)−P(A∩B).

(iv) P(A∪B) =P(A) +P(B)−P(A∩B).

(v) ˇCe je A⊆B, je P(A)≤P(B).

Zgled. Poglejmo si igro na ˇsestih poljih, kjer prvo polje predstavlja ˇstart, polje ˇstevilka6pa cilj. Igralec enkrat vrˇze poˇsteno kocko in premakne figurico naprej za ustrezno ˇstevilo pik brez odboja.

Izraˇcunajmo verjetnost dogodkov A, B in C, kjer jeA ≡ igralec pride na cilj, B ≡ igralec ne pride na cilj in C ≡ igralec pride na polje s sodo ˇstevilko.

Tedaj je P(A) = ²₆, P(B) = 1−P(A) = ⁴₆, P(C) = ⁴₆, P(C) = 1− ⁴₆ = ²₆. Pri igrah, ki jih bomo obravnavali kasneje, bomo opazovali tudi spremembe poloˇzaja pri veˇc zaporednih metih, pri ˇcemer bo verjetnost trenutne pozicije odvisna od preteklih, zato moramo vpeljati tudi pojem pogojne verjetnosti.

Definicija. Naj bo S prostor izidov za nek poskus in naj bo P verjetnost na S. Naj bosta A, B ⊆ S taka dogodka, da velja P(B) > 0. Tedaj pogojno verjetnost dogodka A pri pogoju, da se je zgodil dogodek B, oziroma pogojno verjetnost dogodka A pri pogoju B oznaˇcimo s P(A|B) in jo definiramo kot

P(A|B) = P(A∩B) P(B) . Hitro lahko opazimo, da za pogojno verjetnost velja

P(B |B) = P(B∩B)

P(B) = P(B) P(B) = 1 3

in

P(A|S) = P(A∩S)

P(S) = P(A)

1 =P(A).

Priˇcakovali bi seveda, da tudi pogojna verjetnost ustreza lastnostim verjetno- stne funkcije iz definicije Kolmogorova. Da je to res, nam zagotavlja naslednji izrek.

Izrek 2.2. Naj bo (S,P) verjetnostni prostor in naj bo B ⊆ S tak dogodek, da je P(B) > 0. Tedaj je preslikava Q : P(S) → R, podana s predpisom Q(A) = P(A | B), verjetnost na prostoru izidov S. Z drugimi besedami, tudi (S,Q) je verjetnostni prostor.

Dokaz. Naj bo P(B) > 0. Najprej ˇzelimo pokazati, da je zadoˇsˇceno prvemu aksiomu, in sicer da velja Q(A)≥0. Velja

Q(A) =P(A|B) = P(A∩B) P(B) ,

in ker je po zaˇcetni predpostavki P(B) >0, sledi prvi aksiom. Iz S∩B = B sledi, da je

Q(S) =P(S |B) = P(S∩B)

P(B) = P(B) P(B) = 1,

torej drugi aksiom. Pokaˇzimo sedaj ˇse, da velja tretji aksiom. Naj bodo dogodki A₁, A₂, A₃, . . . paroma disjunktni. Tedaj so paroma disjunktni tudi dogodki

A₁∩B, A₂∩B, A₃ ∩B, . . . Sledi

Q(

∞

[

n=1

A_n) = P((S∞

n=1A_n)∩B)

P(B) = (po definiciji Q)

= P(S∞

n=1(A_n∩B))

P(B) = (po distributivnosti preseka in unije)

= P∞

n=1P(A_n∩B)

P(B) = (po ˇstevni aditivnosti P)

=

∞

X

n=1

P(An∩B) P(B) =

∞

X

n=1

P(A_n|B) =

=

∞

X

n=1

Q(A_n).

4

Zgled. Tako kot prej si poglejmo igro na ˇsestih poljih, le da tokrat poˇsteno kocko meˇcemo dvakrat in vsakiˇc figurico premaknemo za ustrezno ˇstevilo polj.

Oznaˇcimo z A dogodek, da igralec po dveh metih pride na cilj in z B dogodek, da igralec v prvem metu vrˇze 1. Zanima nas verjetnost, da bomo po dveh metih priˇsli na cilj, ˇce smo v prvem metu vrgli 1.

V mnoˇzici izidov S so vsi moˇzni urejeni pari metov, torej je S ={(a, b) :a, b∈ {1, . . . ,6}},

od koder sledi, da je|S|= 36. Ker je kocka poˇstena, predpostavljamo, da so vsi izidi enako verjetni. Torej je verjetnost posameznega izida enaka ₃₆¹.

Za A∩B so ugodne moˇznosti (1,4),(1,5) in (1,6), kar pomeni, da je P(A∩ B) = ₃₆³ = ₁₂¹ . Verjetnost, da smo v prvem metu vrgli 1, pa jeP(B) = ¹₆.Torej je

P(A|B) = P(A∩B) P(B) =

1 12

1 6

= 1 2.

Izrek 2.3 (O popolni verjetnosti). Naj bo (S,P) verjetnostni prostor. Naj bo {A_n ⊆ S : n ∈ I} taka konˇcna ali ˇstevno neskonˇcna druˇzina dogodkov, da velja:

(i) S

n∈IA_n =S,

(ii) A_i∩A_j =∅ za vse i, j ∈I, i6=j, (iii) P(A_n)>0 za vse n ∈I.

Potem za poljuben dogodek B ⊆S velja P(B) = X

n∈I

P(A_n)P(B |A_n).

Druˇzino mnoˇzic A_n imenujemo popoln sistem dogodkov.

Dokaz. Prvi dve zahtevi pomenita, da je druˇzina{A_n: n ∈I}particija mnoˇzice S, zato je {B∩A_n:n∈I} particija mnoˇzice B. To pomeni, da je dogodek B disjunktna unija dogodkovB∩A_n, kjer jen∈I.Po tretjem aksiomu verjetnosti velja

P(B) =P([

n∈I

(B∩A_n)) =X

n∈I

P(B∩A_n) =X

n∈I

P(A_n)P(B |An).

5

Zgled. Nadaljujemo zgled od prej. Tokrat nas zanima, kakˇsna je verjetnost, da smo po drugem metu na polju 5.

Oznaˇcimo zB verjetnost, da smo po drugem metu na polju 5 in zA_i verjetnost, da smo po prvem metu na polju i, kjer je i∈ {2,3,4,5,6}. Potem je {A_i :i∈ {1, . . . ,6}} popoln sistem dogodkov. Izraˇcunati moramo P(B).Velja

P(A₂) = P(A₃) =P(A₄) =P(A₅) = 1

6, P(A₆) = 2 6. Ker je P(B |A₅) =P(B |A₆) = 0, sledi

P(B) = P(B |A₂)·P(A₂) +P(B |A₃)·P(A₃) +P(B |A₄)·P(A₄) =

= 3 36 = 1

12.

Podobno bi lahko definirali ˇse dogodek C, da smo po drugem metu na cilju.

Potem velja P(C |A₂) = ³₆, P(C |A₃) = ⁴₆, P(C |A₄) = ⁵₆, P(C |A₅) = P(C | A₆) = ⁶₆, zato je

P(C) = 3·1 + 4·1 + 5·1 + 6·1 + 6·2

36 = 30

36 = 5 6. Spomnimo se ˇse definicije neodvisnih dogodkov.

Definicija. Naj bo (S, P) verjetnostni prostor. Dogodka A, B ⊆ S sta neod- visna, ˇce velja P(A∩B) =P(A)P(B).

DogodkaAinB z neniˇcelno verjetnostjo sta neodvisna natanko tedaj, ko velja P(A |B) =P(A) in P(B |A) = P(B).

Zgled. Nadaljujemo zgled od prej. Naj bosta A₃ in C dogodka kot v prejˇsnjem zgledu. Potem velja P(C) = ⁵₆ in P(A₃) = ¹₆. Ker je P(C ∩A₃) = ₃₆⁴ 6=

P(C)·P(A₃), dogodka nista neodvisna. To smo tudi priˇcakovali, saj se zdi smiselno, da poloˇzaj po prvem metu vpliva na poloˇzaj po drugem.

Veˇcino doslej omenjenih pojmov sreˇcamo ˇze v srednji ˇsoli, kjer pa se ponavadi ne obravnava sluˇcajnih spremenljivk. Na podlagi njihovih lastnosti obiˇcajno posebej obravnavamo diskretne in zvezne sluˇcajne spremenljivke. Ker v di- plomski nalogi obravnavamo le markovske verige s konˇcno mnoˇzico stanj, ki jih lahko predstavimo z matrikami, bomo tukaj definirali le diskretne sluˇcajne spremenljivke.

Definicija. Naj bo (S, P) verjetnostni prostor. Diskretna sluˇcajna spremen- ljivka na prostoru(S, P)je tedaj vsaka funkcijaX :S →R, za katero velja, da je zaloga vrednosti oziroma slika prostora izidovX(S) = {X(s) :s∈S} ⊆R ˇstevna mnoˇzica.

6

Vzemimo zdajX :S →Rdiskretno sluˇcajno spremenljivko inx∈R. Tedaj je X⁻¹(x) = {s ∈S : X(s) = x} ⊆S, torej je X⁻¹(x) dogodek, ki ga oznaˇcimo z (X =x) in imenujemo dogodek, da sluˇcajna spremenljivka X zavzame vre- dnost x. Zgodi se lahko, da nas bo za neko konkretno vrednost x zanimala verjetnost tega dogodka, torej verjetnost P(X⁻¹(x)) =P(X =x).

V zvezi s sluˇcajnimi spremenljivkami so povezani ˇstevilni pojmi, kot so poraz- delitev, matematiˇcno upanje, varianca, disperzija, kovarianca in podobno. V diplomskem delu bomo omenili le prva dva od naˇstetih.

Definicija. Naj bo X : S →R diskretna sluˇcajna spremenljivka na verjetno- stnem prostoru(S, P). Takrat je verjetnostna funkcijaali porazdelitev diskre- tne sluˇcajne spremenljivke X funkcijap_X :R→[0,1], podana s predpisom

p_X(x) = P(X =x).

Zgled. Nadaljujemo prejˇsnji zgled. Naj bo sluˇcajna spremenljivka X funkcija, ki oznaˇcuje naˇso pozicijo po prvem metu poˇstene kocke, torej ima zalogo vre- dnosti X(S) = {2,3,4,5,6}, verjetnosti P(X = 2) = P(X = 3) = P(X = 4) =P(X = 5) = ¹₆, P(X = 6) = ²₆ in porazdelitev p_X, ki jo lahko predstavimo kar s takoimenovano porazdelitveno shemo

X ∼

2 3 4 5 6

1 6

1 6

1 6

1 6

2 6

.

Podobno naj bo sluˇcajna spremenljivka Y funkcija, ki oznaˇcuje naˇso pozicijo po drugem metu, torej ima zalogo vrednosti Y(S) ={3,4,5,6}, verjetnosti

P(Y = 3) = 1

36, P(Y = 4) = 2

36, P(Y = 5) = 3 36 in P(Y = 6) = ³⁰₃₆, pa zapiˇsemo porazdelitveno shemo kot

Y ∼

3 4 5 6

1 36

2 36

3 36

30 36

.

Torej je verjetnost, da igro konˇcamo po dveh metih, enaka ⁵₆, kar smo seveda izraˇcunali ˇze prej.

Velja seveda

Trditev 2.4. Naj bo X : S → R diskretna sluˇcajna spremenljivka, katere verjetnostni prostor je (S,P). Tedaj za vsak x ∈ R\X(S) velja p_X(x) = 0 in tudi P

x∈X(S)p_X(x) = 1.

Dokaz izpustimo, naveden je v zapiskih predavanj dr. ˇSparla pri predmetu Verjetnostni raˇcun in statistika.

Spomnimo se ˇse, kaj pomeni matematiˇcno upanje.

7

Definicija. Naj bo X diskretna sluˇcajna spremenljivka na verjetnostnem pro- storu (S, P). Tedaj pravimo, da je matematiˇcno upanje spremenljivke X, ka- terega oznaka je E(X), podano s predpisom

E(X) = X

x∈X(S)

x·p_X(x) = X

x∈X(S)

x·P(X =x), ˇce ta vrsta konvergira absolutno (to pomeni, ˇce jeP

x∈X(S)|xP(X =x)|<∞).

V tem diplomskem delu bodo nastopale le diskretne sluˇcajne spremenljivke s konˇcno zalogo vrednosti, zato bodo ustrezne vsote vselej konˇcne.

Zgled. Ponovno si poglejmo igro s ˇsestimi polji in poˇsteno kocko. Polje ˇstevilka 1 nam predstavlja ˇstart, polje ˇstevilka 6 pa cilj. Naj X1 oznaˇcuje ˇstevilko polja po prvem metu in najX₂ oznaˇcuje ˇstevilko polja po drugem metu. Izraˇcunajmo verjetnosti, da je (X₂ = 6 | X₁ = 2) in (X₂ = 4 |X₁ = 2) ter porazdelitev za X1 in X2 in matematiˇcna upanja E(X1) in E(X2).

Ce smo v prvem metu vrgli 1 in smo na polju 2, lahko v drugem metu doseˇˇ zemo cilj, ˇce vrˇzemo 4, 5 ali 6, torej je

P(X₂ = 6 |X₁ = 2) = 3 36 = 1

12.

S podobnim razmislekom dobimo

P(X₂ = 4|X₁ = 2) = 1 36.

Ker so verjetnosti P(X₁ = 1) = 0, P(X₁ = 2) = P(X₁ = 3) = P(X₁ = 4) = P(X1 = 5) = ¹₆ in P(X1 = 6) = ²₆, dobimo porazdelitev

X₁ ∼

1 2 3 4 5 6 0 ¹₆ ¹₆ ¹₆ ¹₆ ²₆

. Matematiˇcno upanje za X₁ pa je

E(X₁) = 1·0 + 2· 1

6+ 3· 1

6+ 4·1

6 + 5· 1

6 + 6· 2 6 = 13

3

= 4.33..

Verjetnosti zaX2pa soP(X2 = 1) =P(X2 = 2) = 0, P(X2 = 3) = ₃₆¹, P(X2 = 4) = ₃₆², P(X₂ = 5) = ₃₆³ in P(X₂ = 6) = ³⁰₃₆, kar nam da porazdelitev

X₂ ∼

1 2 3 4 5 6 0 0 ₃₆¹ ₃₆² ₃₆^{3 30}₃₆

, 8

matematiˇcno upanje za X₂ pa dobimo E(X₂) = 1·0 + 2·0 + 3· 1

36+ 4· 2

36 + 5· 3

36+ 6·30

36 = 103 18

= 5.72.. E(X₁)nam pove, da bomo po prvem metu v povpreˇcju na ˇcetrtem polju,E(X₂) pa nam pove, da bomo po drugem metu v povpreˇcju na ˇsestem polju.

2.2 Linearna algebra

Za laˇzje razumevanje nadaljevanja diplomske naloge smo v tem razdelku zbrali nekaj definicij in izrekov linearne algebre.

Definicija. Naj bosta m ≥1 in n ≥1 dve naravni ˇstevili in polje R. Matrika velikosti m×n nad poljem R je tabela zmn elementi a_ij ∈R, ki so razvrˇsˇceni v m vrstic, ki imajo vsaka po n elementov:

A=











a₁₁ a₁₂ . . . a_1n a₂₁ a₂₂ . . . a_2n ... ... . .. ... a_m1 a_m2 . . . a_mn











Pri elementu a_ij je prvi indeks indeks vrstice, drugi pa je indeks stolpca.Ta element stoji na kriˇziˇsˇcu i-te vrstice in j-tega stolpca. S simboli lahko matriko zapiˇsemo kot A= [aij].

Obstajajo tudi matrike posebnih oblik s posebnimi imeni.

Definicija. Matriko [a₁₁] velikosti 1×1imenujemo kar matrika ’skalar’. Ma- trika z eno samo vrstico se imenuje vrstiˇcna matrikaali vrstica, ˇce pa vsebuje le en stolpec, se imenuje stolpiˇcna matrika ali stolpec.

Matrike bomo v nalogi mnoˇzili na obiˇcajen naˇcin. Najpogosteje bomo med seboj mnoˇzili kvadratne matrike oziroma raˇcunali potence takih matrik. Po- gosto pa bomo potrebovali tudi mnoˇzenje vrstiˇcne matrike velikosti 1×n s kvadratno matriko velikosti n×n, v tem primeru za rezultat dobimo vrstiˇcno matriko velikosti 1×n. Taki vrstiˇcni matriki bomo rekli kar vektor.

Definicija. Vektorju u= (u₁, u₂, . . . , u_n)∈R^1×n pravimo verjetnostni vektor, ˇce so vse njegove komponente nenegativne in je njihova vsota enaka 1: u_i ≥0

∀i∈ {1, . . . , n}, Pn

i=1u_i = 1.

Definicija. Naj boA∈R^n×n neka matrika z nenegativnimi koeficientia_ij ≥0.

MatrikaAje (vrstiˇcno) stohastiˇcna, ˇce dodatno velja ˇse, da je vsota elementov v vsaki vrstici enaka 1, torej Pn

j=1a_ij = 1 za ∀i. Z drugimi besedami, vrstice stohastiˇcne matrike so verjetnostni vektorji.

9

Trditev 2.5. Ce sta matrikiˇ A, B ∈ R^n×n stohastiˇcni matriki, potem je tudi produkt AB stohastiˇcna matrika. Posebej, vse potence A^m, kjer je m ∈ N, so stohastiˇcne matrike.

Dokaz. Naj bosta A= [a_ij]in B = [b_ij] stohastiˇcni matriki reda n×n. Potem je produkt C=AB matrika s koeficienti cij =Pn

k=1aikbkj. Ker velja

n

X

j=1

a_ij = 1,∀i,

in n

X

j=1

b_ij = 1,∀i, za koeficiente i-te vrstice matrike C velja

n

X

j=1

c_ij =

n

X

j=1

(

n

X

k=1

a_ikb_kj) =

n

X

k=1

(

n

X

j=1

a_ikb_kj) =

=

n

X

k=1

a_ik(

n

X

j=1

b_kj) =

n

X

k=1

a_ik = 1, torej je C stohastiˇcna matrika.

Definicija. Stohastiˇcna matrika A je regularna, ˇce so vsi koeficienti neke njene potence Aⁿ, kjer je n∈N, strogo pozitivni.

Definicija. Naj bo A ∈ R^n×n neka stohastiˇcna matrika. Verjetnostni vektor u = (u₁, . . . , u_n) ∈ R^1×n imenujemo fiksni vektor (glede na matriko A), ˇce velja uA = u. Z drugimi besedami, fiksni vektor je torej (levi) lastni vektor matrike A pri lastni vrednosti 1.

Zgled. Naj bo

A=

0 1 0.5 0.5

stohastiˇcna matrika. Njen kvadrat A² =

0.5 0.5 0.25 0.75

ima same pozitivne koeficiente, torej je A regularna. Pri linearni algebri smo lastne vrednosti matrike raˇcunali kot niˇcle karakteristiˇcnega polinoma:

∆_A(λ) =det(A−λI) =

=

0−λ 1

0.5 0.5−λ

=

=λ²−0.5λ−0.5 = (λ+ 0.5)(λ−1).

10

V tem primeru smo za eno od lastnih vrednosti dobili vrednost λ = 1. Za to lastno vrednost lahko z reˇsevanjem ustreznega sistema linearnih enaˇcb doloˇcimo ustrezne (leve) lastne vektorje. Kot reˇsitev dobimo vse veˇckratnike vektorja (1,2). Ker nas zanima verjetnostni vektor, bomo seveda izbrali vektor u = (1/3,2/3), ki je torej fiksni vektor naˇse stohastiˇcne matrike A.

Pri opisanem zgledu smo torej za dano stohastiˇcno matriko uspeli najti tudi ustrezni fiksni vektor. Naslednji izrek pove, da je to vselej moˇzno, ˇce je matrika regularna. Gre za globok izrek iz linearne algebre, katerega dokaz presega to delo in ga lahko poiˇsˇcemo v ustrezni literaturi. Izrek povzemamo po [11, poglavje 7].

Izrek 2.6. Naj bo A∈R^n×n regularna stohastiˇcna matrika. Potem velja:

(i) A ima enoliˇcno doloˇcen fiksni vektoru, katerega vse komponente so strogo pozitivne,

(ii) zaporedje potencA, A², A³, . . . konvergira (po komponentah) proti matriki T, katere vrstice so vse enake fiksnemu vektorju u,

(iii) ˇce je v poljuben verjetnostni vektor ustrezne velikosti, potem zaporedje vektorjev vA, vA², vA³, . . . konvergira (po komponentah) proti fiksnemu vektorju u.

Zgled. Za matriko A iz prejˇsnjega zgleda velja denimo A⁵ =

0.3125 0.6875 0.34375 0.65625

in

A¹⁰ .

=

0.334 0.666 0.333 0.667

, kar je v skladu z zgornjim izrekom.

11

3 Markovske verige s konˇ cno stanji

V tem poglavju bomo definirali pojem markovskih verig in se osredotoˇcili pred- vsem na verige s konˇcno mnoˇzico stanj, ki jih lahko namreˇc uˇcinkovito pred- stavimo in analiziramo s pomoˇcjo stohastiˇcnih matrik. Dokazali bomo tudi enakost Chapmana in Kolmogorova.

V tem razdelku izhajamo iz literature [6], [9] in [10].

3.1 Sluˇ cajni procesi in markovska lastnost

Pred vpeljavo formalne definicije markovskih verig najprej podajmo znamenit primer iz zgodovine verjetnostnega raˇcuna, ki je znan pod imenom Kockarjeva poguba (Gambler’s ruin). Z njim so se ˇze v 17. stoletju ukvarjali ˇstevilni zna- meniti matematiki, med njimi Blaise Pascal, Pierre de Carcavi in drugi. Naˇsa razliˇcica problema je poenostavljena in povzeta po viru [6].

Zgled. Razmislimo o igri na sreˇco, pri kateri v vsakem krogu dobimo 1 kova- nec z verjetnostjop= 0.4in izgubimo 1 kovanec z verjetnostjo q = 1−p= 0.6.

Nato predvidimo pravilo, da konˇcamo z igranjem, ko zberemo vnaprej doloˇceno ˇstevilo kovancev N >0, ali pa, ko nam kovancev zmanjka. Na zaˇcetku imamo 0< n < N kocancev.

Da zgled poenostavimo, vzemimo za N = 5 in n= 2. Torej, zaˇcnemo z dvema kovancema in konˇcamo z igro, ko izgubimo vse kovance ali ko imamo 5 kovan- cev. Zanima nas, kakˇsna je verjetnost, da dobimo 5 kovancev ali izgubimo vse kovance.

Mnoˇzica stanj je enaka moˇznim ˇstevilom kovancev, torej S = {0,1,2,3,4,5}.

Naj bo X_i sluˇcajna spremenljivka, ki predstavlja ˇstevilo kovancev po i igrah.

Doloˇcimo porazdelitve.

P(X_o = 2) = 1, saj zaˇcnemo igrati z dvema kovancema, torej imamo porazde- litev

X0 ∼

0 1 2 3 4 5 0 0 1 0 0 0

.

P(X₁ = 1) =q= 0.6, in sicer ˇce izgubimo 1 kovanec in P(X₁ = 3) =p= 0.4, ˇce dobimo 1 kovanec. Ostalih vrednosti spremenljivkaX₁ ne more zavzeti, torej dobimo porazdelitev

X₁ ∼

0 1 2 3 4 5 0 q 0 p 0 0

∼

0 1 2 3 4 5 0 0.6 0 0.4 0 0

.

12

Da lahko doloˇcimo porazdelitev za X₂, uporabimo izrek o popolni verjetnosti.

Po treh igrah imamo lahko 0, 2 ali 4 kovance.

P(X₂ = 0) = P(X₂ | X₁ = 1)·P(X₁ = 1) = q ·q = q² = 0.6², saj do 0 kovancev lahko pridemo le, ˇce dvakrat izgubimo. P(X₂ = 4) = P(X₂ = 4 | X1 = 3) ·P(X1 = 3) = p·p = p² = 0.4², saj do 4 kovancev po drugi igri pridemo le, ˇce dvakrat zapored zmagamo.

Do dveh kovancev po drugi igri pa lahko pridemo, ˇce v prvi igri izgubimo/zmagamo in nato v drugi igri zmagamo/izgubimo. Torej je verjetnost enaka P(X₂ = 2) = P(X₂ = 2 | X₁ = 1)·P(X₁ = 1) +P(X₂ = 2 | X₁ = 3)·P(X₁ = 3) = p·q+q·p= 2pq= 2·0.6·0.4 in dobimo porazdelitev

X₂ ∼

0 1 2 3 4 5 q² 0 2pq 0 p² 0

∼

0 1 2 3 4 5 0.36 0 0.48 0 0.16 0

. Na podoben naˇcin izraˇcunamo ˇse porazdelitev

X₃ ∼

0 1 2 3 4 5 q² 2pq² 0 3p²q 0 p³

∼

0 1 2 3 4 5 0.36 0.288 0 0.288 0 0.064

, ter tudi porazdelitve X₄, X₅, . . ..

Zanimiva lastnost zgornjega zgleda je, da je za izraˇcun porazdelitve X_n+1 zadoˇsˇcalo poznati porazdelitev X_n, ne pa tudi preteklih porazdelitev. To je v bistvu kljuˇcna lastnost markovskih verig, ki jih bomo definirali v nadaljevanju.

Definicija. Naj bo S ˇstevna mnoˇzica, ki ji bomo rekli mnoˇzica stanj, njenim elementom i ∈ S pa stanja. Sluˇcajni proces (z diskretnim ˇcasom) je vsako zaporedje diskretnih sluˇcajnih spremenljivkX₀, X₁, X₂, . . . , X_n, . . . z zalogo vre- dnosti iz S.

Definicija. Sluˇcajni proces X₀, X₁, X₂, . . . , ima markovsko lastnost, ˇce velja P(X_n+1 =j |X₀ =i₀, X₁ =i₁, . . . , X_n =i_n =i) = P(X_n+1 =j |X_n =i), za vsa stanja i_o, . . . , i_n, j ∈ S in vse n ∈ N. Sluˇcajni proces z markovsko lastnostjo imenujemo markovska veriga. Verjetnostp_ij =P(X_n+1 =j |X_n= i) imenujemo verjetnost prehoda iz stanja i v stanje j.

Opomba. Naˇsa definicija govori o homogeni markovski verigi v diskretnem ˇcasu.

13

3.2 Prehodne matrike in diagrami markovskih verig

Markovske verige lahko opiˇsemo na veˇc naˇcinov, med drugim tudi s posebnimi matrikami, katerih definicija sledi v nadaljevanju in s pomoˇcjo diagramov.

Definicija. Naj bo S ={1,2, . . . , n} konˇcna mnoˇzica stanj z n elementi. Vre- dnosti p_ij lahko zberemo v realno matriko P velikosti n×n

P =











p₁₁ p₁₂ · · · p_1n p₂₁ p₂₂ · · · p_2n ... ... . .. ... p_n1 p_n2 · · · p_nn











∈R^n×n,

ki jo imenujemo prehodna matrika dane markovske verige.

Iz definicije sledi naslednja, skoraj oˇcitna trditev.

Trditev 3.1. Naj bo P prehodna matrika konˇcne markovske verige. Tedaj je P stohastiˇcna matrika.

Dokaz. Imamo prehodno matrikoP konˇcne markovske verige velikosti n×n.

Ker so p_ij verjetnosti prehodov, velja

0≤p_ij ≤1,∀i, j ∈ {1,2, . . . , n}.

S tem smo zadostili prvemu pogoju definicije stohastiˇcne matrike. Po izreku o popolni verjetnosti pa velja ˇse, da je vsota koeficientov v vsaki vrstici enaka 1, torej

n

X

j=1

p_ij =

n

X

j=1

P(X_n+1 =j |X_n=i) =

=

n

X

j=1

P(Xn+1 =j, Xn=i) P(X_n=i) =

Pn

j=1P(X_n+1 =j, X_n=i) P(X_n =i) =

= P(Sn

j=1(X_n+1 =j, X_n =i))

P(X_n=i) = P(Sn

j=1(X_n+1 =j), X_n=i) P(X_n=i) = P(S, X_n=i)

P(Xn=i) = P(X_n =i)

P(Xn =i) = 1,∀i.

Sledi, da je P stohastiˇcna matrika.

Markovska veriga torej doloˇca stohastiˇcno matrikoP. Po drugi strani pa sto- hastiˇcna matrika P reda n×n doloˇca markovsko verigo naS ={1,2, . . . , n}.

Markovske verige bi lahko opisali tudi z diagramom prehodov med stanji. Mar- kovsko verigo doloˇca uteˇzen digraf z lastnostjo, da je vsota uteˇzi na izhodnih povezavah vsakega vozliˇsˇca enaka 1.

14

Zgled. Imejmo digraf, kot je prikazano na spodnji sliki.

Slika 1: Digraf

Vozliˇsˇca grafa predstavljajo stanja markovske verige, uteˇzi na povezavah pa prehodne verjetnosti med stanji. Dobimo matriko

P =









1 2 3 4

1 0 0.8 0 0.2

2 0 0.5 0.5 0

3 0 0 0.3 0.7

4 0 1 0 0







 .

Zgled. Poglejmo si primer nakljuˇcnega sprehoda na enostavnem grafu, kjer se v vsakem koraku z enako verjetnostjo premaknemo v eno od sosednjih vozliˇsˇc.

V tem primeru smo uteˇzi na povezavah doloˇcili tako, da so povezave iz istega vozliˇsˇca enako verjetne, torej, uteˇz na vozliˇsˇcu v je enaka 1/deg(v). Dobimo usmerjen graf, kot je prikazano na sliki 3.

15

Slika 2: Enostaven graf

Slika 3: Diagram markovske verige, ki ustreza nakljuˇcnemu sprehodu po grafu Enostavni nakljuˇcni sprehod na grafu oziroma ustrezna markovska veriga ima

16

prehodno matriko

P =





















1 2 3 4 5 6 7

1 0 ¹₂ ¹₂ 0 0 0 0

2 1

3 0 ¹₃ 0 ¹₃ 0 0

3 1

4 1

4 0 ¹₄ 0 ¹₄ 0

4 0 0 1 0 0 0 0

5 0 ¹₂ 0 0 0 ¹₂ 0

6 0 0 ¹₃ 0 ¹₃ 0 ¹₃

7 0 0 0 0 0 1 0



















 .

3.3 Potenca matrike in enakost Chapmana in Kolmogo- rova

Pri analizi markovskih verig nas pogosto zanima, kako prehajamo med stanji v nekem danem ˇstevilu korakov n.

Definicija. S p^(m)_ij oznaˇcimo m - koraˇcno prehodno verjetnost, da pridemo iz stanja i v stanjej v m korakih, torej

p^(m)_ij =P(X_n+m =j |X_n=i).

Za izraˇcun m - koraˇcnih prehodnih verjetnosti je kljuˇcen naslednji izrek.

Izrek 3.2 (Enakost Chapmana in Kolmogorova). Za prehodne verjetnosti po- ljubne markovske verige velja

p^(m+n)(i, j) =X

k

p^(m)(i, k)p⁽ⁿ⁾(k, j), kjer so i, j, k stanja in m, n∈N.

Dokaz. Enakost je v bistvu posledica izreka o popolni verjetnosti. Naj bo X_m(S) zaloga vrednosti za X_m. Tedaj je {(X_m = k) | k ∈ X_m(S)} popoln sistem dogodkov.

17

p^(m+n)_ij =P(X_m+n =j |X₀ =i)

= P(X_m+n=j, X₀ =i)

P(Xo =i) (po definiciji pogojne verjetnosti)

= P

k∈Xm(S)P(X_m+n =j, X₀ =i|X_m =k)·P(X_m =k)

P(X₀ =i) (po IPV)

= P

k∈Xm(S)P(X_m+n =j, X₀ =i, X_m =k)

P(X₀ =i) · P(X_m =k, X₀ =i) P(X_m =k, X₀ =i)

= X

k∈Xm(S)

P(X_m+n=j |X₀ =i, X_m =k)·P(X_m =k, X₀ =i)

= X

k∈X_m(S)

P(X_m+n=j |X_m =k)·P(X_m =k|X₀ =i) (po ML)

= X

k∈Xm(S)

p⁽ⁿ⁾_jk ·p^(m)_ik .

Slika 4: Markovska lastnost v Chapman - Kolmogorovi enakosti

Da gremo od i do j v m+n korakih, moramo od i do nekega stanja k v m korakih in nato od k do j v n korakih. Enakost Chapmana in Kolmogorova torej pove, da moramo seˇsteti verjetnosti vseh vmesnih stanj, markovska la- stnost pa pomeni, da sta oba dela naˇsega potovanja med stanjema med seboj neodvisna.

Posledica 3.3. Naj bo P = [p_ij] prehodna matrika neke markovske verige in naj bo P^(m) = [p^(m)_ij ] matrika m - koraˇcnih prehodnih verjetnosti iste verige.

Potem je P^m =P^(m).

Zgled. (Poenostavljeni labirint). Hrˇcka damo vsak dan v labirint, kjer ima moˇznost iti levo ali desno. Na levi strani ga ˇcaka hrana, na desni strani pa

18

vrtenje kolesa. Na katero stran bo ˇsel, je odvisno od odloˇcitve, v katero smer je ˇsel prejˇsnji dan. ˇCe je vˇceraj ˇsel levo, je 60% verjetnost, da bo tudi danes ˇsel levo. ˇCe je vˇceraj ˇsel desno, je 80% verjetnost, da bo danes ˇsel levo.

Zapiˇsimo prehodno matriko za odloˇcitve hrˇcka. Pri tem upoˇstevamo verjetno- sti:

(i) p₁₁ - verjetnost, da bo ˇsel hrˇcek danes levo, ˇce je ˇsel vˇceraj levo, (ii) p₁₂ - verjetnost, da bo ˇsel hrˇcek danes desno, ˇce je ˇsel vˇceraj levo, (iii) p₂₁ - verjetnost, da bo ˇsel hrˇcek danes levo, ˇce je ˇsel vˇceraj desno,

(iv) p₂₂ - verjetnost, da bo ˇsel hrˇcek danes desno, ˇce je ˇsel vˇceraj desno.

Verjetnost prehodov razvrstimo v prehodno matriko P =

p₁₁ p₁₂ p21 p22

=

0.60 0.40 0.80 0.20

.

Predpostavimo sedaj, da je na zaˇcetku50% verjetnost, da gre hrˇcek levo in50%

verjetnost, da gre desno. Zapiˇsimo prehodno matriko za naslednja dva dneva in izraˇcunajmo, kolikˇsna je verjetnost, da bo ˇsel hrˇcek ˇcez 10 dni na levo stran labirinta.

Upoˇstevamo zaˇcetno porazdelitev, ki jo zapiˇsemo v obliki vektorja v₀ = (0.50 0.50),

nato pa izraˇcunamo za prvi dan v₀·P =v₁. 0.50 0.50

·

0.60 0.40 0.80 0.20

= 0.70 0.30 ,

kar nam pove, da je verjetnost, da bo hrˇcek prvi dan zavil levo enaka 70%, da bo zavil desno pa30%. Izraˇcunajmo ˇse za drugi dan, in sicerv₀·P² =v₂, kar pomeni, da bomo potrebovali kvadrat matrike P.

P² =P ·P =

0.60 0.40 0.80 0.80

0.60 0.40 0.80 0.20

=

0.68 0.32 0.64 0.36

, od koder lahko naprej izraˇcunamo

0.50 0.50

·

0.68 0.32 0.64 0.36

= 0.66 0.34 ,

kar nam pove, da je verjetnost, da bo hrˇcek drugi dan zavil levo enaka 66%, da bo zavil desno pa 34%.

19

Izraˇcunajmo sedaj ˇse, kolikˇsna je verjetnost, da bo ˇsel hrˇcek ˇcez 10 dni na levo stran labirinta. Najprej potrebujemo matriko P¹⁰.

P¹⁰=

0.667 0.333 0.667 0.333

,

nato pa izraˇcunamo enaˇcbo v₀·P¹⁰=v₁₀, in sicer 0.50 0.50

·

0.667 0.333 0.667 0.333

= 0.667 0.333 ,

kar pomeni, da bo ˇsel hrˇcek deseti dan levo z verjetnostjo 66.7%, desno pa z verjetnostjo 33.3%.

20

4 Namizne igre in markovske verige

4.1 Preprosti sprehodi do cilja

ˇStevilne namizne igre potekajo tako, da igralci meˇcejo kocko ali podoben pri- pomoˇcek ter premikajo figurice po igralni ploˇsˇci v skladu s pravili igre in izidi metov. Pri najpreprostejˇsih igrah se igralec vselej premika od starta v eni sami smeri proti cilju. Ko cilj doseˇze, pa se igra zakljuˇci. Taki situaciji bi v teoriji markovskih verig rekli nakljuˇcni sprehod z absorbirajoˇcim stanjem.

Zgled. Imamo preprosto namizno igro z n + 1 polji, oznaˇcenimi po vrsti s ˇstevilkami od 0 do n, kjer ˇstevilka 0 predstavlja ˇstart, ˇstevilka n pa cilj. Pri tej igri meˇcemo kovanec, ˇce vrˇzemo cifro, se premaknemo za eno polje naprej, ˇce vrˇzemo grb, ostanemo na mestu. Zanima nas, kolikˇsno je najmanjˇse ˇstevilo metov, da pridemo na cilj, kolikˇsno je povpreˇcno ˇstevilo metov in kolikˇsna je verjetnost, da pridemo na cilj. Poglejmo si najprej na primeru, ko je n = 3 in meˇcemo poˇsteni kovanec, kjer imamo igralno ploˇsˇco, kot je prikazano na spodnji sliki.

Slika 5: Prikaz igralne ploˇsˇce za n = 3

Moˇzna stranja pri igri so, da smo na poljih0,1,2 ali 3, torej je mnoˇzica stanj enaka S ={0,1,2,3}. Ker se pri igri v primeru cifre premaknemo naprej za eno polje, bo pri n = 3 najmanjˇse ˇstevilo metov, da pridemo do cilja, enako 3. Prehodna matrika bo velikosti 4× 4. Ker meˇcemo poˇsteni kovanec, bo verjetnost premika iz nekega polja in verjetnost, da na nekem polju ostanemo, enaka 0.5. Torej je prehodna matrika P enaka

P =









0 1 2 3

0 0.5 0.5 0 0

1 0 0.5 0.5 0

2 0 0 0.5 0.5

3 0 0 0 1







 .

21

Zanima nas, kolikˇsna je verjetnost, da se igra konˇca po nekem doloˇcenem ˇstevilu korakov, denimo k. Na zaˇcetku smo z verjetnostjo 1 na zaˇcetnem polju 0, zato uporabimo vektoru= (1,0,0,0). Pri mnoˇzenju s potencami matrike P bomo za rezultat vedno dobili prvo vrstico ustrezne matrike. Dobimo

P² =









0.25 0.5 0.25 0 0 0.25 0.5 0.25 0 0 0.25 0.75

0 0 0 1









, . . . , P⁷ =









0.01 0.05 0.16 0.77 0 0.01 0.05 0.94 0 0 0.01 0.99

0 0 0 1







 ,

P⁸ =









0 0.03 0.11 0.86 0 0 0.03 0.96

0 0 0 1

0 0 0 1







 .

Za matriko P^k koeficienti v prvi vrstici pomenijo verjetnosti, da smo po k korakih v stanju i, ˇce smo zaˇceli v 0. Oznaˇcimo s p_k = p^(k)₀₃ verjetnost, da smo po k korakih na cilju. Potem je denimo verjetnost, da smo po sedmih metih na cilju, enaka p₇ = 0.77, verjetnost, da smo po osmih metih na cilju, pa p₈ = 0.86. Njuna razlika doloˇca verjetnost, da smo na cilj priˇsli natanko v osmem koraku. Oznaˇcimo r_k =p_k−pk−1, potem je r₈ = 0.86−0.77 = 0.09.

Podobno smo izraˇcunali ostale vrednosti v tabeli do k = 12. Za veˇcje k so verjetnsti r_k manjˇse od0.01.

k 1 2 3 4 5 6 7 8 9 10 11 12

p_k 0 0 0.13 0.31 0.5 0.66 0.77 0.86 0.91 0.95 0.97 0.98 r_k 0 0 0.13 0.19 0.19 0.16 0.12 0.08 0.06 0.04 0.02 0.01

Tabela 1: Verjetnosti, da v k korakih pridemo na cilj

Ce zˇ Y oznaˇcimo sluˇcajno spremenljivko, ki opisuje verjetnost, da smo na cilj priˇsli v natanko k - tem koraku, potem njeno porazdelitev opisujejo vrednosti rk. Zato lahko s pomoˇcjo zgornje tabele izraˇcunamo pribliˇzek matematiˇcnega upanja te spremenljivke.

E(Y) = 1·0 + 2·0 + 3·0.13 + 4·0.19 +. . .+ 12·0.01 +. . . .

= 5.82.

Povpreˇcno ˇstevilo metov potrebnih za dosego cilja je torej 5.82.

Nalogo lahko posploˇsimo na poljubno ˇstevilo poljn+ 1 in kovanec z verjetnostjo cifre enako p. Na cilj torej pridemo v k - tem koraku, ˇce takrat pade n - ta cifra. To pomeni, da je v prvihk−1metih padlo n−1cifer, v k - tem metu pa spet cifra. ˇCe spet oznaˇcimo zY sluˇcajno spremenljivko, ki opisuje verjetnost, da se igra konˇca v natanko k - tem koraku, potem velja

P(Y =k) =

k−1 n−1

·pⁿ⁻¹·(1−p)^{k−1−(n−1)}·p=

k−1 n−1

pⁿ(1−p)^k−n, 22

saj mora na prvih k−1 mestih pasti n−1 cifer, kar se lahko zgodi na ^k−1_n−1 naˇcinov, vsak posamezen naˇcin pa se zgodi z verjetnostjo pⁿ⁻¹·(1−p)^k−n. To je ravno ena od oblik negativne binomske porazdelitve. Znano je, da je njeno upanje E(Y) = ⁿ_p, glej na primer [9]. Opazimo, da je prejˇsnji pribliˇzek res le pribliˇzek, saj bi bila toˇcna vrednost enaka 6.

Opomba. V tem primeru bi se lahko popolnoma izognili uporabi markovskih verig oziroma matrik, saj znamo verjetnost, da se igra konˇca v k - tem koraku opisati z direktno formulo.

4.2 Hi Ho Cherry O

Hi Ho Cherry O je otroˇska namizna igra za dva, tri ali ˇstiri igralce. Igralci vrtijo kolo z namenom, da bi zbirali ˇceˇsnje. Igra poteka, dokler eden izmed igralcev ne zbere deset ˇceˇsenj. Ta igra je pri nas nekoliko manj znana. Najprej bomo predstavili pravila igre, nato pa zapisali mnoˇzico stanj, ustrezne matrike in diagram.

V tem razdelku izhajamo iz [7].

Slika 6: Namizna igra Hi Ho Cherry O Vir: [3]

4.2.1 Pravila igre

Vsak igralec zaˇcne igro z prazno koˇsaro in desetimi ˇceˇsnjami na svojem dre- vesu. Igralci po vrsti vrtijo kolo, ki je razdeljeno na sedem delov, oznaˇcenih s ˇstevilkami od 1 do 4 in sliˇcicami pes, ptica in prevrnjeno vedro. V skladu z izidom vrtenja mora vsak igralec upoˇstevati naslednja navodila:

23

(i) ˇStevilka 1: Prestavi 1 ˇceˇsnjo iz drevesa v svoje vedro.

(ii) ˇStevilka 2: Prestavi 2 ˇceˇsnji iz drevesa v svoje vedro.

(iii) ˇStevilka 3: Prestavi 3 ˇceˇsnje iz drevesa v svoje vedro.

(iv) ˇStevilka 4: Prestavi 4 ˇceˇsnje iz drevesa v svoje vedro.

(v) Pes: Iz svojega vedra na drevo vrni 2 ˇceˇsnji.

(vi) Ptica: Enako kot pri psu.

(vii) Prevrnjeno vedro: Na drevo vrni vse ˇceˇsnje iz svojega vedra.

V primeru, da na drevesu ni dovolj ˇceˇsenj za izvedbo pravil 1−4, igralec paˇc prestavi toliko ˇceˇsenj, kot jih je na voljo. Podobno ravna v primeru psa ali ptice, ˇce v vedru nima dovolj ˇceˇsenj. Igra se zakljuˇci, ko eden izmed igralcev v vedru nabere vse ˇceˇsnje iz svojega drevesa.

4.2.2 Matematiˇcni opis igre

Opisali bomo situacijo za posameznega igralca. V jeziku markovskih ve- rig bomo najprej podali mnoˇzico stanj. Razliˇcna moˇzna stanja pri igri so, da imamo 0,1,2, . . . oziroma 10 ˇceˇsenj. Torej imamo mnoˇzico stanj S = {0,1,2, . . . ,10}.

Prehodna matrika markovske verige pri igri nam pokaˇze verjetnosti prehoda med razliˇcnimi stanji, torej iz ˇstevila ˇceˇsenj pred vrtenjem kolesa v ˇstevilo ˇceˇsenj po vrtenju kolesa. Pri vrtenju kolesa je moˇznih 7 razliˇcnih izidov, ki so vsi enako verjetni. Denimo, da smo v stanju 0. Potem z verjetnostjo 1/7 pridemo v stanje 1,2,3 ali 4, torej je

p₀₁=p₀₂=p₀₃=p₀₄= 1/7.

Pri izidih pes, ptica ali prevrnjeno vedro pa bomo ostali kar v istem stanju, zato jep00 = 3/7. Petih ˇceˇsenj ali veˇc ne moremo dobiti, zato jep05 =p06 =. . .= 0.

Dobljene vrednosti predstavljajo prvo vrstico matrike. Podobno dobimo ostale vrednosti v naslednjih vrsticah, ko imamo pred vrtenjem kolesa 1,2, . . .oziroma 10 ˇceˇsenj, ki jih zapiˇsemo v matriko P velikosti 11×11

24

P=





































0 1 2 3 4 5 6 7 8 9 10

0 3

7 1 7

1 7

1 7

1

7 0 0 0 0 0 0

1 3

7 0 ¹₇ ¹₇ ¹₇ ¹₇ 0 0 0 0 0

2 3

7 0 0 ¹₇ ¹₇ ¹₇ ¹₇ 0 0 0 0

3 1

7 2

7 0 0 ¹₇ ¹₇ ¹₇ ¹₇ 0 0 0

4 1

7 0 ²₇ 0 0 ¹₇ ¹₇ ¹₇ ¹₇ 0 0

5 1

7 0 0 ²₇ 0 0 ¹₇ ¹₇ ¹₇ ¹₇ 0

6 1

7 0 0 0 ²₇ 0 0 ¹₇ ¹₇ ¹₇ ¹₇

7 1

7 0 0 0 0 ²₇ 0 0 ¹₇ ¹₇ ²₇

8 1

7 0 0 0 0 0 ²₇ 0 0 ¹₇ ³₇

9 1

7 0 0 0 0 0 0 ²₇ 0 0 ⁴₇

10 0 0 0 0 0 0 0 0 0 0 1



































 .

Da zberemo 10 ˇceˇsenj, moramo kolo zavrteti najmanj trikrat. Po dveh kro- gih se igra ne more zakljuˇciti, saj imamo lahko po dveh vrtenjih najveˇc 8 ˇceˇsenj.

Podobno kot pri prejˇsnji igri tudi tu oznaˇcimo s p_k =p^(k)_0A, kjer A predstavlja ˇstevilko 10, verjetnost, da smo pokkorakih na cilju in zr_k =p_k−pk−1. V spo- dnji tabeli je prikazanih nekaj verjetnosti pk in rk, nekatere vmesne vrednosti so zaradi preglednosti izpuˇsˇcene, so pa prikazane na spodnjih dveh stolpiˇcnih diagramih, kjer viˇsine stolpcev prikazujejo verjetnosti za k∈ {1,2, . . . ,40}.

k 1 5 9 13 17 21 25 29 33 37 40

p_k 0 0.15 0.39 0.56 0.68 0.77 0.83 0.88 0.91 0.94 0.95 r_k 0 0.06 0.06 0.04 0.03 0.02 0.01 0.01 0.01 0.01 0 . Tabela 2: Verjetnosti, da vk korakih pridemo na cilj pri igri Hi Ho Cherry O

Slika 8: Verjetnosti r_k zak ∈ {1,2, . . . ,40}

25

Slika 7: Verjetnosti p_k za k∈ {1,2, . . . ,40}

Oznaˇcimo sedaj z X sluˇcajno spremenljivko, ki opisuje verjetnost, da smo na cilj priˇsli v natankok - tem koraku. Njeno porazdelitev opisujejo vrednosti r_k. S pomoˇcjo izraˇcunanih r_k vrednosti za k∈ {1,2, . . . ,40}izraˇcunamo pribliˇzek matematiˇcnega upanja te spremenljivke

E(X) = 1·0 + 2·0 + 3·0.03 + 4·0.06 +. . .+ 39·0.01 + 40·0 .

= 13.14, kar nam pove, da je povpreˇcno ˇstevilo vrtljajev, potrebnih za dosego cilja, 13.14. Ta pribliˇzek je zelo groba ocena povpreˇcnega ˇstevila vrtljajev, potreb- nih za dosego cilja. Avtor [7] je za k vzel vrednosti {1,2, . . . ,100} in dobil pribliˇzek matematiˇcnega upanja, enak 15.8.

Poglejmo si ˇse diagram prehoda med stanji. Od prej vemo, da je razliˇcnih stanj 11. Dve stanji med seboj poveˇzemo, ˇce obstaja verjetnost prehoda med njima in oznaˇcimo moˇzno smer prehoda. Na spodnjem diagramu so oznaˇcene verjetnosti prehoda, kjer ni oznak, je verjetnost prehoda enaka 1/7.

26

Slika 9: Diagram prehodov za igro Hi Ho Cherry O

4.3 Druge igre

V strokovni literaturi so bile s pomoˇcjo markovskih verig opisane tudi druge igre, Kaˇce in lestve, Monopoly, Risk. V tem poglavju bodo na kratko predsta- vljene nekatere ugotovitve in izraˇcuni v zvezi s prvima dvema. Bolj podroben opis in razdelavo Kaˇc in lestev najdemo v [1] in [5], Monopolyja pa v [13] in [2], V tem razdelku izhajamo iz literature [8].

4.3.1 Kaˇce in lestve

Pri namizni igri kaˇce in lestve je igralna ploˇsˇca velikosti 10×10 sestavljena iz 100 kvadratkov, oznaˇcenih po vrsti s ˇstevilkami od 1 do 100, pri ˇcemer je ˇstart zunaj igralne ploˇsˇce (ˇce igralec vrˇze 3, premakne figurico na kvadratek ˇstevilka 3), cilj pa na kvadratku ˇstevilka 100 (ˇce je pozicija igralca na kva- dratku ˇstevilka 97, igro zakljuˇci le, ˇce vrˇze 3). Igra je zanimiva, saj igralna ploˇsˇca vsebuje 10 kaˇc in 9 lestev, ki igralcu bodisi oteˇzijo bodisi olajˇsajo pot do cilja. ˇCe figurica pristane na kaˇcji glavi, igralec zdrsne po kaˇci navzdol do njenega repa, ˇce pa figurica pristane na dnu lestve, se povzpne na vrh le te.

27

Slika 10: Primer igralne ploˇsˇce za igro Kaˇce in lestve Vir: [4]

Pozicije lestev so doloˇcene s parom (a, b), kjer sta a in b natanko doloˇcena.

a doloˇca kvadratek, v katerem je dno lestve, b doloˇca kvadratek, v katerem je vrh lestve. Podobno so pozicije kaˇc doloˇcene s parom (c, d), kjer c doloˇca kvadratek, v katerem je kaˇcja glava in d doloˇca kvadratek, v katerem je kaˇcji rep.

Igro lahko moduliramo z markovskimi verigami, saj je naslednja pozicija fi- gurice na igralni ploˇsˇci odvisna le od trenutne pozicije figurice na igralni ploˇsˇci. ˇCe upoˇstevamo zaˇcetno pozicijo zunaj igralne ploˇsˇce, ter da figurica ne ostane na dnu lestve oziroma na kaˇcji glavi, potem ima markovska veriga 101−(9 + 10) = 82 stanj, ki jih oznaˇcimo z 0,1, . . . ,81. Mnoˇzica stanj za ta primer je torej S ={0,1, . . . ,81}.

V ˇclanku [1] so avtorji s preˇstevanjem razliˇcnih moˇznosti izraˇcunali, da je mi- nimalno ˇstevilo potez, da igralec zakljuˇci igro, enako 7, verjetnost, da igro za- kljuˇci z minimalnim ˇstevilom potez, pa je pribliˇzno enaka 0.006. Avtor ˇclanka navaja tudi priˇcakovano ˇstevilo potez pri igri za doloˇceno ˇstevilo igralcev, kar je navedeno v spodnji tabeli.

28

Stevilo igralcevˇ Priˇcakovano ˇstevilo potez

1 39.2

2 26.3

3 21.7

4 19.3

Tabela 3: Povpreˇcno ˇstevilo potez glede na ˇstevilo igralcev 4.3.2 Monopoly

Slika 11: Primer igralne ploˇsˇce za igro Monopoly Vir: [15]

Avtor ˇclanka [8] navaja, da bi bilo pri Monopolyju predvsem dobro vedeti, koliko ˇcasa bo igralec potreboval, da bo pristal na doloˇcenem ozemlju, saj si s tem lahko pomaga pri oblikovanju strategije igranja. Preden zaˇcnemo z raˇcunanjem verjetnosti, moramo premisliti razliˇcne moˇznosti. Igralna ploˇsˇca pri Monopolyju vsebuje 40 polj, eno izmed njih pa je ”Pojdi v zapor!”, na katerem se ne ostane po zakljuˇcenem metu kock. Polje, kjer je ”Zapor”, je lahko obiskano na dva razliˇcna naˇcina, in sicer, da je igralec v zaporu ali samo na obisku. Torej imamo skupno 40 razliˇcnih stanj.

Vendar Monopolyja ne moremo modelirati kot stacionarno markovsko verigo s 40 stanji. Problem nastane, ko igralec trikrat zaporedoma na obeh kockah vrˇze enako ˇstevilo pik, saj mora v tem primeru v zapor (tu naslednja pozicija igralca ni odvisna le od trenutne pozicije). Da se izognemo temu problemu, lahko vsa polja razdelimo na tri dele, in sicer polje, na katerem pristanemo, brez da bi vrgli enako ˇstevilo pik na kockah, polje, na katerem pristanemo, ko smo enkrat vrgli enako ˇstevilo pik na kockah in polje, na katerem pristanemo, ko smo dvakrat vrgli enako ˇstevilo pik na kockah.

29

Eden izmed problemov, na katerega naletimo, je tudi zapor. Pri markovskih verigah se ne moremo prosto odloˇcati, moramo nekoliko prilagoditi pravila igre:

(i) lahko ostanemo v zaporu, dokler lahko poskuˇsamo vreˇci enako ˇstevilo pik na obeh kockah (najveˇc trikrat),

(ii) plaˇcamo in takoj odidemo iz zapora.

Ce se igralec odloˇˇ ci, da bo ostal v zaporu, lahko modeliramo zapor na tri sta- nja, in sicer v zaporu brez poskusa meta za enako ˇstevilo pik na kockah, v zaporu z enim poskusom meta za enako ˇstevilo pik na kockah in v zaporu z dvema poskusoma meta za enako ˇstevilo pik na kockah. Po tem imamo sku- paj 120 stanj. ˇCe se igralec odloˇci, da bo takoj zapustil zapor, potem zapor modeliramo na eno stanje in imamo skupaj 118 stanj. ˇCe se ˇzelimo drˇzati teh dveh prilagojenih pravil, moramo iz igre odstaniti kartici, s katerima gremo lahko brezplaˇcno iz zapora. Eden manj opaznih problemov je jemanje kartic priloˇznosti in drˇzavne blagajne. Ker je jemanje kartic iz vrha in odlaganje ˇze uporabljenih na dno kupˇcka nestacionarno, je ena izmed reˇsitev, da vsakih ko kartico uporabimo, kupˇcek premeˇsamo.

V reviji [2] avtorja med drugim podata vse izraˇcune verjetnosti za razliˇcna stanja zapora glede na predhodno pozicijo.

30

Literatura

[1] Althoen, S.C., King, L., Schilling, K. (1993). How long is a game of Snakes and Ladders?. Mathematical Gazette: Volume 77 Issue 478.

[2] Ash, R., Bishop, R. (1972).Monopoly as a Markov Process. Mathematich Magazine. 45 : 26−29.

[3] BYU Mathematics Department. (2010). Pridobljeno s https://math.

byu.edu/~jeffh/mathematics/games/cherry/cherry.html

[4] Callcentrehelper. (2017) Pridobljeno s https://www.

callcentrehelper.com/snakes-and-ladders-call-centre-game-template-20235.

htm.

[5] Daykin, D. E., Jeacocke, J. E., Neal, D. G. (1967). Markov Chains And Snakes and Ladders. Mathematical Gazette: Volume 51 Issue 378.

[6] Durret, R. (2009). Elementary probability for applications. New York : Cambridge University Press.

[7] Humpherys, J. (2010). Hi Ho Cherry O. Pridobljeno s https://math.

byu.edu/~jeffh/mathematics/games/cherry/cherry.html.

[8] Johnson, R. W. (2003). Using games to teach markov chains. Primus:

13 : 4,337−348.

[9] Kuzman, B.(2017). Verjetnostni raˇcun in statistika, Zapiski predavanj 2016/2017, rokopis. Ljubljana: PeF.

[10] Lay, D. C. (2012). Linear Algebra and Its Applications. Cambridge:

Pearson.

[11] Lipschutz, S. (1998). Schaum’s Outline of Theory and Problems of Pro- bability. New York: McGraw-Hill.

[12] Malniˇc, A. (2016). Osnove linearne algebre, Zapiski predavanj. Lju- bljana: PeF.

[13] Murrel, P. (1999).The Statistics of Monopoly. Chance. 12(4) : 36−40.

[14] ˇSparl, P. (2013). Verjetnostni raˇcun in statistika, Zapiski predavanj.

Ljubljana: PeF.

[15] Wikipedia. (2009). Pridobljeno s https://en.wikipedia.org/wiki/

File:German_Monopoly_board_in_the_middle_of_a_game.jpg

31