MATEMANIJA

U ovoj temi razmatraju se lanci Markova. Ruski matematičar Andrej Markov je dao fundamentalan matematički doprinos diskretnim slučajnim procesima s diskretnim vremenom.

Moja namera je da zainteresujem naše korisnike za ovu izuzetno (po meni) zanimljivu oblast teorije verovatnoće.
Napisaću i tutorijal naravno teorijski s primerima ali prvo neka mi neko reši ovaj zadatak, koliko da vidim da ima nekog odziva:

Aca, Mirko i Ceca dobacuju se loptom. Na početku je lopta bila kod Mirka. U toku igre Aca uvek dobacuje loptu Mirku, Mirko uvek dobacuje loptu Ceci dok Ceca s podjednakom verovatnoćom dobacuje loptu Aci ili Mirku. Kolika je verovatnoća da će lopta posle [inlmath]4[/inlmath] dobacivanja biti kod Cece?

p.s. Rešite kako kod želite, no ja ću ga svakako rešiti banalnim množenjem matrica, po teoretskim postavkama Markova. I to za tren oka!

Resenje je [inlmath]\displaystyle\frac{1}{2}[/inlmath]. Naime, ja nisam koristio lance Markova (premda sam cuo za njih, ali samo cuo), vec sam pravio stablo (drvo, kako god) i onda samo prebrojim koliko mi se puta pojavila Ceca u poslednjem (cetvrtom) nivou. Konkretno ovde iz prilozenog stabla (mada bi ove neke crtice trebalo da budu ukoso, ali se nisam zezao sa time) dobijamo da imamo dva [inlmath]C[/inlmath] na cetiri mesta, tj. da je verovatnoca [inlmath]\displaystyle\frac{2}{4}=\frac{1}{2}[/inlmath]. Oznake [inlmath]M=\text{Mirko}[/inlmath], [inlmath]A=\text{Aco}[/inlmath], [inlmath]C=\text{Ceca}[/inlmath] su verujem jasne.

