Markov-prosessen

En stokastisk prosess er definert som Markov (eller Markov ), en tilfeldig prosess der sannsynligheten for overgang som bestemmer overgangen til en systemtilstand kun avhenger av tilstanden til det umiddelbart foregående systemet ( Markov-egenskapen ) og ikke av hvordan det kom til denne staten. [1] Omvendt er en ikke-Markov- prosess en tilfeldig prosess som Markov-egenskapen ikke er gyldig for. Den har fått navnet sitt fra den russiske matematikeren Andrei Andreevich Markov som først utviklet teorien. Markov-modeller brukes i utformingen av telekommunikasjonsnettverk : den resulterende køteorien finner anvendelse i mange områder, fra køer ved tellere til datapakker i kø i en ruter .

En Markov-prosess kan beskrives ved hjelp av uttalelsen om Markov-eiendommen , eller "no-memory"-tilstand, som kan skrives som:

{\ displaystyle P {\ big (} X (t_ {n + 1}) = x_ {n + 1} {\ big |} X (t_ {n}) = x_ {n}, X (t_ {n-1 }) = x_ {n-1}, \ ldots, X (t_ {0}) = x_ {0} {\ big)} = P {\ big (} X (t_ {n + 1}) = x_ {n +1} {\ stor |} X (t_ {n}) = x_ {n} {\ stor)}}

Markov-kjeder

En Markov-kjede er en Markov-prosess med diskret tilstandsrom , så det er en stokastisk prosess som tar verdier i et diskret rom og som nyter Markov-eiendommen . Settet med tilstandsrom kan være endelig eller uendelig tellbart. I det første tilfellet snakker vi om en endelig tilstand Markov-kjede. En Markov-kjede kan være kontinuerlig-tid eller diskret-tid, basert på medlemssettet til tidsvariabelen (kontinuerlig eller diskret). $S.$ $T.$

Formelt er en Markov-kjede en Markovsk stokastisk prosess preget av en parameter , et sett med tilstander og en overgangssannsynlighetsfunksjon . $t_i \ i T$ $S.$ $P: S \ ganger S \ ganger T \ mapsto [0,1]$

Siden den er en Markovsk prosess, nyter den Markov-eierskap : $P.$

P (X (t_ {n + 1}) = x_ {n + 1} | X (t_n) = x_n, X (t_ {n-1}) = x_ {n-1}, \ ldots, X (t_0) = x_0) = P (X (t_ {n + 1}) = x_ {n + 1} | X (t_n) = x_n)

I tilfelle av en diskret-tids Markov-kjede , det vil si med det diskrete settet, er notasjonen forenklet: $T.$

P (X_ {n + 1} = x_ {n + 1} | X_n, X_ {n-1}, \ ldots, X_0) = P (X_ {n + 1} = x_ {n + 1} | X_n). \,

Homogene Markov-kjeder

En homogen Markov-kjede er en Markov-prosess der sannsynligheten for overgang til tider ikke avhenger av tiden selv, men bare av tilstanden til systemet på det umiddelbart foregående tidspunktet . Med andre ord er overgangssannsynligheten uavhengig av opprinnelsen til tidsaksen og avhenger derfor kun av avstanden mellom de to tidsøyeblikkene. $du$ $S (t_ {i-1})$

For homogene kjeder holder tilstanden

P (X_ {n + 1} = x | X_n = y) = \ P (X_ {n} = x | X_ {n-1} = y)

Mer generelt er det vist at i en homogen Markov-kjede er sannsynligheten for overgang fra en tilstand til en annen i trinn konstant over tid: $n$

P (X_ {i + n} = x | X_i = y) = \ P (X_ {i-1 + n} = x | X_ {i-1} = y) \ \ \ \ \ \ forall i = \ 1 , 2, \ ldots

