Markov kjede

I sannsynlighetsteori er en spesiell type diskret stokastisk prosess der sannsynligheten for at en hendelse inntreffer bare avhenger av den umiddelbart foregående hendelsen , kjent som en Markov-kjede eller Markov- modell . Denne funksjonen med å inkludere nylig minne kalles Markov-egenskapen i motsetning til uavhengige hendelser som ikke har noe minne om noen tidligere hendelser. I en tidlig artikkel fra 1906 definerte AA Markov den "enkle kjeden" som "en uendelig sekvens x1, x2, ..., xk, xk+1, ..., av variabler koblet på en slik måte at xk+1 for enhver k er uavhengig av x1, x2, ..., xk−1, forutsatt at xk er kjent." Markov kalte kjeden "homogen" hvis den betingede fordelingen av xk+1 gitt xk var uavhengig av k. Han vurderte også "komplekse" strenger der "hvert tall er direkte koblet til ikke bare ett, men flere tall før det." [ 1 ]

Den har fått navnet sitt fra den russiske matematikeren Andrei Markov (1856-1922), som introduserte den i 1906 . [ 1 ]

Disse statistiske modellene har et stort antall reelle applikasjoner.

Definisjon

I matematikk er en Markov -kjede en tidsdiskret stokastisk prosess med diskret tilstandsrom som for ethvert heltall og for alle tilfredsstiller $\{X_{n}:n=0,1,2\dots \}$ $ja$ $n\geq 0$ $x_{0},x_{1},\dots ,x_{n+1}\in S$

P[X_{n+1}=x_{n+1}|X_{0}=x_{0},X_{1}=x_{1},\dots ,X_{n}=x_{n }]=P[X_{n+1}=x_{n+1}|X_{n}=x_{n}]

denne eiendommen er kjent som Markov-eiendommen .

Funksjoner

Homogene og inhomogene kjeder

En Markov-kjede sies å være homogen hvis sannsynligheten for å gå fra stat til stat i ett trinn ikke avhenger av tiden kjeden er funnet, det vil si: $i$ $j$

P[X_{n+1}=j|X_{n}=i]=P[X_{1}=j|X_{0}=i]

for alt og for hvem som helst . $n\geq 0$ $i,j\in S$

Hvis for et par stater og i noen tid den nevnte egenskapen ikke holder, sier vi at Markov-kjeden er ikke-homogen . $n$

Overgangssannsynligheter

La og være to tilstander av en Markov-kjede. Sannsynligheten for å gå fra tidstilstand til tidstilstand er angitt med $i$ $j$ $i$ $n$ $j$ $n+1$

p_{ij}(n,n+1)=\operatørnavn {P} [X_{n+1}=j|X_{n}=i]

Når kjeden er homogen, er denne sannsynligheten betegnet med

p_{ij}=\operatørnavn {P} [X_{n+1}=j|X_{n}=i]

som representerer sannsynligheten for å flytte fra stat til stat i en tidsenhet. $Yo$ $j$

Overgangssannsynlighetsmatrise

Hvis vi har ett-trinns overgangssannsynlighetene , , hvis vi varierer indeksene over tilstandsrommet, får vi matrisen kalt ett-trinns overgangssannsynlighetsmatrisen , det vil si: $p_{ij}$ $i,j$ $S=\{0,1,2,\dots \}$ $P$

P={\begin{bmatrix}p_{00}&p_{01}&p_{02}&\cdots \\p_{10}&p_{11}&p_{12}&\cdots \\p_{20}&p_ {21}&p_{22}&\cdots \\\vdots &\vdots &\vdots \end{bmatrix}}

hvor input representerer sannsynligheten for å gå fra stat til stat i ett trinn. $(i, j)$ $Yo$ $j$

Matrisen er en stokastisk matrise siden den tilfredsstiller $P$

$p_{ij}\geq 0$
$\sumj\in S}p_{ij}=1$

Tilsvarende er overgangssannsynlighetsmatrisen definert i trinn, den er betegnet med og gitt av $n$ $P(n)$

