Eksempler på Markov -kjeder - Examples of Markov chains

Denne artikkelen inneholder eksempler på Markov -kjeder og Markov -prosesser i aksjon.

Alle eksemplene er i det tellbare statlige rommet . For en oversikt over Markov -kjeder i generelt statlig rom, se Markov -kjeder på et målbart statlig rom .

Diskret tid

Brettspill spilt med terninger

Et spill med slanger og stiger eller et annet spill hvis trekk helt og holdent bestemmes av terninger, er en Markov -kjede, en absorberende Markov -kjede . Dette er i kontrast til kortspill som blackjack , der kortene representerer et 'minne' om tidligere trekk. For å se forskjellen, vurder sannsynligheten for en bestemt hendelse i spillet. I de ovennevnte terningspillene er det eneste som teller den nåværende tilstanden til brettet. Den neste tilstanden på brettet avhenger av den nåværende tilstanden og neste terningkast. Det avhenger ikke av hvordan ting kom til sin nåværende tilstand. I et spill som blackjack kan en spiller få en fordel ved å huske hvilke kort som allerede er vist (og dermed hvilke kort som ikke lenger er i kortstokken), så neste tilstand (eller hånd) i spillet er ikke uavhengig av tidligere stater.

Tilfeldige gå Markov -kjeder

En senter-partisk tilfeldig tur

Tenk på en tilfeldig spasertur på tallinjen der posisjonen (kall det x ) for hvert trinn kan endres med +1 (til høyre) eller -1 (til venstre) med sannsynligheter:

{\ displaystyle P _ {\ mathrm {move ~ left}} = {\ dfrac {1} {2}}+{\ dfrac {1} {2}} \ left ({\ dfrac {x} {c+| x |} }\Ikke sant)}

{\ displaystyle P _ {\ mathrm {move ~ right}} = 1-P _ {\ mathrm {move ~ left}}}

(hvor c er en konstant større enn 0)

For eksempel, hvis konstanten, c , er lik 1, er sannsynligheten for et trekk til venstre i posisjonene x = −2, −1,0,1,2 gitt av henholdsvis. Den tilfeldige turen har en sentrerende effekt som svekkes når c øker. ${\ displaystyle {\ dfrac {1} {6}}, {\ dfrac {1} {4}}, {\ dfrac {1} {2}}, {\ dfrac {3} {4}}, {\ dfrac {5} {6}}}$

Siden sannsynlighetene bare avhenger av den nåværende posisjonen (verdien av x ) og ikke av noen tidligere posisjoner, tilfredsstiller denne partiske tilfeldige turen definisjonen av en Markov -kjede.

Gambling

Anta at du starter med $ 10, og du satser $ 1 på et uendelig, rettferdig myntkast på ubestemt tid, eller til du mister alle pengene dine. Hvis representerer antall dollar du har etter n kast, med , så er sekvensen en Markov -prosess. Hvis jeg vet at du har $ 12 nå, ville det være forventet at du med like odds enten vil ha $ 11 eller $ 13 etter neste kast. Dette gjetningen forbedres ikke av den ekstra kunnskapen at du begynte med $ 10, deretter gikk opp til $ 11, ned til $ 10, opptil $ 11 og deretter til $ 12. Det faktum at gjetningen ikke forbedres av kunnskapen om tidligere kast, viser Markov -eiendommen , den hukommelsesløse egenskapen til en stokastisk prosess. ${\ displaystyle X_ {n}}$ ${\ displaystyle X_ {0} = 10}$ ${\ displaystyle \ {X_ {n}: n \ in \ mathbb {N} \}}$

En enkel værmodell

Sannsynligheten for værforhold (modellert som enten regnfull eller solrik), gitt været dagen før, kan representeres av en overgangsmatrise :

{\ displaystyle P = {\ begin {bmatrix} 0.9 & 0.1 \\ 0.5 & 0.5 \ end {bmatrix}}}

Matrisen P representerer værmodellen der en solskinnsdag er 90% sannsynlig å bli fulgt av en ny solskinnsdag, og en regnværsdag er 50% sannsynlig å bli fulgt av en annen regnværsdag. Kolonnene kan merkes som "solrike" og "regnfulle", og radene kan merkes i samme rekkefølge.

Matrisen ovenfor som en graf.

( P ) _ij er sannsynligheten for at hvis en gitt dag er av type i , vil den bli fulgt av en dag av type j .

Legg merke til at radene med P summerer til 1: dette er fordi P er en stokastisk matrise .