Virkelige systemer som kan modelleres med homogene Markov-kjeder er sjeldne: det er nok å tenke på "vær"-systemet for å forstå hvordan sannsynligheten for overgang fra en tilstand (for eksempel "sol") til en annen tilstand (for eksempel "regn" ") avhenger av sesongen, så det er ikke mulig å modellere dette systemet som en homogen Markov-kjede. Men ved å begrense analysen av systemet til et visst tidsintervall, kan den homogene oppførselen vurderes: i dette tilfellet kan tidsintervallet være en enkelt sesong.

Overgangsmatrise

En homogen Markov-kjede med endelig tilstand der settet av tilstander i systemet er endelig og har elementer kan representeres ved hjelp av en overgangsmatrise og en initial sannsynlighetsvektor . $S.$ $Nei.$ $A \ i \ mathbb {R} ^ {N \ ganger N}$ $\ tilde {\ pi} _0 \ in \ mathbb {R} ^ N$

Elementene til representerer sannsynlighetene for overgang mellom tilstandene i kjeden: en kjede som er i tilstanden har sannsynlighet for å gå over til tilstand j i neste trinn. Spesielt indikerer elementene på hoveddiagonalen til sannsynlighetene for å forbli i samme tilstand . Vektoren definerer sannsynlighetene for at Markov-kjeden opprinnelig er i hver av tilstandene. En homogen Markov-kjede er unikt definert av paret . $TIL$ $de$ $a_ {ij}$ $a_ {ii}$ $TIL$ $de$ $\ tilde {\ pi} _0$ $Nei.$ $(A, \ tilde {\ pi} _0)$

Hvis det på et tidspunkt har sannsynlighetsfordelingen , er sannsynlighetene for at systemet samtidig er i hver av tilstandene gitt av vektoren definert som følger: $t_ {0}$ $\ tilde {\ pi} _0$ $\ tilde {\ pi} _n$ $t_n$ $Nei.$

(\ tilde {\ pi} _n) ^ T = (\ tilde {\ pi} _0) ^ T \ cdot A ^ n

der det indikerer transponeringen av vektoren . $(\ tilde {\ pi} _n) ^ T$ $\ tilde {\ pi} _n$

Fra den aksiomatiske definisjonen av sannsynlighet utledes følgende egenskaper for matrisen : $TIL$

$a_ {ij} \ ge 0, \ forall i, j \ in \ {1 \ ldots N \}$

${\ displaystyle \ sum _ {j = 1} ^ {N} a_ {ij} = 1, \ forall i \ in \ {1 \ ldots N \}}$ .

Den andre egenskapen tilsvarer å kreve at summen av elementene på hver rad er lik 1, i så fall kalles matrisen også stokastisk .

For eksempel, og de kan være følgende: $TIL$ $\ tilde {\ pi} _0$

A = \ start {pmatrix} 0.3 & 0.5 & 0.2 \\ 0.1 & 0.8 & 0.1 \\ 0.5 & 0.5 & 0 \ end {pmatrix}, \ quad \ tilde {\ pi} _0 = \ start {pmatrix} 0.4 \ \ 0,3 \\ 0,3 \ end {pmatrix}

I tilfelle av en homogen diskret tilstand Markov-kjede, kan den syntetiske notasjonen tas i bruk:

P ^ {(n)} _ {ij} \ equiv P \ venstre (X_ {m + n} = s_j | X_ {m} = s_i \ høyre) = P \ venstre (X_ {n} = s_j | X_ {0 } = s_i \ høyre)

hvor (n) ikke er en eksponent, men er en indeks.

Så vi har . $(\ tilde {\ pi} _n) _j = \ sum_ {i \ i S} (\ tilde {\ pi} _0) _i (P ^ {(n)}) _ {ij}$

Vi har følgende egenskaper:

$P_ {ij} \ ge 0 \ \ \ forall i, j \ i S$

$\ sum_ {j \ i S} P_ {ij} = 1$ .

Aperiodiske Markov-kjeder

Perioden for en tilstand av en diskret tilstand Markov-kjede, med begrenset eller tellbar uendelighet, er definert som minimum antall tidstrinn for at det skal være en ikke-null sannsynlighet for å returnere til samme tilstand, med start fra tilstanden til tiden . Perioden er formelt definert som følger: $s_i \ i S$ $S.$ $ja$ $t_m$ $d (s_i)$

d (s_i, t_m) = MCD \ {n \ ge 1: P \ venstre (X_ {m + n} = s_i | X_m = s_i \ høyre)> 0 \}

hvor GCD er den største felles faktoren .

I tilfelle av en homogen endelig tilstand Markov-kjede med antall tilstander , som derfor kan representeres av en matrise , kan definisjonen omformuleres som følger: $Nei.$ $A \ i \ mathbb {R} ^ N$

d (s_i) = MCD \ {n \ ge 1: (A ^ n) _ {ii}> 0 \}

Tilstanden sies å være aperiodisk hvis perioden er lik 1. $ja$

En Markov-kjede kalles aperiodisk hvis alle dens tilstander er aperiodiske, ellers kalles den periodisk .

Irredusible Markov-kjeder

En diskret-stats Markov-kjede sies å være irreduserbar hvis det starter fra hver stat er det større enn null sannsynlighet for å nå en annen tilstand . Formelt er en Markov-kjede irreduserbar hvis: $ja$ $s_j$

\ forall s_i, s_j \ i S, \ forall m \ i \ mathbb {N}, \ finnes n \ i \ mathbb {N}: P \ venstre (X_ {m + n} = s_j | X_m = s_i \ høyre) > 0

Positive tilbakevendende tilstander

{\ displaystyle T_ {i} = {\ begynne {cases} min \ {n \ geq 1 \ tc, \ X_ {n} = s_ {i} \} & se \ X_ {n} = s_ {i} \ for \ noen \ n \ geq 1 \\ + \ infty & ellers \ end {cases}}}

staten sies å være positiv tilbakevendende hvis $s_i \ i S$ ${\ displaystyle E (T_ {i} | X_ {0} = s_ {i}) = \ mu _ {i} <+ \ infty.}$

Hvis en kjede er irreduserbar og en av dens tilstander er positiv gjentakende, er alle tilstandene positive gjentakende, i dette tilfellet sies kjeden å være positiv gjentakende .

Stasjonære distribusjoner

Gitt en homogen diskret-state Markov-kjede , er dens stasjonære sannsynlighetsfordeling , også kalt likevektsfordelingen , en diskret sannsynlighetsfordeling som tilfredsstiller følgende: $\ pi = \ {\ pi_1 \ ldots \ pi_n \ ldots \}$

$\ forall i \ i S, \ pi_i \ ge 0$

$\ sum_ {i \ i S} \ pi_i = 1$

$\ forall j \ i S, \ sum_ {i \ i S} \ pi_iP_ {ij} = \ pi_j$ .

Uformelt er en stasjonær fordeling en sannsynlighetsfordeling som forblir konstant ettersom Markov-kjeden utvikler seg over tid.

Betydningen av stasjonære fordelinger for homogene Markov-kjeder i diskrete tilstand er gitt av følgende teoremer:

Eksistens- og unikhetsteoremet sier at gitt en homogen diskret tilstand Markov-kjede med overgangssannsynlighet og tilstandsrom , hvis Markov-kjeden er irreduserbar og positivt tilbakevendende, så er det en unik stasjonær fordeling for Markov-kjeden. $P_ {ij}$ $S.$ $\ pi$

Konvergensteoremet sier at gitt en homogen diskret tilstand Markov-kjede med overgangssannsynlighet og tilstandsrom , hvis Markov-kjeden er irreduserbar, aperiodisk og positivt tilbakevendende, så konvergerer sannsynlighetsfordelingen til tider til den stasjonære fordelingen for hver initialfordeling av valgt sannsynlighet . Det har vi altså $P_ {ij}$ $S.$ $\ tilde {\ pi} _n$ $t_n$ $\ pi$ $\ tilde {\ pi} _0$

\ forall \ tilde {\ pi} _0, \ forall i, j \ i S, \ lim_ {n \ til \ infty} \ sum_ {i \ i S} (\ tilde {\ pi} _0) _i (P ^ { (n)}) _ {ij} = \ pi_j

Konvergensen av en Markov-kjede til en stasjonær distribusjon og muligheten for å bygge en kjede med en valgt stasjonær distribusjon er grunnlaget for Metropolis-Hastings-algoritmen .

Ergodic Markov Chains

En Markov-kjede er definert ergodisk hvis og bare hvis den eksisterer for hvert startøyeblikk og for hver innledende sannsynlighetstilstand og er uavhengig av og fra sannsynlighetsgrensen for uendelige tider $t_ {0}$ $\ tilde {\ pi} (t_0)$ $t_ {0}$ $\ tilde {\ pi} (t_0)$

P = \ lim_ {t \ til \ infty} \ tilde {\ pi} (t)

Applikasjoner

Mange Link Analysis Ranking - algoritmer er basert på teorien om Markov-prosesser. For eksempel er PageRank utledet av Google basert på den påfølgende overgangsfrekvensen for brukere fra et nettsted A til et nettsted B gjennom lenkene som fører fra A til B og ikke på det enkle antallet og typen lenker fra A til B, i for å gjenspeile populariteten til lenken for brukere og ikke viktigheten for skaperen av nettstedet. Det vil si at frekvensen til et nettsted er en verdi i intervallet [0,1] som tilsvarer den gjennomsnittlige tiden brukt på nettstedet av et stort antall brukere etter ganske lang tid: frekvensen, riktig skalert, utgjør Siderangering av nettstedet. Siden overgangsfrekvensen tilnærmer overgangssannsynligheten, kan den stasjonære sannsynlighetsfordelingen til Markov-kjeden dannet av alle nettstedene estimeres ved å konstruere en overgangsmatrise .
En del av naturlig språkmodellering bruker også Markovske statistiske modeller . For eksempel, innen vokalsyntese , var CSELT blant forløperne til denne trenden, spesielt for det italienske språket og latinske språk . [2]
Flere prognosealgoritmer innen økonomi, finans og systemdynamikk benytter seg av Markov-prosesser.

Mye av tidsseriemodelleringen innen finans er også basert på stokastiske prosesser generert av Markov-kjeder.

Programvare

I R er et ganske komplett bibliotek markovchain-pakken [3]
En liste over pythonpakker finner du her [4]
Mathematica har utviklet ad hoc-funksjoner for Markov-kjeder siden versjon 9.

Merknader

^ Markov-kjede | Definisjon av Markov-kjeden på amerikansk engelsk av Oxford Dictionaries , på Oxford Dictionaries | Engelsk . Hentet 27. november 2018 .
^ Billi, R., Canavesio, F., Ciaramella, A., & Nebbia, L. (1994, september). Interaktiv stemmeteknologi på jobben: CSELT-opplevelsen. I Interactive Voice Technology for Telecommunications Applications, 1994., Second IEEE Workshop on (s. 43-48). IEEE.
^ Giorgio Alfredo Spedicato [aut, cre og Tae Seung Kang, markovchain: Easy Handling Discrete Time Markov Chains , 26. august 2019. Hentet 13. september 2019 .
^ Martin Thoma, Python Markov Chain Packages , om Martin Thoma . Hentet 13. september 2019 .

Bibliografi

( EN ) Olle Häggström (2002), Finite Markov Chains and Algorithmic Applications , Cambridge University Press, ISBN 0-521-81357-3

Relaterte elementer

Andre prosjekter

Wikimedia Commons inneholder bilder eller andre filer om Markov-prosessen

Eksterne lenker

( EN ) Markov-prosessen , i Encyclopedia Britannica , Encyclopædia Britannica, Inc.