Exempel på Markov-kedjor

Den här artikeln innehåller exempel på Markov-kedjor och Markov-processer i aktion.

Alla exempel finns i det räknebara tillståndsutrymmet . För en översikt över Markov-kedjor i allmänt tillståndsutrymme, se Markov-kedjor på ett mätbart tillståndsutrymme .

Diskret tid

Brädspel spelas med tärningar

Ett spel med ormar och stegar eller något annat spel vars drag helt och hållet bestäms av tärningar är en Markov-kedja, verkligen en absorberande Markov-kedja . Detta till skillnad från kortspel som blackjack , där korten representerar ett "minne" av tidigare drag. För att se skillnaden, överväg sannolikheten för en viss händelse i spelet. I de ovan nämnda tärningsspelen är det enda som spelar roll brädets nuvarande tillstånd. Nästa tillstånd på brädet beror på det aktuella tillståndet och nästa tärningskast. Det beror inte på hur saker och ting kommit till sitt nuvarande tillstånd. I ett spel som blackjack kan en spelare få en fördel genom att komma ihåg vilka kort som redan har visats (och därmed vilka kort som inte längre finns i kortleken), så nästa tillstånd (eller hand) i spelet är inte oberoende av tidigare stater.

Random walk Markov-kedjor

En centruminriktad random walk

Överväg en slumpmässig promenad på tallinjen där positionen (kalla den x ) vid varje steg kan ändras med +1 (till höger) eller −1 (till vänster) med sannolikheter:

P_{\mathrm {move~left} }={\dfrac {1}{2}}+{\ dfrac {1}{2}}\left({\dfrac {x}{c+|x|}}\right)

P_{\mathrm {move~right} }=1-P_{\mathrm {move~left} }

(där c är en konstant större än 0)

Till exempel, om konstanten, c , är lika med 1, ges sannolikheterna för en förflyttning till vänster vid positionerna x = −2,−1,0,1,2 av ${\dfrac {1}{6}},{\dfrac {1}{4}},{\dfrac {1}{2}},{\dfrac {3}{4}},{ \dfrac {5}{6}}$ respektive. Slumpgången har en centrerande effekt som försvagas när c ökar.

Eftersom sannolikheterna endast beror på den aktuella positionen (värdet av x ) och inte på några tidigare positioner, uppfyller denna partiska slumpmässiga vandring definitionen av en Markov-kedja.

Spelande

Anta att du börjar med $10, och du satsar $1 på en oändlig, rättvis, myntkastning på obestämd tid, eller tills du förlorar alla dina pengar. Om $X_{n}$ representerar antalet dollar du har efter n kast, med $X_{0}=10$ , då sekvensen ${\ displaystyle \{X_{n}:n\in \mathbb {N} \}}$ är en Markov-process. Om jag vet att du har $12 nu, skulle det förväntas att med jämna odds, kommer du antingen ha $11 eller $13 efter nästa kast. Denna gissning förbättras inte av den extra kunskapen att du började med $10, sedan gick upp till $11, ner till $10, upp till $11 och sedan till $12. Det faktum att gissningen inte förbättras av kunskapen om tidigare kast visar upp Markov-egenskapen , den minneslösa egenskapen hos en stokastisk process.

En enkel vädermodell

Sannolikheterna för väderförhållanden (modellerade som antingen regniga eller soliga), givet vädret föregående dag, kan representeras av en övergångsmatris :

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

Matrisen P representerar vädermodellen där en solig dag med 90 % sannolikhet följs av en annan solig dag, och en regnig dag med 50 % sannolikt kommer att följas av en annan regnig dag. Kolumnerna kan märkas "soligt" och "regnigt", och raderna kan märkas i samma ordning.

Ovanstående matris som en graf.

( P ) _ij är sannolikheten att, om en given dag är av typ i , kommer den att följas av en dag av typ j .

Lägg märke till att raderna i P summerar till 1: detta beror på att P är en stokastisk matris .

Förutsäga vädret

Vädret på dag 0 (idag) är känt för att vara soligt. Detta representeras av en initialtillståndsvektor där den "soliga" posten är 100% och den "regniga" posten är 0%:

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

Vädret på dag 1 (i morgon) kan förutsägas genom att multiplicera tillståndsvektorn från dag 0 med övergångsmatrisen:

\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}}

Det finns alltså 90 % chans att dag 1 också blir solig.