P(n)={\begin{bmatrix}p_{00}(n)&p_{01}(n)&p_{02}(n)&\cdots \\p_{10}(n)&p_{11 }(n)&p_{12}(n)&\cdots \\p_{20}(n)&p_{21}(n)&p_{22}(n)&\cdots \\\vdots &\vdots &\vdots \end{bmatrix}}

hvor input representerer sannsynligheten for å gå fra tilstand til stat i trinn. $(i, j)$ $Yo$ $j$ $n$

Chapman–Kolmogorov-ligningen

For alle slike det og for alle stater det gjelder $r,n\in \mathbb {Z}$ $0\leq r\leq n$ $i,j\in S$

p_{ij}(n)=\sum​​k\in S}p_{ik}(r)p_{kj}(nr)

Som en konsekvens av dette resultatet er trinnovergangssannsynligheten , , gitt ved inntastingen av den -te potensen til ett- trinns overgangssannsynlighetsmatrisen, dvs. $n$ $p_{ij}(n)$ $(i, j)$ $n$

p_{ij}(n)=(P^{n})_{ij}

Med det ovenstående blir problemet med å beregne overgangssannsynlighetene i trinn å finne den -te potensen av matrisen av overgangssannsynligheter i ett trinn, dvs. $n$ $n$

{\begin{aligned}P(n)&={\begin{bmatrix}p_{00}(n)&p_{01}(n)&\cdots \\p_{10}(n)&p_{11 }(n)&\cdots \\\vdots &\vdots \end{bmatrix}}\\&={\begin{bmatrix}p_{00}&p_{01}&\cdots \\p_{10}&p_{11 }&\cdots \\\vdots &\vdots \end{bmatrix}}^{n}\\&=P^{n}\end{aligned}}

Kommunikasjonskurs

For to stater og i staters rom vil vi si at staten er tilgjengelig fra staten og skrive hvis slik at $i$ $j$ $ja$ $j$ $i$ $i\høyrepil j$ $\exists \,n\i \mathbb {Z}++}$

p_{ij}(n)>0

hvis og da vil vi si at staten kommuniserer med staten og skrive . $i\høyrepil j$ $j\høyrepil i$ $i$ $j$ $i\longleftrightarrow j$

Egenskapen er en ekvivalensrelasjon . Denne relasjonen induserer en oppdeling av statsrommet. Vi vil kalle disse ekvivalensklassene for kommunikasjonsklasser . $\longleftrightarrow$

Gitt en tilstand vil vi betegne dens kommunikasjonsklasse som , så hvis og bare hvis . $i\in S$ $C(i)$ $i\longleftrightarrow j$ $C(i)=C(j)$

Hvis da kjeden sies å være irreduserbar. $C(i)=S$

Periodisitet

Perioden til en stat er definert som : $i\in S$

d(i)={\rm {gcd}}\{n\geq 1:p_{ii}(n)>0\}

hvor angir den største felles divisor . ${\rm {gcd}}$

Hvis vi sier at det er en aperiodisk tilstand . $d(i)=1$ $i$
Hvis vi skal si at hun har mensen . $d(i)=k\geq 2$ $i$ $k$

En Markov-kjede sies å være aperiodisk hvis alle dens tilstander er aperiodiske, det vil si hvis $d(i)=1\quad \for alle \;i\in S$ .

Første besøkstider

Hvis , definerer vi tidspunktet for første besøk a som den tilfeldige variabelen $C\subset S$ $C$

\tau​​C}={\begin{cases}\min\{n>0|X_{n}\in C\}&{\mbox{if }}\{n>0|X_{n }\in C\}\neq \emptyset \\1&{\mbox{if }}\{n>0|X_{n}\in C\}=\emptyset \end{cases}}

det vil si at den angir første gang strengen går inn i tilstandssettet . $\tau{C}$ $C$

Sannsynlighet for første besøk

Den definerer

f_{ij}(n)=\operatørnavn {P} [X_{n}=j,X_{n-1}\neq j,\dots ,X_{1}\neq j|X_{0}= Yo]