Forutsier været

Været på dag 0 (i dag) er kjent for å være sol. Dette er representert ved en initialtilstandsvektor der "solrik" oppføring er 100%, og "regnfull" oppføring er 0%:

{\ displaystyle \ mathbf {x} ^{(0)} = {\ begin {bmatrix} 1 og 0 \ end {bmatrix}}}

Været på dag 1 (i morgen) kan forutsies ved å multiplisere tilstandsvektoren fra dag 0 med overgangsmatrisen:

{\ displaystyle \ mathbf {x} ^{(1)} = \ mathbf {x} ^{(0)} P = {\ begin {bmatrix} 1 & 0 \ end {bmatrix}} {\ begin {bmatrix} 0.9 & 0. 1 \\ 0.5 & 0.5 \ end {bmatrix}} = {\ begin {bmatrix} 0.9 & 0.1 \ end {bmatrix}}}

Dermed er det en 90% sjanse for at dag 1 også vil være solrik.

Været på dag 2 (i overmorgen) kan forutsies på samme måte, fra tilstandsvektoren vi beregnet for dag 1:

{\ displaystyle \ mathbf {x} ^{(2)} = \ mathbf {x} ^{(1)} P = \ mathbf {x} ^{(0)} P ^{2} = {\ begin {bmatrix } 1 & 0 \ end {bmatrix}} {\ begin {bmatrix} 0.9 & 0.1 \\ 0.5 & 0.5 \ end {bmatrix}}^{2} = {\ begin {bmatrix} 0.86 & 0.14 \ end {bmatrix} }}

eller

{\ displaystyle \ mathbf {x} ^{(2)} = \ mathbf {x} ^{(1)} P = {\ begin {bmatrix} 0.9 & 0.1 \ end {bmatrix}} {\ begin {bmatrix} 0.9 & 0.1 \\ 0.5 & 0.5 \ end {bmatrix}} = {\ begin {bmatrix} 0.86 & 0.14 \ end {bmatrix}}}

Generelle regler for dag n er:

{\ displaystyle \ mathbf {x} ^{(n)} = \ mathbf {x} ^{(n-1)} P}

{\ displaystyle \ mathbf {x} ^{(n)} = \ mathbf {x} ^{(0)} P ^{n}}

Værets jevne tilstand

I dette eksemplet endres spådommer for været på fjerntliggende dager mindre og mindre på hver påfølgende dag og har en tendens til en steady state -vektor . Denne vektoren representerer sannsynligheten for sol og regnvær på alle dager, og er uavhengig av det opprinnelige været.

Steady state -vektoren er definert som:

{\ displaystyle \ mathbf {q} = \ lim _ {n \ to \ infty} \ mathbf {x} ^{(n)}}

men konvergerer til en strengt positiv vektor bare hvis P er en vanlig overgangsmatrise (det vil si at det er minst én P ⁿ med alle ikke-null oppføringer).

Siden q er uavhengig av begynnelsesbetingelser, må det være uforandret når de er transformert med P . Dette gjør det til en egenvektor (med egenverdi 1), og betyr at det kan være avledet fra P .

I lekmanns termer er steady-state-vektoren vektoren som, når vi multipliserer den med P , får vi nøyaktig samme vektor tilbake. For væreksemplet kan vi bruke dette til å sette opp en matriseligning:

{\ displaystyle {\ begin {align} P & = {\ begin {bmatrix} 0.9 & 0.1 \\ 0.5 & 0.5 \ end {bmatrix}} \\\ mathbf {q} P & = \ mathbf {q} && {\ tekst {(}} \ mathbf {q} {\ text {er uendret av}} P {\ text {.)}} \\ & = \ mathbf {q} I \\\ mathbf {q} (PI) & = \ mathbf {0} \\\ mathbf {q} \ left ({\ begin {bmatrix} 0.9 & 0.1 \\ 0.5 & 0.5 \ end {bmatrix}}-{\ begin {bmatrix} 1 & 0 \\ 0 & 1 \ end {bmatrix}} \ right) & = \ mathbf {0} \\\ mathbf {q} {\ begin {bmatrix} -0.1 & 0.1 \\ 0.5 & -0.5 \ end {bmatrix}} & = \ mathbf {0 } \\ {\ begin {bmatrix} q_ {1} & q_ {2} \ end {bmatrix}} {\ begin {bmatrix} -0.1 & 0.1 \\ 0.5 & -0.5 \ end {bmatrix}} & = {\ begynn {bmatrix} 0 & 0 \ end {bmatrix}} \\-0.1q_ {1}+0.5q_ {2} & = 0 \ end {align}}}