Vädret på dag 2 (i övermorgon) kan förutsägas på samma sätt, från tillståndsvektorn som vi beräknade för dag 1:

\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

\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}}

Allmänna regler för dag n är:

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

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

Stadig väderlek

I det här exemplet ändras förutsägelserna för vädret på mer avlägsna dagar mindre och mindre för varje efterföljande dag och tenderar mot en vektor för stabilt tillstånd . Denna vektor representerar sannolikheterna för soligt och regnigt väder alla dagar och är oberoende av det ursprungliga vädret.

Steady state vektorn definieras som:

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

men konvergerar till en strikt positiv vektor endast om P är en regelbunden övergångsmatris (det vill säga det finns minst en Pn med alla poster som inte är noll) ^.

Eftersom q är oberoende av initiala villkor måste den vara oförändrad när den transformeras av P . Detta gör den till en egenvektor (med egenvärde 1), och betyder att den kan härledas från P .

I lekmannatermer är steady-state vektorn vektorn som, när vi multiplicerar den med P , får vi tillbaka exakt samma vektor. För väderexemplet kan vi använda detta för att sätta upp en matrisekvation:

{\begin{aligned}P&={\begin{bmatrix}0.9 .1\\0.5&0.5\end{bmatrix}}\\\mathbf {q} P&=\mathbf {q} &&{\text{(}}\mathbf {q} {\text{ är oförändrad 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}}&={\begin{bmatrix}0&0\end{bmatrix}}\\-0.1q_{1} +0.5q_{2}&=0\end{aligned}}

och eftersom de är en sannolikhetsvektor vet vi det

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

Att lösa detta par av samtidiga ekvationer ger steady state vektorn:

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

Sammanfattningsvis, på lång sikt är cirka 83,3 % av dagarna soliga. Det är viktigt att inse att inte alla Markov-processer har en steady state-vektor. I synnerhet måste övergångsmatrisen vara regelbunden . Annars kommer tillståndsvektorerna att svänga över tiden utan att konvergera.

Aktiemarknad

Med hjälp av en riktad graf representeras sannolikheterna för de möjliga tillstånd en hypotetisk aktiemarknad kan uppvisa. Matrisen till vänster visar hur sannolikheter som motsvarar olika tillstånd kan ordnas i matrisform.

Ett tillståndsdiagram för ett enkelt exempel visas i figuren till höger, med hjälp av en riktad graf för att avbilda tillståndsövergångarna . Delstaterna representerar om en hypotetisk aktiemarknad uppvisar en tjurmarknad , björnmarknad eller stagnerande marknadstrend under en given vecka. Enligt figuren följs en tjurvecka av ytterligare en tjurvecka 90 % av tiden, en björnvecka 7,5 % av tiden och en stillastående vecka de andra 2,5 % av tiden. Märkning av tillståndsutrymmet {1 = tjur, 2 = björn, 3 = stillastående} är övergångsmatrisen för detta exempel

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

Fördelningen över tillstånd kan skrivas som en stokastisk radvektor $x$ med relationen $x (n + 1) = x (n) P$ . Så om systemet vid tidpunkten $n är i tillstånd$ $x (n) , så$ är fördelningen tre tidsperioder senare, vid tidpunkten $n +3 .$

{\begin{aligned}x^{(n+3)}&=x^{(n+2)}P=\left(x^{(n+1)}P\right)P\ \\\&=x^{(n+1)}P^{2}=\left(x^{(n)}P\höger)P^{2}\\&=x^{(n)} P^{3}\\\end{aligned}}

Markov Chains förutsägelse på 3 diskreta steg baserat på övergångsmatrisen från exemplet till vänster.

I synnerhet, om systemet vid tidpunkten $n är i tillstånd 2 (björn), så$ är fördelningen vid tidpunkten $n + 3$

{\begin{aligned}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.35725&0.35725&0.5687bendmatrix\5 }}.\end{aligned}}

Markov kedjer förutsägelse på 50 diskreta steg. Återigen används övergångsmatrisen från vänster.

Med hjälp av övergångsmatrisen är det möjligt att till exempel beräkna den långsiktiga andelen veckor under vilka marknaden är stagnerande, eller det genomsnittliga antalet veckor det tar att gå från en stillastående till en tjurmarknad. Med hjälp av övergångssannolikheterna indikerar steady-state sannolikheterna att 62,5 % av veckorna kommer att vara på en tjurmarknad, 31,25 % av veckorna kommer att vara på en björnmarknad och 6,25 % av veckorna kommer att vara stillastående, eftersom:

\lim _{N\to \inftyb}={}^{0625 0,0625 0. 0625\\0.625&0.3125&0.0625\\0.625&0.3125&0.0625\end{bmatrix}}

En grundlig utveckling och många exempel finns i onlinemonografin Meyn & Tweedie 2005.

En finita-state-maskin kan användas som en representation av en Markov-kedja. Om man antar en sekvens av oberoende och identiskt fördelade insignaler (till exempel symboler från ett binärt alfabet som valts genom myntkast), om maskinen är i tillstånd y vid tidpunkten n , då är sannolikheten att den flyttar till tillstånd x vid tidpunkten n + 1 beror bara på det aktuella tillståndet.

Kontinuerlig tid

En födelse-död process

Om man poppar hundra kärnor popcorn i en ugn, varvid varje kärna poppar vid en oberoende exponentiellt fördelad tidpunkt, då skulle detta vara en kontinuerlig Markov-process . Om $X_{t}$ anger antalet kärnor som har dykt upp till tidpunkten t , kan problemet definieras som att hitta antalet kärnor som kommer in senare. Det enda man behöver veta är antalet kärnor som har poppat före tiden "t". Det är inte nödvändigt att veta när de dök upp, så att veta $X_{t}$ för tidigare gånger "t" är inte relevant.

Processen som beskrivs här är en approximation av en Poisson-punktsprocess – Poisson-processer är också Markov-processer.

Se även

^ Øksendal, BK (Bernt Karsten), 1945- (2003). Stokastiska differentialekvationer: en introduktion med tillämpningar (6:e upplagan). Berlin: Springer. ISBN 3540047581 . OCLC 52203046 . {{ citera bok }} : CS1 underhåll: flera namn: lista över författare ( länk )
^ Gagniuc, Paul A. (2017). Markov-kedjor: Från teori till implementering och experiment . USA, NJ: John Wiley & Sons. s. 1–235. ISBN 978-1-119-38755-8 .
^ ^a ^b ^c Van Kampen, NG (2007). Stokastiska processer i fysik och kemi . NL: North Holland Elsevier. s. 73 –95. ISBN 978-0-444-52965-7 .
^ ^a ^b ^c ^d Van Kampen, NG (2007). Stokastiska processer i fysik och kemi . NL: North Holland Elsevier. s. 73 –95. ISBN 978-0-444-52965-7 .
^ "Går stadigt (tillstånd) med Markov-processer" . Bloomington-lärare.
^ ^a ^b Gagniuc, Paul A. (2017). Markov-kedjor: från teori till implementering och experiment . Hoboken, NJ: John Wiley & Sons. s. 131–163. ISBN 9781119387572 . OCLC 982373850 .
^ SP Meyn och RL Tweedie, 2005. Markov-kedjor och stokastisk stabilitet arkiverade 2013-09-03 på Wayback Machine

externa länkar

Monopol som en Markov-kedja

[:3-1] Øksendal, BK (Bernt Karsten), 1945- (2003). Stokastiska differentialekvationer: en introduktion med tillämpningar (6:e upplagan). Berlin: Springer. ISBN 3540047581 . OCLC 52203046 . {{ citera bok }} : CS1 underhåll: flera namn: lista över författare ( länk )

[:02-2] Gagniuc, Paul A. (2017). Markov-kedjor: Från teori till implementering och experiment . USA, NJ: John Wiley & Sons. s. 1–235. ISBN 978-1-119-38755-8 .

[:0-3] Van Kampen, NG (2007). Stokastiska processer i fysik och kemi . NL: North Holland Elsevier. s. 73 –95. ISBN 978-0-444-52965-7 .

[:1-4] Van Kampen, NG (2007). Stokastiska processer i fysik och kemi . NL: North Holland Elsevier. s. 73 –95. ISBN 978-0-444-52965-7 .

[5] "Går stadigt (tillstånd) med Markov-processer" . Bloomington-lärare.

[:2-6] Gagniuc, Paul A. (2017). Markov-kedjor: från teori till implementering och experiment . Hoboken, NJ: John Wiley & Sons. s. 131–163. ISBN 9781119387572 . OCLC 982373850 .

[MCSS-7] SP Meyn och RL Tweedie, 2005. Markov-kedjor och stokastisk stabilitet arkiverade 2013-09-03 på Wayback Machine