som sannsynligheten for at en kjede som starter i staten når staten for første gang i trinn, hvor . $Yo$ $j$ $n$ $f_{ij}(0)=0$

Spesielt når , angir sannsynligheten for å gå tilbake til staten i trinn for første gang. $i=j$ $f_{ii}(n)$ $Yo$ $n$

og er definert

f_{ij}=\sum​​n=1}^{\infty }f_{ij}(n)

som sannsynligheten for et eventuelt besøk fra stat til stat og $Yo$ $j$

f_{ii}=\sum​​n=1}^{\infty }f_{ii}(n)

som sannsynligheten for å forlate staten og returnere til den på en begrenset tid. $Yo$

Gjentakelse

I en statlig rom Markov-kjede sier vi at: $ja$

$i$ er en tilbakevendende tilstand hvis . $f_{ii}=1$
$i$ er forbigående ja . $f_{ii}<1$

eller bruk overgangssannsynlighetene i trinn: $n$

$i$ er tilbakevendende hvis $\sumn=1}^{\infty }p_{ii}(n)=\infty$
$i$ det er forbigående ja $\sumn=1}^{\infty }p_{ii}(n)<\infty$

Gjentakelse er en klasseegenskap siden

Hvis det er rekursivt , er e rekursivt. $i$ $i\longleftrightarrow j$ $j$
Hvis e er forbigående så er det forbigående. $i$ $i\longleftrightarrow j$ $j$

AA.

Gjennomsnittlig gjentakelsestid

Det er definert som gjennomsnittlig gjentakelsestid for en tilbakevendende tilstand med utgangspunkt i tilstanden som forventningen til $j$ $i$

\tauij}=\min\{n\geq 1:X_{n}=j|X_{0}=i\}

og er betegnet med $\mu ij}$

\mu​​ij}=\operatørnavn {E} [\tau​​ij}]=\sum​​n=1}^{\infty }nf_{ij}(n)

Denne forventningen representerer gjennomsnittlig antall skritt det tar for kjeden å gå tilbake til den rekursive tilstanden . $j$

Spesielt når vi skriver i stedet for . $i=j$ $\mu i}$ $\mu ij}$

En tilbakevendende tilstand sies å være $i$

null rekursiv hvis . $\mu i}=\infty$
positivt tilbakevendende ja . $\mu i}<\infty$

Positiv gjentakelse er en klasseegenskap siden

Hvis den er positiv rekursiv , er e positiv rekursiv. $i$ $i\longleftrightarrow j$ $j$
Hvis e er null-rekursiv , er den null-rekursiv. $i$ $i\longleftrightarrow j$ $j$

Stasjonære distribusjoner

Vektoren sies å være en sannsynlighetsfordeling if $\pi =(\pi 0},\pi 1 ,\dots )$

$\pi i}\geq 0$
$\sum i}\pi i}=1$

En sannsynlighetsfordeling sies å være stasjonær for en Markov-kjede med overgangssannsynlighetsmatrise if $\pi =(\pi 0},\pi 1 ,\dots )$ $P=(p_{ij})$

\pi​​j}=\sum​​i\in S}\pi​​i}p_{ij}

I matriseform er ovennevnte ekvivalent med og betyr at hvis en initial tilfeldig variabel har en fordeling så er fordelingen av også , det vil si at denne fordelingen ikke endres over tid. $\pi =\pi P$ $X_{0}$ $\pi$ $X_{n}$ $\pi$

For å finne en mulig stasjonær fordeling av en kjede med matrise , er en metode å løse ligningssystemet $P$

\left\{{\begin{array}{cc}\pi =\pi P\\{\text{Med forbehold om:}}}\\&\sum​​j\in S}\pi​​j }=1\\&\pij\geq 0\end{array}}\right.

Den stasjonære distribusjonen er kanskje ikke unik eller eksisterer til og med ikke.

Eksistens og enhet

Hvis en Markov-kjede er irreduserbar og positivt rekursiv , har den en unik stasjonær distribusjon, og dette er gitt av

