Korisnički Kontrolni Panel
Pogledajte svoj profil
Pogledajte svoje postove
ČPP
Prijavite se

Matematički forum na kojem možete da diskutujete o raznim matematičkim oblastima, pomognete drugima oko rešavanja zadataka, a i da dobijete pomoć kada vam zatreba


















Index stranica OSTALE MATEMATIČKE OBLASTI VEROVATNOĆA

Lanci Markova

[inlmath]P\left(A_k/B\right)P\left(B\right)=P\left(B/A_k\right)P\left(A_k\right)[/inlmath]

Lanci Markova

Postod desideri » Sreda, 16. Mart 2016, 15:22

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! :)
Korisnikov avatar
Zaslužni forumaš
 
Postovi: 1542
Lokacija: Beograd
Zahvalio se: 1097 puta
Pohvaljen: 864 puta

Sharuj ovu temu na:

Share on Facebook Facebook Share on Twitter Twitter Share on MySpace MySpace Share on Google+ Google+

Re: Lanci Markova

Postod Onomatopeja » Sreda, 16. Mart 2016, 22:45

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).
 
Postovi: 613
Zahvalio se: 15 puta
Pohvaljen: 588 puta

  • +2

Re: Lanci Markova

Postod desideri » Ponedeljak, 21. Mart 2016, 22:31

Pre svega thanks Onomatopeji što se za ovo zainteresovao i sve tačno rešio na originalan način. :thumbup:
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]
Korisnikov avatar
Zaslužni forumaš
 
Postovi: 1542
Lokacija: Beograd
Zahvalio se: 1097 puta
Pohvaljen: 864 puta

  • +1

Re: Lanci Markova

Postod Daniel » Sreda, 23. Mart 2016, 09:28

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]
I do not fear death. I had been dead for billions and billions of years before I was born, and had not suffered the slightest inconvenience from it. – Mark Twain
Korisnikov avatar
Daniel  OFFLINE
Administrator
 
Postovi: 9300
Lokacija: Beograd
Zahvalio se: 5151 puta
Pohvaljen: 4951 puta

Re: Lanci Markova

Postod desideri » Sreda, 23. Mart 2016, 18:51

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 :thumbup: 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?
Korisnikov avatar
Zaslužni forumaš
 
Postovi: 1542
Lokacija: Beograd
Zahvalio se: 1097 puta
Pohvaljen: 864 puta


Povratak na VEROVATNOĆA

Ko je OnLine

Korisnici koji su trenutno na forumu: Nema registrovanih korisnika i 43 gostiju


Index stranicaTimObriši sve kolačiće boarda
Danas je Četvrtak, 28. Mart 2024, 20:44 • Sva vremena su u UTC + 1 sat
Pokreće ga phpBB® Forum Software © phpBB Group
Prevod – www.CyberCom.rs