Takodje, kada sam imao grananje kod [inlmath]C[/inlmath] drugi put na [inlmath]M[/inlmath] i [inlmath]A[/inlmath], onda sam i kod [inlmath]M[/inlmath] (sa tog istog nivoa, tj. treceg) granao sa dva [inlmath]C[/inlmath], da bi mi svaka grana imala istu tezinu (da nisam to uradio, dobio bih u poslednjem nivou [inlmath]M[/inlmath], [inlmath]A[/inlmath], [inlmath]C[/inlmath], odakle bih naivno rekao da je resenje [inlmath]\displaystyle\frac{1}{3}[/inlmath] (sto nije tacno i sto se dalo za ocekivati da nije, jer onda bi se ispostavilo da nam informacija ko kome dodaje nicemu ne koristi).

Kôd: Obeleži sve

                                    M
                                    |
                                    C
                     |                                 |
                     M                                 A
                     |                                 |
                     C                                 M
             |             |                    |              |
             M             A                    C              C

Naravno, posto smo vec poceli da granamo svaki element po dva puta (jer ce se u svakom narednom koraku pojaviti jedno [inlmath]C[/inlmath], a ono se grana dva puta, a time i ostali), to cemo u narednom koraku imati [inlmath]8[/inlmath] grana, pa u narednom [inlmath]16[/inlmath], i tako dalje. Hocu reci, sam algoritam se dosta usloznjava za samu vecu primenu (evo ja sam izracunao i da posle [inlmath]7[/inlmath] koraka (a i [inlmath]8[/inlmath], dobije se isti rezultat) je verovatnoca [inlmath]\displaystyle\frac{12}{32}=\frac{3}{8}[/inlmath] (za osam se dobije [inlmath]\displaystyle\frac{24}{64}[/inlmath]), a vec za [inlmath]9[/inlmath] me je mrzelo).

Pre svega thanks Onomatopeji što se za ovo zainteresovao i sve tačno rešio na originalan način.
E sada i po postavkama Markova da rešimo zadatak:
Najpre se postavlja matrica verovatnoća prelaza za jedan korak tj. jedno dobacivanje:
[dispmath]P=\begin{bmatrix}
0 & 1 & 0\\
0 & 0 & 1\\
\frac{1}{2} & \frac{1}{2 } & 0
\end{bmatrix}[/dispmath]
Da pojasnim ovo:
Na primer element matrice [inlmath]P[/inlmath] koji je u trećem redu matrice i prvi je s leve strane predstavlja verovatnoću da Ceca dobaci loptu Aci.
Isti je sistem zaključivanja tj. postavke verovatnoća za sve elemente ove matrice. Ovo je stohastička matrica, što znači da je zbir svake njene vrste ili reda jednak jedinici.

Dalje se definiše početni vektor verovatnoća:
[dispmath]P(0)=\begin{bmatrix}
0 & 1 & 0
\end{bmatrix}[/dispmath]
Ovo znači da je lopta na početku bila kod Mirka, koji je na drugom mestu. U vektoru, naravno.

Verovatnoće stanja nakon prvog koraka, drugog koraka itd. dobijaju se prostim množenjem matrica:
[dispmath]P(1)=P(0)\cdot P=\begin{bmatrix}
0 & 0 & 1
\end{bmatrix}[/dispmath]
Zar ovo nije logično: na početku je lopta bila kod Mirka, a Mirko je onda bacio loptu Ceci. Pa je sada lopta kod Cece.

Idemo dalje:
[dispmath]P(2)=P(1)\cdot P=\begin{bmatrix}
\frac{1}{2} & \frac{1}{2} & 0
\end{bmatrix}[/dispmath]
Ovako možemo množiti matrice i ručno i softverski do bilo kog koraka, no evo vam još jedne genijalne postavke Markova:
Nakon beskonačno dugog vremena verovatnoće nalaženja po stanjima nalaze se iz matrične jednačine:
[dispmath]t\cdot P=t[/dispmath]
Ovde je:
[dispmath]t=\begin{bmatrix}
x & y & z
\end{bmatrix}[/dispmath]
Pri čemu obavezno važi normirajući uslov: [inlmath]x+y+z=1[/inlmath]

desideri je napisao:Nakon beskonačno dugog vremena verovatnoće nalaženja po stanjima nalaze se iz matrične jednačine:
[dispmath]t\cdot P=t[/dispmath]

Ako sam dobro skontao sve ovo, do citirane jednačine se dolazi na osnovu rekurentne veze
[dispmath]P\left(n\right)=P\left(n-1\right)\cdot P[/dispmath]
pa kada „limesujemo“ obe strane,
[dispmath]\lim_{n\to\infty}P\left(n\right)=\lim_{n\to\infty}\bigl(P\left(n-1\right)\cdot P\bigr)[/dispmath][dispmath]\lim_{n\to\infty}P\left(n\right)=\left(\lim_{n\to\infty}P\left(n-1\right)\right)\cdot P[/dispmath]
ako [inlmath]\lim\limits_{n\to\infty}P\left(n\right)[/inlmath] označimo sa [inlmath]t[/inlmath], tada će važiti i [inlmath]\lim\limits_{n\to\infty}P\left(n-1\right)=t[/inlmath]:
[dispmath]t=t\cdot P[/dispmath]
što je, naravno, ekvivalentno citiranoj jednačini [inlmath]t\cdot P=t[/inlmath]. Za ovaj primer s Mirkom, Acom i Cecom dobiju se vrednosti
[dispmath]t=\begin{bmatrix}
x & y & z
\end{bmatrix}=\begin{bmatrix}
\displaystyle\frac{1}{5} & \displaystyle\frac{2}{5} & \displaystyle\frac{2}{5}
\end{bmatrix}[/dispmath]
što znači verovatnoću od [inlmath]\displaystyle\frac{1}{5}[/inlmath] da će posle beskonačno dugog vremena lopta biti kod Ace, verovatnoću od [inlmath]\displaystyle\frac{2}{5}[/inlmath] da će posle beskonačno dugog vremena lopta biti kod Mirka i verovatnoću od [inlmath]\displaystyle\frac{2}{5}[/inlmath] da će posle beskonačno dugog vremena lopta biti kod Cece.

Što možemo i proveriti:
[dispmath]t\cdot P=\begin{bmatrix}
\displaystyle\frac{1}{5} & \displaystyle\frac{2}{5} & \displaystyle\frac{2}{5}
\end{bmatrix}\cdot\begin{bmatrix} 0 & 1 & 0\\
0 & 0 & 1\\
\displaystyle\frac{1}{2} & \displaystyle\frac{1}{2 } & 0
\end{bmatrix}=\begin{bmatrix}
\displaystyle\frac{\cancel2}{5}\cdot\frac{1}{\cancel2} & \displaystyle\frac{1}{5}\cdot1+\frac{\cancel2}{5}\cdot\frac{1}{\cancel2} & \displaystyle\frac{2}{5}\cdot1
\end{bmatrix}=\begin{bmatrix}
\displaystyle\frac{1}{5} & \displaystyle\frac{2}{5} & \displaystyle\frac{2}{5}
\end{bmatrix}=t[/dispmath]

Markov je ovo:
[dispmath]t \cdot P=t[/dispmath]
dokazivao koristeći osobinu regularnosti matrice [inlmath]P^n[/inlmath] koja se opet posebno dokazuje.
Ali zaista je ispravan i Danielov (originalan!) dokaz iz prethodnog posta. Ostaje samo za Daniela.
Pošto su se ljudi zainteresovali za Lance Markova (na moju žalost samo kolege iz Moderatorskog tima i poneki gost a ja bih voleo i ostale naše članove da vidim, ali šta ću ) zadajem i sledeći zadatak:

U prvoj urni su tri bele kuglice a u drugoj dve crne kuglice. Svake sekunde iz svake od ove dve urne izvadi se istovremeno po jedna kuglica i zamene im se mesta, tj. stave se u suprotne urne. Kolika je verovatnoća da će posle četiri sekunde u prvoj urni biti dve bele i jedna crna kuglica?