\pi j}={\frac {1}{\mu j}}}

hvor er gjennomsnittlig gjentakelsestid for staten . $\muj}$ $j$

Konvergens til stasjonær distribusjon

Hvis en Markov-kjede er

Ureduserbar
aperiodisk
Med stasjonær distribusjon $\pi$

deretter for noen $i,j\in S$

\lim​​n\to \infty }p_{ij}(n)=\pi​​j}

Konvergens for Markov-kjeder

Hvis en Markov-kjede er

Ureduserbar
positivt tilbakevendende
aperiodisk

da begrenser sannsynligheten seg

\pi​​j}=\lim​​n\to \infty }p_{ij}(n)

eksisterer, de er gitt av

\pi j}={\frac {1}{\mu j}}}

og er den eneste løsningen på ligningssystemet

\left\{{\begin{array}{cc}\pi =\pi P\\{\text{Med forbehold om:}}}\\&\sum​​j\in S}\pi​​j }=1\\&\pij\geq 0\end{array}}\right.

Typer Markov-kjeder

Irredusible kjeder

En Markov-kjede sies å være irreduserbar hvis noen av følgende betingelser er oppfylt (tilsvarer hverandre):

Fra hvilken som helst stat kan du få tilgang til alle andre. $ja$
Alle stater kommuniserer med hverandre.
$C(i)=S$ for noen . $i\in S$
$C(i)=S$ for alt . $i\in S$
Det eneste lukkede settet er totalen.

Ehrenfest-kjeden eller den tilfeldige vandringen uten absorberende barrierer er eksempler på irreduserbare Markov-kjeder.

Positive gjentakende kjeder

En Markov-kjede sies å være positivt rekursiv hvis alle dens tilstander er positivt rekursive. Hvis kjeden også er irreduserbar, er det mulig å vise at det er en enkelt invariant sannsynlighetsvektor og den er gitt av:

\pi j}={\frac {1}{\mu j}}}

Vanlige strenger

En Markov-kjede sies å være regelmessig (også primitiv eller ergodisk ) hvis det eksisterer en positiv kraft i overgangsmatrisen hvis oppføringer alle strengt tatt er større enn null.

Når tilstandsrommet er begrenset, hvis angir overgangsmatrisen til kjeden, har vi: $ja$ $P$

\lim​​n\to {\mathcal {1}}\,}P^{n}=W

hvor er en matrise med alle sine rader lik den samme sannsynlighetsvektoren w , som viser seg å være den invariante sannsynlighetsvektoren til kjeden. Når det gjelder vanlige strenger, er denne invariante vektoren unik. $W$

Absorberende kjeder

En Markov-kjede med begrenset tilstandsrom sies å være absorberende hvis følgende to betingelser er oppfylt:

Kjedet har minst én absorberende tilstand.
Fra enhver ikke-absorberende tilstand, er noen absorberende tilstand tilgjengelig.

Hvis vi betegner som A settet av alle absorberende tilstander og dets komplement som D , har vi følgende resultater:

Dens overgangsmatrise kan alltid bringes til en av formene

P={\begin{pmatrix}Q&R\\0&I\end{pmatrix}}

hvor submatrisen Q tilsvarer tilstandene til settet , er identitetsmatrisen, er nullmatrisen og en del submatrise. $D$ $Yo$ $0$ $R$

$P_{x}(T_{A}<{\mathcal {1}}\,)=1$ , det vil si at uansett hvor kjeden er, vil den til slutt ende opp i en absorberende tilstand.

Markov lenker i kontinuerlig tid

Hvis vi i stedet for å betrakte en diskret sekvens indeksert i settet av naturlige tall, vurderer de tilfeldige variablene som varierer i et kontinuerlig intervall av settet med reelle tall, vil vi ha en kjede i kontinuerlig tid. For denne typen strenger i kontinuerlig tid uttrykkes Markov-egenskapen som følger: $X_{1},X_{2},\dots ,X_{i},\dots$ $i$ $\mathbb {N} \;\!$ $X_{t}$ $t$ $\mathbb {R} \;\!$