og siden de er en sannsynlighetsvektor vet vi det

{\ displaystyle q_ {1}+q_ {2} = 1.}

Ved å løse dette paret av samtidige ligninger får steady state -vektoren:

{\ displaystyle {\ begin {bmatrix} q_ {1} & q_ {2} \ end {bmatrix}} = {\ begin {bmatrix} 0.833 & 0.167 \ end {bmatrix}}}

Som konklusjon, på lang sikt er om lag 83,3% av dagene sol. Det er viktig å innse at ikke alle Markov -prosesser har en steady state -vektor. Spesielt må overgangsmatrisen være vanlig . Ellers vil tilstandsvektorene svinge over tid uten å konvergere.

Aksjemarked

Ved å bruke en rettet graf er sannsynligheten for de mulige tilstandene et hypotetisk aksjemarked kan vise representert. Matrisen til venstre viser hvordan sannsynligheter tilsvarende forskjellige tilstander kan ordnes i matriseform.

Et tilstandsdiagram for et enkelt eksempel er vist i figuren til høyre, ved hjelp av en rettet graf for å vise tilstandsovergangene . Statene representerer om et hypotetisk aksjemarked viser et oksemarked , bjørnmarked eller stillestående markedstrend i løpet av en gitt uke. I følge figuren blir en okseuke fulgt av en ny okseuke 90% av tiden, en bjørnuke 7,5% av tiden og en stillestående uke de andre 2,5% av tiden. Merking av tilstandsrommet {1 = okse, 2 = bjørn, 3 = stillestående} overgangsmatrisen for dette eksemplet er

{\ displaystyle P = {\ begin {bmatrix} 0.9 & 0.075 & 0.025 \\ 0.15 & 0.8 & 0.05 \\ 0.25 & 0.25 & 0.5 \ end {bmatrix}}.}

Den fordeling over tilstander kan skrives som en stokastisk rad vektor $x$ med forholdet $x (n + 1) = x (n) P$ . Så hvis systemet på tidspunktet $n$ er i tilstand $x (n)$ , så er tre tidsperioder senere, på tidspunktet $n + 3$ fordelingen

{\ displaystyle {\ begynne {justert} x^{(n+3)} & = x^{(n+2)} P = \ venstre (x^{(n+1)} P \ høyre) P \\ \\ & = x^{(n+1)} P^{2} = \ venstre (x^{(n)} P \ høyre) P^{2} \\ & = x^{(n)} P ^{3} \\\ ende {justert}}}

Markov Chains prediksjon på 3 diskrete trinn basert på overgangsmatrisen fra eksemplet til venstre.

Spesielt hvis systemet på tidspunkt $n$ er i tilstand 2 (bjørn), er fordelingen på tidspunktet $n + 3$

{\ displaystyle {\ begin {align} x^{(n+3)} & = {\ begin {bmatrix} 0 & 1 & 0 \ end {bmatrix}} {\ begin {bmatrix} 0.9 & 0.075 & 0.025 \\ 0.15 & 0. 8 & 0.05 \\ 0.25 & 0.25 & 0.5 \ end {bmatrix}}^{3} \\ [5pt] & = {\ begin {bmatrix} 0 & 1 & 0 \ end {bmatrix}} {\ begin {bmatrix} 0.7745 & 0. 17875 & 0.04675 \\ 0.3575 & 0.56825 & 0.07425 \\ 0.4675 & 0.37125 & 0.16125 \\\ end {bmatrix}} \\ [5pt] & = {\ begin {bmatrix} 0.3575 & 0.56825 & 0.07425 \ end {bmatrix }}. \ end {align}}}

Markov kjeder prediksjon på 50 diskrete trinn. Igjen brukes overgangsmatrisen fra venstre.

Ved å bruke overgangsmatrisen er det for eksempel mulig å beregne den langsiktige brøkdelen av uker der markedet er stillestående, eller gjennomsnittlig antall uker det vil ta å gå fra et stillestående til et oksemarked. Ved bruk av overgangssannsynligheter indikerer steady-state sannsynligheter at 62,5% av ukene vil være i et oksemarked, 31,25% av ukene vil være i et bjørnemarked og 6,25% av ukene vil være stillestående siden:

{\ displaystyle \ lim _ {N \ to \ infty} \, P^{N} = {\ begin {bmatrix} 0.625 & 0.3125 & 0.0625 \\ 0.625 & 0.3125 & 0.0625 \\ 0.625 & 0.3125 & 0.0625 \ slutt {bmatrix}}}

En grundig utvikling og mange eksempler finnes i den elektroniske monografien Meyn & Tweedie 2005.

En finite-state-maskin kan brukes som en representasjon av en Markov-kjede. Forutsatt en sekvens av uavhengige og identisk fordelte inngangssignaler (for eksempel symboler fra et binært alfabet valgt med myntkast), hvis maskinen er i tilstand y på tidspunktet n , så sannsynligheten for at den beveger seg til tilstand x på tidspunktet n + 1 avhenger bare av gjeldende tilstand.

Kontinuerlig tid

En fødsel -død prosess

Hvis en popper hundre popcornkjerner i en ovn, og hver kjerne dukker opp på et uavhengig eksponensielt fordelt tidspunkt, ville dette være en kontinuerlig Markov-prosess . Hvis angir antall kjerner som har dukket opp til tid t , kan problemet defineres som å finne antall kjerner som vil dukke opp senere. Det eneste man trenger å vite er antall kjerner som har dukket opp før tiden "t". Det er ikke nødvendig å vite når de dukket opp, så å vite for tidligere ganger "t" er ikke relevant. ${\ displaystyle X_ {t}}$ ${\ displaystyle X_ {t}}$

Prosessen beskrevet her er en tilnærming til en Poisson -punktprosess - Poisson -prosesser er også Markov -prosesser.

Se også

Referanser

^ Øksendal, BK (Bernt Karsten), 1945- (2003). Stokastiske differensialligninger: en introduksjon med applikasjoner (6. utg.). Berlin: Springer. ISBN 3540047581. OCLC 52203046 .CS1 -vedlikehold: flere navn: forfatterliste ( lenke )
^ Gagniuc, Paul A. (2017). Markov Chains: From Theory to Implementation and Experimentation . USA, NJ: John Wiley & Sons. s. 1–235. ISBN 978-1-119-38755-8.
^ ^a ^b ^c Van Kampen, NG (2007). Stokastiske prosesser i fysikk og kjemi . NL: Nord -Holland Elsevier. s. 73 –95. ISBN 978-0-444-52965-7.
^ ^a ^b ^c ^d Van Kampen, NG (2007). Stokastiske prosesser i fysikk og kjemi . NL: Nord -Holland Elsevier. s. 73 –95. ISBN 978-0-444-52965-7.
^ "Går stabil (tilstand) med Markov -prosesser" . Bloomington -veiledere.
^ ^a ^b Gagniuc, Paul A. (2017). Markov -kjeder: fra teori til implementering og eksperimentering . Hoboken, NJ: John Wiley & Sons. s. 131–163. ISBN 9781119387572. OCLC 982373850 .
^ SP Meyn og RL Tweedie, 2005. Markov-kjeder og stokastisk stabilitet arkivert 2013-09-03 på Wayback Machine

Eksterne linker

Monopol som en Markov -kjede

[:3-1] Øksendal, BK (Bernt Karsten), 1945- (2003). Stokastiske differensialligninger: en introduksjon med applikasjoner (6. utg.). Berlin: Springer. ISBN 3540047581. OCLC 52203046 .CS1 -vedlikehold: flere navn: forfatterliste ( lenke )

[:02-2] Gagniuc, Paul A. (2017). Markov Chains: From Theory to Implementation and Experimentation . USA, NJ: John Wiley & Sons. s. 1–235. ISBN 978-1-119-38755-8.

[:0-3] Van Kampen, NG (2007). Stokastiske prosesser i fysikk og kjemi . NL: Nord -Holland Elsevier. s. 73 –95. ISBN 978-0-444-52965-7.

[:1-4] Van Kampen, NG (2007). Stokastiske prosesser i fysikk og kjemi . NL: Nord -Holland Elsevier. s. 73 –95. ISBN 978-0-444-52965-7.

[5] "Går stabil (tilstand) med Markov -prosesser" . Bloomington -veiledere.

[:2-6] Gagniuc, Paul A. (2017). Markov -kjeder: fra teori til implementering og eksperimentering . Hoboken, NJ: John Wiley & Sons. s. 131–163. ISBN 9781119387572. OCLC 982373850 .

[MCSS-7] SP Meyn og RL Tweedie, 2005. Markov-kjeder og stokastisk stabilitet arkivert 2013-09-03 på Wayback Machine

Languages

In other projects