P(X(t_{n+1})=x_{n+1}|X(t_{n})=x_{n},\ldots ,X(t_{1})=x_{1})=P (X(t_{n+1})=x_{n+1}|X(t_{n})=x_{n})

slik at

t_{n+1}>t_{n}>t_{n-1}>\dots >t_{1}

For en kontinuerlig Markov-kjede med et begrenset antall tilstander, kan en stokastisk matrise defineres gitt av:

\mathbf {P} (t_{1},t_{2})=[p_{ij}(t_{1},t_{2})]_{i,j=1,\dots ,N},\qquad p_{ij}(t_{1},t_{2})=P[X(t_{2})=j|X(t_{1})=i],\ 0\geq t_{1}<t_{ to}

Kjeden kalles homogen hvis . For en homogen kontinuerlig-tids Markov-kjede med et endelig antall tilstander, kan den såkalte infinitesimal-generatoren defineres som: [ 2 ] $\mathbf {P} (t_{1},t_{2})=\mathbf {P} (t_{2}-t_{1})$

\mathbf {Q} =\lim​​h\to 0^{+}}{\frac {\mathbf {P} (h)-\mathbf {I} }{h}}

Og det kan vises at den stokastiske matrisen er gitt av:

\mathbf {P} (t)=e^{\mathbf {Q} t}=\sumn=0}^{\infty }{\frac {\mathbf {Q} n}t^{n }}{n! }}

Applikasjoner

Meteorologi

Hvis vi vurderer været i en region over forskjellige dager, er det mulig å anta at den nåværende tilstanden bare avhenger av den siste tilstanden og ikke av hele historien i seg selv, slik at Markov-kjeder kan brukes til å formulere grunnleggende klimatologiske modeller. For eksempel er det utviklet modeller for tilbakefall av nedbør basert på Markov-kjeder. [ 3 ]

Epidemiologiske modeller

En viktig anvendelse av Markov-kjeder er i Galton-Watson-prosessen . Dette er en forgreningsprosess som blant annet kan brukes til å modellere utviklingen av en epidemi (se matematisk modellering av epidemier ).

Internett

Siderangeringen til en nettside (brukt av Google i søkemotorene) er definert gjennom en Markov-kjede, der plasseringen som en side vil ha i søkemotoren vil bli bestemt av dens vekt i den stasjonære distribusjonen av kjeden.

Simulering

Markov-kjeder brukes til å gi en analytisk løsning på visse simuleringsproblemer, for eksempel i køteori er M/M/1-modellen [ 4 ] faktisk en Markov-kjedemodell.

Gambling

Det er mange sjansespill som kan modelleres gjennom en Markov-kjede. Gamblers ruinmodell , som fastslår sannsynligheten for at en person som satser på et sjansespill ender opp uten penger, er en av bruksområdene til Markov-kjedene på dette området.

Økonomi og finans

Markov-kjeder kan brukes i enkle opsjonsprisingsmodeller for å avgjøre når en arbitrasjemulighet eksisterer , så vel som i modellering av aksjemarkedskrasj eller for å bestemme prisvolatilitet . I næringslivet har Markov-kjeder blitt brukt til å analysere kjøpsmønstrene for dårlige fordringer , planlegge for bemanningsbehov og analysere utstyrsutskifting.

Genetikk

Markov-kjeder brukes i populasjonsgenetikkteori for å beskrive endringen i genfrekvenser i en liten populasjon med diskrete generasjoner, utsatt for genetisk drift . Den har blitt brukt i konstruksjonen av Motō Kimuras diffusjonsmodell .

Musikk

Ulike musikkkomposisjonsalgoritmer bruker Markov-kjeder, for eksempel Csound- eller Max -programvaren . En av komponistene som brukte denne teknikken i komposisjonene hans var Iannis Xenakis med verket Analoguique A et B (1958–59).

Operasjoner

Markov-kjeder brukes i inventar, vedlikehold og prosessflyt.

Nevrale nettverk

De brukes i Boltzmann-maskiner .

Referanser

↑ a b Basharin, Gely P.; Langville, Amy N.; Naumov, Valery A. (2004). "Livet og arbeidet til A. A. Markov" . Lineær algebra og dens anvendelser 386 : 3-26 . Hentet 31. mars 2010 .
↑ Masaki Kijima, 1997, s. 175
↑ R. Gabriel & J. Neumann (2006): En Markov-kjedemodell for daglig nedbør i Tel Aviv
↑ Masaki Kijima, 1997, s. 287-290.

Bibliografi

AA Markov. "Rasprostranenie zakona bol'shih meisel med velichiny, zavisyaschie drug ot druga". Izvestiya Fiziko-matematicheskogo obschestva pri Kazanskom universitete , 2-ya seriya, tom 15, pp. 135–156, 1906.
AA Markov. "Utvidelse av grensesetningene for sannsynlighetsteori til en sum av variabler koblet i en kjede". gjengitt i vedlegg B av: R. Howard. Dynamic Probabilistic Systems, bind 1: Markov Chains . John Wiley og sønner, 1971.
Klassisk tekst i oversettelse: AA Markov, et eksempel på statistisk undersøkelse av teksten Eugene Onegin vedrørende koblingen av prøver i kjeder, trans. David Link. Science in Context 19.4 (2006): 591–600. Online: http://journals.cambridge.org/production/action/cjoGetFulltext?fulltextid=637500
Leo Breman. Sannsynlighet . Originalutgave utgitt av Addison-Wesley, 1968; gjengitt av Society for Industrial and Applied Mathematics, 1992. ISBN 0-89871-296-3 . (Se kapittel 7.)
JL Doob. Stokastiske prosesser . New York: John Wiley and Sons, 1953. ISBN 0-471-52369-0 .
SP Meyn og RL Tweedie. Markov-kjeder og stokastisk stabilitet . London: Springer-Verlag, 1993. ISBN 0-387-19832-6 . online: [1] . Andre utgave som vises, Cambridge University Press , 2009.
SP Meyn. Kontrollteknikker for komplekse nettverk . Cambridge University Press, 2007. ISBN 978-0-521-88441-9 . Vedlegg inneholder forkortet Meyn & Tweedie. online: https://web.archive.org/web/20100619011046/https://netfiles.uiuc.edu/meyn/www/spm_files/CTCN/CTCN.html
Booth, Taylor L. (1967). Sekvensielle maskiner og automatteori (1. utgave). New York: John Wiley and Sons, Inc. Library of Congress-kortkatalognummer 67-25924 . Omfattende, vidtfavnende bok ment for spesialister, skrevet for både teoretiske datavitere så vel som elektroingeniører. Med detaljerte forklaringer av statlige minimeringsteknikker, FSM-er, Turing-maskiner, Markov-prosesser og uavgjørlighet. Utmerket behandling av Markov-prosesser s. 449ff. Diskuterer Z-transformers, D-transformers i sin kontekst.
Kemeny, John G.; Mirkil, Hazleton; Snell, J. Laurie; Thompson, Gerald L. (1959). Finite Mathematical Structures (1. utgave). Englewood Cliffs, NJ: Prentice-Hall, Inc. Library of Congress-kortkatalognummer 59-12841 . Klassisk tekst. jf. kapittel 6 Finite Markov-kjeder s. 384ff.
Kijima, Masaaki (1997). Markov-prosesser for stokastisk modellering (1. utgave). Cambridge: Chapman & Hall. ISBN 0 412 60660 7 .
E. Nummelin. "Generelle irreduserbare Markov-kjeder og ikke-negative operatører". Cambridge University Press, 1984, 2004. ISBN 0-521-60494-X

Eksterne lenker

Markov lenker i diskret tid
Eksempel på en Markov-kjede i diskret tid
Teknikker for å forstå datasimuleringer : Markov-kjedeanalyse
Disambiguering ved bruk av Markov Chains
En visuell forklaring av Victor Powell