Markov kæde

I matematik er en Markov-kæde en diskret tid Markov-proces eller kontinuerlig tid og et diskret tilstandsrum. En Markov-proces er en stokastisk proces, der besidder Markov-egenskaben : informationen, der er nyttig til at forudsige fremtiden, er helt indeholdt i den nuværende tilstand af processen og er ikke afhængig af tidligere tilstande (systemet har ingen "hukommelse"). Markov-processer er opkaldt efter deres opfinder, Andrei Markov .

En diskret tid Markov-processen er en sekvens af tilfældige variable med værdier i staten rum , som vi vil bemærke i det følgende. Værdien er i øjeblikket processtilstanden. De applikationer, hvor tilstandsrummet er endeligt eller tælleligt, er utallige: man taler derefter om Markov- kæder eller om Markov-kæder med diskret tilstandsrum . De væsentlige egenskaber ved generelle Markov-processer , for eksempel gentagelses- og ergodicitetsegenskaber , kan angives eller bevises mere simpelt i tilfælde af Markov-kæder med diskret tilstand . Denne artikel vedrører netop Markov-kæderne med et diskret statsrum . ${\ displaystyle X_ {0},}$ ${\ displaystyle X_ {1},}$ ${\ displaystyle X_ {2},}$ ${\ displaystyle X_ {3}, \ \ dots}$ $E$ $X_ {n}$ $ikke.$ $E$

Andrei Markov offentliggjorde de første resultater om endelige statsrum Markov-kæder i 1906 . En generalisering til et utalligt uendeligt statsrum blev offentliggjort af Kolmogorov i 1936 . Markov processer er relateret til Brownsk bevægelse og den ergodic hypotese , to emner af statistiske fysik , der var meget vigtigt i begyndelsen af det XX th århundrede .

Svag Markov-ejendom

Definitioner

Dette er den karakteristiske egenskab ved en Markov-kæde: forudsigelsen af fremtiden fra nutiden gøres ikke mere præcis af yderligere informationer om fortiden, fordi al den information, der er nyttig til forudsigelsen af fremtiden, er indeholdt i den nuværende tilstand af processen. Den svage Markov-egenskab har flere ækvivalente former, som alle svarer til at observere, at den betingede lov om at kende fortiden, dvs. at kende kun er en funktion af : $X _ {{n + 1}}$ ${\ displaystyle \ left (X_ {k} \ right) _ {0 \ leq k \ leq n},}$ $X_ {n}$ ${\ begin {align} \ forall n \ geq 0, \ forall (i_ {0}, \ ldots, i _ {{n-1}}, i, j) & \ in E ^ {{n + 2}} , \\ {\ mathbb {P}} {\ Big (} X _ {{n + 1}} = j & \ mid \, X_ {0} = i_ {0}, X_ {1} = i_ {1} , \ ldots, X _ {{n-1}} = i _ {{n-1}}, X_ {n} = i {\ Big)} = {\ mathbb {P}} \ venstre (X _ {{ n + 1}} = j \ mid X_ {n} = i \ right). \ slut {justeret}}$

En almindelig variant af Markov-kæder er den homogene Markov-kæde , for hvilken sandsynligheden for overgangen er uafhængig af : $ikke$ ${\ displaystyle \ forall n \ geq 1, \ forall (i, j) \ i E ^ {2}, \ quad \ mathbb {P} (X_ {n + 1} = j \ mid X_ {n} = i) = \ mathbb {P} (X_ {n} = j \ mid X_ {n-1} = i)}$

I resten af artiklen vil kun homogene Markov-kæder blive taget i betragtning. For en interessant anvendelse af ikke- homogene Markov-kæder til kombinatorisk optimering , se artiklen Simuleret annealing . Der er en stærk Markov-egenskab , der er knyttet til forestillingen om stoptid : Denne stærke Markov-egenskab er afgørende for beviset for vigtige resultater (forskellige gentagelseskriterier, stærk lov for stort antal for Markov-kæder). Det fremgår af artiklen " Markov ejendom ".

Kriterium

Grundlæggende kriterium - Lad være en sekvens af uafhængige tilfældige variabler med samme lov med værdier i et mellemrum og enten et målbart kort over i Antag at sekvensen er defineret af gentagelsesrelationen: ${\ displaystyle Y = (Y_ {n}) _ {n \ geq 1}}$ $F$ $f$ $E \ gange F$ ${\ displaystyle E.}$ ${\ displaystyle X = (X_ {n}) _ {n \ geq 0}}$ $\ forall n \ geq 0, \ qquad X _ {{n + 1}} = f \ left (X_ {n}, Y _ {{n + 1}} \ right),$ og antag, at sekvensen er uafhængig af Then er en homogen Markov-kæde. $Y$ ${\ displaystyle X_ {0}.}$ $x$

Eksempel: problemet med klistermærkesamleren :

Petit Pierre samler portrætterne af de elleve spillere fra det nationale fodboldhold, som han finder på klistermærker inde i emballagen til chokoladestængerne; hver gang han køber en tablet, har han 1 til 11 chance for at finde portrættet af spiller nr. (for alt ). Bemærk status for Pierre Petit-samlingen efter åbning af emballagen til dens e- chokoladestang. er en Markov-kæde startende fra , fordi den passer i den forrige ramme for valget siden $k$ $k$ ${\ displaystyle X_ {n} \ i {\ mathcal {P}} ([\! [1,11] \!])}$ $ikke$ ${\ displaystyle X = (X_ {n}) _ {n \ geq 0}}$ ${\ displaystyle X_ {0} = \ emptyset}$ ${\ displaystyle F = [\! [1,11] \!], \ E = {\ mathcal {P}} (F), \ f (x, y) = x \ cup \ {y \},}$ $X _ {{n + 1}} = X_ {n} \ kop \ {Y _ {{n + 1}} \},$ hvor de tilfældige variabler er uafhængige og ensartede tilfældige variabler på : de er de successive tal for vignetterne trukket fra chokoladestængerne. Den gennemsnitlige tid, der kræves for at fuldføre samlingen (her det antal tabletter, som Petit Pierre skal købe i gennemsnit til at fuldføre sin samling) er for en samling af vignetter i alt, hvor er det th harmoniske nummer . For eksempel chokoladebarer. ${\ displaystyle Y_ {n}}$ ${\ displaystyle [\! [1,11] \!]}$ $IKKE$ ${\ displaystyle N \, H_ {N},}$ ${\ displaystyle H_ {N}}$ $IKKE$ ${\ displaystyle 11 \, H_ {11} = 33,2 \ dots \ quad}$

Bemærkninger:

Markov-ejendommen stammer fra uafhængigheden af det, det forbliver sandt, når de har forskellige love, og når "gentagelsesforholdet" afhænger af . Antagelserne ud over uafhængigheden er der kun for at sikre kædens homogenitet af Markov. ${\ displaystyle Y_ {i} \;}$ $Y_ {i}$ ${\ displaystyle X_ {n + 1} = f_ {n} \ venstre (X_ {n}, Y_ {n + 1} \ højre)}$ $ikke.$
Kriteriet er grundlæggende, idet enhver homogen Markov-kæde kan simuleres via en gentagelse af formen til en velvalgt funktion . Vi kan endda vælge og vælge uafhængige og ensartede variabler over intervallet [0,1], hvilket er praktisk til undersøgelse af Markov-kæder ved hjælp af Monte-Carlo-metoder . ${\ displaystyle X_ {n + 1} = f \ left (X_ {n}, Y_ {n + 1} \ right),}$ $f$ ${\ displaystyle F = [0,1],}$ ${\ displaystyle Y_ {j}}$

Overgangssandsynligheder

Definition

Definition - Nummeret kaldes sandsynligheden for tilstand- til- tilstand-overgang i et trin eller sandsynligheden for tilstand- til- stat-overgang, hvis der ikke er tvetydighed. Vi noterer ofte dette nummer ${\ displaystyle \ mathbb {P} \ left (X_ {1} = j \ mid X_ {0} = i \ right)}$ $jeg$ $j$ $jeg$ ${\ displaystyle j,}$ ${\ displaystyle p_ {i, j}:}$ $p _ {{i, j}} = {\ mathbb {P}} \ left (X _ {{1}} = j \ mid X_ {0} = i \ right).$

Familienumre kaldes overgangsmatrix , overgangskernen eller overgangsoperatøren af Markov-kæden. ${\ displaystyle P = \ left (p_ {i, j} \ right) _ {(i, j) \ in E ^ {2}}}$

Terminologien overgang matrix er den mest anvendte, men det er hensigtsmæssigt, strengt taget, kun når, for et helt tal Hvornår er endelig, for eksempel af cardinal kan man altid nummer elementerne i vilkårligt fra 1 til hvad indstiller problemet, men ufuldkomment, fordi denne omnummerering er kontraintuitiv i mange eksempler. ${\ displaystyle n \ geq 1,}$ ${\ displaystyle E = \ {1,2, \ ldots, n \}.}$ $E$ ${\ displaystyle n,}$ $E$ ${\ displaystyle n,}$

Ehrenfest-model: de to hunde og deres lopper:

To hunde deler lopper som følger: i hvert øjeblik vælges en af lopperne tilfældigt og hopper derefter fra en hund til en anden. Systemets tilstand er beskrevet af et element, hvor $IKKE$ $IKKE$ ${\ displaystyle x = (x_ {1}, x_ {2}, \ prikker, x_ {N}) \ i \ {0,1 \} ^ {N},}$ $x _ {{i}} = 0 {\ text {eller}} 1 {\ text {afhængigt af om chip n}} ^ {{\ circ}} \ i {\ text {er på 1. eller på 2. hund .}}$

Det har også elementer, men at nummerere dem fra 1 til ville være akavet at følge systemets udvikling, som består i at vælge en af koordinaterne tilfældigt og ændre dens værdi. Hvis vi vil forstå systemet mindre detaljeret (fordi vi ikke er i stand til at genkende en chip fra en anden), kan vi simpelthen studere antallet af chips på hund nr. 1, hvilket svarer til at vælge igen, for forståelse ville det være en skam at omnummerere staterne fra 1 til Bemærk at til denne nye modelisering, $E$ $2 ^ {N}$ $2 ^ {N}$ $IKKE$ $x$ ${\ displaystyle E = \ {0,1,2, \ dots, N \}.}$ ${\ displaystyle N + 1.}$ $p _ {{k, k + 1}} = {\ tfrac {Nk} N} {\ text {et}} p _ {{k, k-1}} = {\ tfrac {k} N},$ da f.eks. antallet af chips på bagsiden af hund nr. 1 går fra k til k-1, hvis det er en af disse k- chips, der vælges til at hoppe, blandt de N- chips, der er til stede i "systemet". Denne model omtales oftere som “ Ehrenfest Urns Model ”. Det blev introduceret i 1907 af Tatiana og Paul Ehrenfest for at illustrere nogle af de "paradokser", der opstod i fundamentet for den spirende statistiske mekanik, og for at modellere lyserød støj . Den Ehrenfest urne model blev behandlet af matematiker Mark Kac at være "nok en af de mest instruktive modeller i alle fysik."

I stedet for at nummerere staterne fra 1 er det derfor i mange tilfælde mere ergonomisk at acceptere endelige eller uendelige matricer, hvis rækker og kolonner er "nummererede" ved hjælp af elementerne i Produktet af to sådanne "matricer", og defineres derefter meget naturligt ved ${\ displaystyle E.}$ ${\ displaystyle A = \ left (a_ {i, j} \ right) _ {(i, j) \ in E ^ {2}}}$ ${\ displaystyle B = \ left (b_ {i, j} \ right) _ {(i, j) \ i E ^ {2}}}$ $(AB) _ {{i, j}} = \ sum _ {{\ ell \ i E}} a _ {{i, \ ell}} b _ {{\ ell, j}},$ analogt med den mere klassiske formel for produktet af to kvadratiske matricer af størrelse ${\ displaystyle n,}$ $(AB) _ {{i, j}} = \ sum _ {{k = 1}} ^ {n} a _ {{i, k}} b _ {{k, j}}.$

Ejendomme

Proposition - Overgangsmatrixen er stokastisk : summen af vilkårene for en række giver altid 1. ${\ displaystyle P = \ left (p_ {i, j} \ right) _ {(i, j) \ in E ^ {2}}}$ $P$ $\ forall i \ i E, \ quad \ sum _ {{j \ i E}} p _ {{i, j}} = 1.$

Proposition - Loven i Markov-kæden er kendetegnet ved parret, der består af dets overgangsmatrix og dets oprindelige lov (loven om ): for al den fælles lovgivning er givet af ${\ displaystyle X = \ left (X_ {n} \ right) _ {n \ geq 0}}$ ${\ displaystyle P,}$ $X_ {0}$ $n \ geq 1$ ${\ displaystyle (X_ {0}, X_ {1}, \ ldots, X_ {n})}$ ${\ mathbb {P}} \ left (X _ {{0}} = i_ {0}, X _ {{1}} = i_ {1}, \ ldots, X _ {{n-1}} = i _ {{n -1}}, X _ {{n}} = i_ {n} \ højre) = {\ mathbb {P}} \ venstre (X _ {{0}} = i_ {0} \ højre) \ p _ {{i_ {{0}}, i_ {1}}} \, p _ {{i _ {{1}}, i_ {2}}} \, \ ldots \, p _ {{i _ {{n-2}}, i _ {{n-1}}} \, p _ {{i _ {{n-1}}, i_ {n}}}.$

Demonstration

Ved induktion, på rang 0, ${\ mathbb {P}} \ left (X _ {{0}} = i_ {0} \ right) = {\ mathbb {P}} \ left (X _ {{0}} = i_ {0} \ right ).$

I rækken ved at stille ${\ displaystyle n,}$ ${\ displaystyle P_ {k} = \ mathbb {P} \ left (X_ {0} = i_ {0}, X_ {1} = i_ {1}, \ ldots, X_ {k-1} = i_ {k- 1}, X_ {k} = i_ {k} \ højre),}$ ${\ frac {P_ {n}} {P _ {{n-1}}}} = {\ mathbb {P}} {\ Big (} X _ {{n}} = i_ {n} \ mid \, X_ {0} = i_ {0}, X_ {1} = i_ {1}, \ ldots, X _ {{n-1}} = i _ {{n-1}} {\ Big)} = p _ {{i _ {{n-1}}, i_ {n}}},$ i kraft af den svage Markov-ejendom, så hvis har det forventede udtryk, så også. ${\ displaystyle P_ {n-1}}$ $P_ {n}$

Når vi studerer en bestemt Markov-kæde, er dens overgangsmatrix generelt veldefineret og fast i hele undersøgelsen, men den oprindelige lov kan ændre sig under undersøgelsen, og notationerne skal afspejle den oprindelige lov, der overvejes i øjeblikket: hvis i et øjeblik af undersøgelsen betragter vi en Markov-kæde af indledende fordeling defineret af, så sandsynlighederne noteres, og forventningerne noteres Især hvis vi siger, at Markov-kæden starter fra sandsynlighederne noteres, og forventningerne noteres ${\ displaystyle \ forall i \ i E, \ quad \ mathbb {P} \ left (X_ {0} = i \ right) = \ mu _ {i}, \ quad}$ ${\ displaystyle \ mathbb {P} _ {\ mu} \ left (\ dots \ right), \ quad}$ ${\ displaystyle \ mathbb {E} _ {\ mu} \ left [\ dots \ right]. \ quad}$ ${\ displaystyle \ mathbb {P} \ left (X_ {0} = j \ right) = 1, \ quad}$ ${\ displaystyle j, \ quad}$ ${\ displaystyle \ mathbb {P} _ {j} \ left (\ dots \ right), \ quad}$ ${\ displaystyle \ mathbb {E} _ {j} \ left [\ dots \ right]. \ quad}$

Overgangsmatrixens beføjelser

For sandsynligheden for overgang i trin afhænger ikke af : ${\ displaystyle k \ geq 1,}$ $k$ ${\ displaystyle \ mathbb {P} \ left (X_ {n + k} = j \ mid X_ {n} = i \ right),}$ $ikke$

Proposition - Den overgangsmatricen i trin , er lig med magt th af overgangsmatricen Vi note $k$ ${\ displaystyle \ left (\ mathbb {P} \ left (X_ {n + k} = j \ mid X_ {n} = i \ right) \ right) _ {(i, j) \ in E ^ {2} },}$ $k$ $P.$ $p _ {{i, j}} ^ {{(k)}} = {\ mathbb {P}} \ left (X _ {{n + k}} = j \ mid X_ {n} = i \ right) ,$ og $P ^ {k} = \ venstre (p _ {{i, j}} ^ {{(k)}} \ højre) _ {{(i, j) \ i E ^ {2}}}.$

Demonstration

Ved gentagelse. På rang 1 er det en konsekvens af homogeniteten af Markov-kæden, der allerede er nævnt i afsnittet Svag Markov-egenskab : ${\ mathbb {P}} \ left (X _ {{n + 1}} = j \ mid X_ {n} = i \ right) = {\ mathbb {P}} \ left (X _ {{1}} = j \ mid X_ {0} = i \ right).$

Rang ${\ displaystyle k,}$ ${\ begin {align} {\ mathbb {P}} \ left (X_ {n} = i {\ text {and}} X _ {{n + k}} = j \ right) & = \ sum _ {{ \ ell \ i E}} {\ mathbb {P}} \ left (X_ {n} = i, \, X _ {{n + k-1}} = \ ell {\ text {and}} X _ { {n + k}} = j \ right) \\ & = \ sum _ {{\ ell \ in E}} {\ mathbb {P}} \ left (X_ {n} = i, \, X _ {{ n + k- 1}} = \ ell \ right) \ {\ mathbb {P}} \ left (X _ {{n + k}} = j \ mid X_ {n} = i, \, X _ {{ n + k-1}} = \ ell \ right) \\ & = \ sum _ {{\ ell \ in E}} {\ mathbb {P}} \ left (X_ {n} = i, \, X _ {{n + k-1}} = \ ell \ right) \ p _ {{\ ell, j}} \\ & = {\ mathbb {P}} \ left (X_ {n} = i \ right) \ \ sum _ {{\ ell \ in E}} p _ {{i, \ ell}} ^ {{(k-1)}} \ p _ {{\ ell, j}} \\ & = {\ mathbb {P}} \ venstre (X_ {n} = i \ højre) \ p _ {{i, j}} ^ {{(k)}}, \ slut {justeret}}$ eller

den 1 st lighed er den tredje aksiom af sandsynlighed ,
den 2 nd lighed er definitionen af en betinget sandsynlighed ,
den 3 th lighed skyldes en form for lav Markov ejendom,
den 4. th lighed er en gentagelse ejendommen ikke ${\ displaystyle k-1,}$
den 5 th lighed er formlen af produktet fra to "arrays", anvendt på produktet af med ${\ displaystyle P ^ {k-1}}$ $P.$

Afslutningsvis deler vi de to ekstreme udtryk for denne rækkefølge af lighed med, medmindre dette sidste udtryk er nul, i hvilket tilfælde vi kan definere vilkårligt, derfor f.eks. Lig med ${\ displaystyle \ mathbb {P} \ left (X_ {n} = i \ right),}$ ${\ displaystyle \ mathbb {P} \ left (X_ {n + k} = j \ mid X_ {n} = i \ right)}$ ${\ displaystyle p_ {i, j} ^ {(k)}.}$

Ved en simpel anvendelse af den samlede sandsynlighedsformel udleder vi de marginale love i Markov-kæden.

Korollar - Loven om er givet ved ${\ displaystyle X_ {n + k}}$ ${\ mathbb {P}} \ left (X _ {{n + k}} = j \ right) = \ sum _ {{i \ in E}} {\ mathbb {P}} \ left (X _ {{ n}} = i \ right) p _ {{i, j}} ^ {{(k)}}.$

I særdeleshed, ${\ mathbb {P}} \ left (X _ {{n}} = j \ right) = \ sum _ {{i \ in E}} {\ mathbb {P}} \ left (X _ {{0} } = i \ right) p _ {{i, j}} ^ {{(n)}}.$

I matrixskrivning, hvis loven om betragtes som en linie-vektor med den omformuleres til: ${\ displaystyle X_ {n}}$ ${\ displaystyle \ mu _ {n} = (\ mu _ {n, i}) _ {i \ i E},}$ ${\ displaystyle \ mu _ {n, i} = \ mathbb {P} \ left (X_ {n} = i \ right),}$ $\ mu _ {{n + k}} = \ mu _ {{n}} P ^ {k} \ quad {\ text {and}} \ quad \ mu _ {{n}} = \ mu _ {{0 }} P ^ {n}.$

Klassificering af stater

For vi siger, at det er tilgængeligt fra hvis og kun hvis det eksisterer sådan, at vi betegner: ${\ displaystyle (i, j) \ i E ^ {2}}$ $j$ $jeg$ $n \ geq 0$ ${\ displaystyle \ mathbb {P} (X_ {n} = j \ mid X_ {0} = i)> 0.}$ $\ {j \ leftarrow i \} \ quad \ Leftrightarrow \ quad \ left \ {\ findes n \ geq 0 {\ tekst {såsom}} p _ {{, i}} ^ {{(n)}}> 0 \ højre \}.$

Vi siger det og kommunikerer, hvis og kun hvis de eksisterer sådan, og vi betegner: $jeg$ $j$ ${\ displaystyle (n, m) \ in \ mathbb {N} ^ {2}}$ ${\ displaystyle \ mathbb {P} (X_ {n} = j \ mid X_ {0} = i)> 0}$ ${\ displaystyle \ mathbb {P} (X_ {m} = i \ mid X_ {0} = j)> 0.}$ $\ {j \ leftrightarrow i \} \ quad \ Leftrightarrow \ quad \ left \ {j \ leftarrow i {\ text {and}} i \ leftarrow j \ right \}.$

Forholdet til kommunikation , bemærket er en ækvivalensrelation . Når vi taler om klasse, når vi taler om staterne i en Markov-kæde, er det generelt til ækvivalensklasser for den relation , vi henviser til. Hvis alle stater kommunikerer, siges Markov-kæden at være irreducerbar . ${\ displaystyle \ leftrightarrow,}$ $\ venstresteg$

Forholdet til at være tilgængeligt , betegnet, strækker sig til ækvivalensklasser: for to klasser, og det har vi ${\ displaystyle \ leftarrow,}$ $VS$ ${\ displaystyle C ^ {\ prime}}$ $\ {C \ leftarrow C ^ {{\ prime}} \} \ quad \ Leftrightarrow \ quad \ left \ {\ findes (i, j) \ i C \ gange C ^ {{\ prime}}, \ qquad i \ leftarrow j \ right \} \ quad \ Leftrightarrow \ quad \ left \ {\ forall (i, j) \ in C \ times C ^ {{\ prime}}, \ qquad i \ leftarrow j \ right \}.$

Forholdet er en ordenforhold mellem ækvivalensklasser. $\ venstre pil$

En klasse siges at være endelig, hvis den ikke fører til nogen anden, dvs. hvis klassen er minimal for forholdet, ellers siges den at være forbigående . At høre til en endelig eller forbigående klasse har konsekvenser for de probabilistiske egenskaber ved en tilstand i Markov-kæden, især på dens status som en tilbagevendende tilstand eller en forbigående tilstand . Antallet og karakteren af de afsluttende klasser dikterer strukturen for sæt af stationære sandsynligheder , som nøjagtigt opsummerer den asymptotiske opførsel af Markov-kæden, som det kan ses i det næste afsnit og i de to eksempler, der er beskrevet i slutningen af denne side. ${\ displaystyle \ leftarrow.}$

Er $M _ {{ij}} = \ venstre \ {n \ geq 1 \ | \ p _ {{i, j}} ^ {{(n)}}> 0 \ højre \}.$

Den periode af en stat er GCD af sættet. Hvis to stater kommunikere, de har samme periode: Vi kan derfor tale om den periode af en klasse af stater. Hvis perioden er 1, siges klassen at være aperiodisk . Aperiodiciteten af tilstandene i en Markov-kæde betinger konvergensen af loven mod den stationære sandsynlighed, se siden Stationær sandsynlighed for en Markov-kæde . $jeg$ ${\ displaystyle M_ {ii}.}$ $X_ {n}$

Klassificeringen af stater og deres periode kan let læses på Markov-kædediagrammet . Men hvis alle elementerne i overgangsmatrixen er strengt positive, er Markov-kæden irreducerbar og aperiodisk: tegning af grafen for Markov-kæden er overflødig.

Stationær lov

Definition

Der kan være en eller flere målinger på tilstandsrummet såsom: ${\ displaystyle \ pi = (\ pi _ {i}) _ {i \ i E},}$ ${\ displaystyle E,}$ $\ pi = \ pi \, P,$ eller endda $\ forall j \ i E, \ qquad \ pi _ {j} = \ sum _ {{i \ i E}} \ pi _ {i} \, p _ {{i, j}}.$

En sådan måling kaldes en stationær måling . Et stationært mål er en egenfunktion af transponeringen af overgangsmatrixen, der er knyttet til egenværdien 1. Det kaldes stationær sandsynlighed eller stationær lov, hvis den opfylder de yderligere betingelser: $\ pi$

$\ forall i \ i E, \ qquad \ pi _ {i} \ \ geq \ 0,$
$\ sum _ {{i \ i E}} \ pi _ {i} \ = \ 1.$

Udtrykket " stationær " er begrundet i følgende forslag:

Proposition - Hvis den oprindelige lov i Markov-kæden (dvs. loven om ) er en stationær sandsynlighed, så er loven for alle stadig $X_ {0}$ ${\ displaystyle \ pi,}$ ${\ displaystyle n \ geq 0,}$ $X_ {n}$ ${\ displaystyle \ pi.}$

Demonstration

Dette følger af egenskaberne for kræfterne i overgangsmatrixen givet ovenfor: loven μ n af X n udtrykkes som en funktion af loven μ 0 af X 0 som følger: eller medfører ${\ displaystyle \ mu _ {n} = \ mu _ {0} P ^ {n} = \ pi P ^ {n},}$ ${\ displaystyle \ pi P = \ pi}$ ${\ displaystyle \ pi P ^ {n} = \ pi. \}$

Mere generelt er Markov-kæden en stationær proces, hvis og kun hvis dens oprindelige lov er en stationær sandsynlighed .

Eksistens og unikhed

I tilfælde af Markov-kæder med diskret tilstand bestemmer visse egenskaber ved processen, om der er en stationær sandsynlighed eller ej, og om den er unik eller ej:

en Markov-kæde er irreducerbar, hvis en hvilken som helst stat er tilgængelig fra enhver anden stat;
en tilstand er tilbagevendende positiv, hvis forventningen om tidspunktet for første tilbagevenden til denne tilstand, startende fra denne tilstand, er endelig.

Hvis en Markov-kæde har mindst en positiv tilbagevendende tilstand, er der en stationær sandsynlighed. Hvis der er en stationær sandsynlighed sådan , at tilstanden er positiv tilbagevendende, og omvendt. $\ pi$ ${\ displaystyle \ pi _ {i}> 0}$ $jeg$

Sætning - Hvis en Markov-kæde kun har en endelig klasse, er der højst en stationær sandsynlighed. Vi har derefter ækvivalens mellem de 3 propositioner: ${\ displaystyle C,}$

der er en unik stationær sandsynlighed, bemærket ${\ displaystyle \ pi,}$
der er en positiv tilbagevendende tilstand,
alle stater i den sidste klasse er positive tilbagevendende.

Vi har også ækvivalensen $\ {\ pi _ {i}> 0 \} \ Leftrightarrow \ {i \ i C \} \ Leftrightarrow \ {i {\ text {er tilbagevendende positiv}} \}.$

Denne sætning gælder især for irreducerbare Markov-kæder, da sidstnævnte kun har en klasse (som derfor nødvendigvis er en endelig klasse); især kontrollerer de irreducerbare Markov-kæder ${\ displaystyle C = E.}$

Stærk lov af stort antal og ergodicitet

I tilfælde af en irreducerbar og tilbagevendende positiv Markov- kæde er den stærke lov for et stort antal i kraft: middelværdien af en funktion over forekomsterne af Markov-kæden er lig med dens middel i henhold til dens stationære sandsynlighed. Mere præcist under antagelse $f$ $\ sum _ {{i \ in E}} | f (i) | \, \ pi _ {i} \ <+ \ infty,$ vi har næsten helt sikkert : $\ lim _ {{n}} \; {\ frac {1} {n}} \; \ sum _ {{k = 0}} ^ {{n-1}} f (X_ {k}) \ = \ \ sum _ {{i \ in E}} f (i) \, \ pi _ {i} \ = \ \ pi f.$

Gennemsnittet af værdien af forekomsterne er derfor på lang sigt lig med forventningen i henhold til den stationære sandsynlighed. Især denne ækvivalens om midlerne gælder, hvis er indikatorfunktion af en delmængde af tilstandsrummet: $f$ $PÅ$ $\ lim _ {{n}} \; {\ frac {1} {n}} \; \ sum _ {{k = 0}} ^ {{n-1}} \ chi _ {A} (X_ {k }) \ = \ \ sum _ {{i \ i A}} \ \ pi _ {i} \ = \ \ pi (A).$

Dette gør det muligt at nærme sig den stationære sandsynlighed ved hjælp af den empiriske fordeling (som er et histogram konstrueret ud fra en bestemt sekvens), som i tilfældet med tilfældig gang med barriere .

Især hvis processen bygges ved at tage den stationære sandsynlighed som den oprindelige lov, defineres skiftet af $\ theta$ $x = (x_ {0}, x_ {1}, x_ {2}, \ dots) \ i E ^ {{{\ mathbb {N}}}} \ quad \ rightarrow \ quad \ theta \, x = (x_ {1}, x_ {2}, x_ {3}, \ prikker)$ bevarer foranstaltningen, hvilket gør Markov-kæden til et målt dynamisk system . Den stærke lov om stort antal resulterer i, at Markov-kæden er et ergodisk dynamisk system . Ergodicitet er både stærkere end den stærke lov for store tal, fordi vi for eksempel kan udlede, at der har en næsten bestemt grænse, men det er også svagere, fordi det i princippet kræver Markov-kædens stationaritet, hvilket ikke er tilfældet med den stærke lov af stort antal. ${\ displaystyle {\ frac {1} {n}} \; \ sum _ {k = 0} ^ {n-1} f (X_ {k}, X_ {k + 1}),}$ ${\ displaystyle \ sum _ {i, j \ i E} f (i, j) \, \ pi _ {i} p_ {i, j},}$

Konvergens mod den stationære lov

Hvis Markovkæde er irreducible , positiv tilbagevendende og aperiodisk, derefter konvergerer til en matrix, som hver række er den unikke stationære fordeling Især loven af konvergerer til uafhængigt af den oprindelige lov I tilfælde af et tilstandsrum færdig, dette er bevist af Perron-Frobenius sætningen . Bemærk, at det er naturligt, at sekvensen, der er defineret ved induktion af forholdet , muligvis for at begrænse et fast punkt for denne transformation, dvs. en opløsning af ligningen ${\ displaystyle P ^ {k}}$ ${\ displaystyle \ pi.}$ $\ mu _ {n}$ $X_ {n}$ $\ pi$ ${\ displaystyle \ mu _ {0}.}$ ${\ displaystyle \ mu _ {n},}$ ${\ displaystyle \ mu _ {n + 1} = \ mu _ {n} P,}$ ${\ displaystyle \ pi = \ pi P.}$

Endelig tilstand plads Markov kæder

Hvis en Markov-kæde er irreducerbar, og hvis dens tilstandsrum er endelig, er alle dens tilstande positive tilbagevendende. Den stærke lov med stort antal er så gældende.

Mere generelt er alle elementerne i en endelig endelig klasse positive tilbagevendende, uanset om tilstandsrummet er endeligt eller uendeligt tælleligt.

Kvasistationelle fordelinger af en absorberet Markov-kæde

Lad være en Markov-kæde over sæt af naturlige tal . Antag, at tilstand 0 absorberer og kæden absorberes næsten 0. Lade være absorptionen tid på 0. Vi siger, at en sandsynlighed på en kvasi-stationær fordeling, hvis for alle og for alle , $(X_ {n})$ ${\ displaystyle \ {0,1,2, ... \}}$ ${\ displaystyle T_ {0} = \ inf \ {n \ geq 0, X_ {n} = 0 \}}$ $\nøgen$ ${\ displaystyle \ {1,2,3, ... \}}$ ${\ displaystyle j \ geq 1}$ $n \ geq 1$

{\ displaystyle \ sum _ {i \ geq 1} \ nu _ {i} \ mathbb {P} (X_ {n} = j | X_ {0} = i, T_ {0}> n) = \ nu _ { j}.}

Vi siger, at en sandsynlighed på en Yaglom grænse , hvis for alt og alt , $\ mu$ ${\ displaystyle \ {1,2,3, ... \}}$ $i \ geq 1$ ${\ displaystyle j \ geq 1}$

{\ displaystyle \ lim _ {n \ to \ infty} \ mathbb {P} (X_ {n} = j | X_ {0} = i, T_ {0}> n) = \ mu _ {j}.}

En Yaglom-grænse er en kvasi-stationær distribution . Hvis den findes, er Yaglom-grænsen unik. På den anden side kan der være flere kvasi-stationære distributioner.

Hvis der er en kvasi-stationær fordeling, så findes der et reelt antal sådan, at . $\nøgen$ ${\ displaystyle \ rho (\ nu) \ in] 0.1 [}$ ${\ displaystyle \ sum _ {i} \ nu _ {i} \ mathbb {P} (T_ {0}> n | X_ {0} = i) = \ rho (\ nu) ^ {n}}$

Bedømmelse

I ovenstående formler er elementet ( ) sandsynligheden for overgangen fra til . Summen af elementerne i en række er altid lig med 1, og den stationære fordeling gives af venstre egenvektor i overgangsmatrixen. $jeg, j$ $jeg$ $j$

Nogle gange støder vi på overgangsmatricer, hvor udtrykket ( ) er sandsynligheden for overgang fra til , i hvilket tilfælde overgangsmatricen simpelthen er transponeret af det, der er beskrevet her. Summen af elementerne i en søjle er derefter værd 1. Desuden gives den stationære fordeling af systemet af højre egenvektor i overgangsmatrixen i stedet for den venstre egenvektor. $jeg, j$ $j$ $jeg$

Eksempel: Hamster Doudou

Hamsteren Doudou kender kun tre steder i sit bur: spånerne hvor han sover, føderen hvor han spiser og hjulet hvor han træner. Hans dage ligner hinanden meget, og hans aktivitet er let repræsenteret af en Markov-kæde. Hvert minut kan han enten ændre sin aktivitet eller fortsætte den, han lavede. Navnet proces uden hukommelse er slet ikke overdrevet at tale om Doudou.

Når han sover, har han en 9 ud af 10 chance for ikke at vågne op i det næste minut.
Når han vågner, er der en 1 ud af 2 chance for at han vil spise og en 1 ud af 2 chance for at han vil træne.
Måltidet varer kun et minut, hvorefter han gør noget andet.
Efter at have spist, er der en chance for 3 ud af 10, at han vil løbe i hjulet, men især en 7 ud af 10 chance for, at han går i seng igen.
Løb er trættende for Doudou; der er en 8 ud af 10 chance for, at han vil sove igen efter et minut. Ellers glemmer han fortsat, at han allerede er lidt træt.

Diagrammer

Diagrammer kan vise alle pile, der hver repræsenterer en sandsynlighed for overgang. Det er dog mere læsbart, hvis:

vi tegner ikke pilene med nul sandsynlighed (overgang umulig);
vi trækker ikke sløjferne (en stats pil mod sig selv) . Men de eksisterer; deres sandsynlighed er underforstået, fordi vi ved, at summen af sandsynligheden for pilene, der forlader fra hver stat, skal være lig med 1.

Eksempel med implicitte sløjfer
Eksempel med trukkede løkker

Overgangsmatrix

Overgangsmatricen af dette system er som følger (rækkerne og kolonnerne svarer således til tilstandene repræsenteret i chippen , feeder , hjul graf ): $P = {\ begin {bmatrix} 0,9 & 0,05 & 0,05 \\ 0,7 & 0 & 0,3 \\ 0,8 & 0 & 0,2 \\\ slutning {bmatrix}}$

Prognoser

Lad os antage, at Doudou sover i løbet af undersøgelsens første minut. ${\ mathbf {x}} ^ {{0)}} = {\ begynder {bmatrix} 1 & 0 & 0 \ end {bmatrix}}$

Efter et minut kan vi forudsige: ${\ mathbf {x}} ^ {{(1)}} = {\ mathbf {x}} ^ {(0)}} P = {\ begin {bmatrix} 1 & 0 & 0 \ end {bmatrix}} {\ begin {bmatrix} 0,9 & 0,05 & 0,05 \\ 0,7 & 0 & 0,3 \\ 0,8 & 0 & 0,2 \\\ slutning {bmatrix}} = {\ start {bmatrix} 0,9 & 0,05 & 0,05 \ slut {bmatrix} }$

Således er der efter et minut en 90% chance for at Doudou stadig sover, 5% for at han vil spise og 5% for at han løber.

${\ mathbf {x}} ^ {{(2)}} = {\ mathbf {x}} ^ {{(1)}} P = {\ mathbf {x}} ^ {{(0)}} P ^ {2} = {\ begin {bmatrix} 1 & 0 & 0 \ slut {bmatrix}} {\ begin {bmatrix} 0,9 & 0,05 & 0,05 \\ 0,7 & 0 & 0,3 \\ 0,8 & 0 & 0,2 \\\ slutning {bmatrix}} ^ {2} = {\ begin {bmatrix} 0,885 & 0,045 & 0,07 \ end {bmatrix}}$

Efter 2 minutter er der en 4,5% chance for, at hamsteren spiser.

Generelt set i minutter: $ikke$ ${\ mathbf {x}} ^ {{(n)}} = {\ mathbf {x}} ^ {{(n-1)}} P$ og ${\ mathbf {x}} ^ {{(n)}} = {\ mathbf {x}} ^ {{(0)}} P ^ {n}$

Teorien viser, at sandsynligheden efter en vis tid er uafhængig af den oprindelige lov. Lad os bemærke det : $q$ ${\ mathbf {q}} = \ lim _ {{n \ to \ infty}} {\ mathbf {x}} ^ {{(n)}}$

Vi opnår konvergens, hvis og kun hvis kæden er aperiodisk og irreducerbar . Dette er tilfældet i vores eksempel, så vi kan skrive: ${\ begin {align} P & = {\ begin {bmatrix} 0,9 & 0,05 & 0,05 \\ 0,7 & 0 & 0,3 \\ 0,8 & 0 & 0,2 \\\ slutning {bmatrix}} \\ {\ mathbf {q} } P & = {\ mathbf {q}} \ qquad {\ mbox {(}} {\ mathbf {q}} {\ mbox {er den uforanderlige lov med hensyn til}} P {\ mbox {.)}} \ \ & = {\ mathbf {q}} I \\ {\ mathbf {q}} (IP) & = {\ mathbf {0}} \\ & = {\ mathbf {q}} \ left ({\ begin { bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\\ end {bmatrix}} - {\ begin {bmatrix} 0,9 & 0,05 & 0,05 \\ 0,7 & 0 & 0,3 \\ 0,8 & 0 & 0,2 \\\ slutning {bmatrix}} \ højre) \\ & = {\ mathbf {q}} {\ begynder {bmatrix} 0.1 & -0.05 & -0.05 \\ - 0.7 & 1 & -0.3 \ \ - 0.8 & 0 & 0, 8 \\\ end {bmatrix}} \\ & = {\ begin {bmatrix} q_ {1} & q_ {2} & q_ {3} \ end {bmatrix}} {\ begin {bmatrix} 0,1 & -0, 05 & -0,05 \\ - 0,7 & 1 & -0,3 \\ - 0,8 & 0 & 0,8 \\\ slutning {bmatrix}} \\ & = {\ start {bmatrix} 0 & 0 & 0 \ end {bmatrix}} \ end {justeret}}$

Når vi ved det, opnår vi: $q_ {1} + q_ {2} + q_ {3} = 1$ ${\ begin {bmatrix} q_ {1} & q_ {2} & q_ {3} \ end {bmatrix}} = {\ begin {bmatrix} 0.884 & 0.0442 & 0.0718 \ end {bmatrix}}$

Doudou bruger derfor 88,4% af sin tid på at sove, 4,42% spiser og 7,18% løber.

Illustration af virkningen af modellen

Det følgende eksempel sigter mod at vise vigtigheden af modellering af systemet. God modellering gør det muligt at besvare komplekse spørgsmål med enkle beregninger.

Vi studerer en (fiktiv) civilisation, der består af flere sociale klasser, og hvor enkeltpersoner kan bevæge sig fra en klasse til en anden. Hvert trin repræsenterer et år. Vi vil overveje en slægt snarere end en person for at undgå at skaffe to hundrede år. Der er fire forskellige sociale statuser:

slave;
ledig;
borger;
høj embedsmand.

I dette firma:

slaver kan forblive slaver eller blive frie mænd (ved at købe deres frihed eller ved at blive befriet liberalt af deres herre);
frie mænd kan forblive frie eller sælge deres frihed (til at betale deres gæld osv.) eller endda blive borgere (igen ved fortjeneste eller ved at købe titlen som borger);
borgere er borgere for livet og overfører deres statsborgerskab til deres slægt (man kunne tro, at antallet af borgere har en tendens til at stige, og at efter en vis tid er alle borgere, men historisk set er borgerne i de civilisationer, der fulgte dette mønster, decimeret af krigene og nye slaver ankommer regelmæssigt fra udlandet). De kan også stille op som kandidater til årlige valg for at blive højtstående embedsmænd (dommere). Ved afslutningen af deres mandat kan de genvalges eller blive almindelige borgere igen.

For at komplicere eksemplet lidt og således vise omfanget af ansøgningerne fra Markov-kæderne vil vi overveje, at embedsmænd er valgt i flere år. Derfor afhænger fremtiden for en individuel embedsmand af, hvor længe han har været offentlig tjenestemand. Vi er derfor i tilfælde af en ikke-homogen Markov-kæde. Heldigvis kan vi let komme tilbage til en homogen kæde. Faktisk er det tilstrækkeligt at tilføje en kunstig tilstand for hvert år af mandatet. I stedet for at have en stat 4: Officiel , vil vi have en stat:

4: embedsmand ved starten af sit mandat;
5: embedsmand i andet mandatår
etc.

Sandsynlighederne, der forbinder to på hinanden følgende kunstige tilstande (f.eks. Tredje og fjerde år), har værdi 1, fordi man mener, at ethvert mandat, der startede, slutter (man kunne modellere det modsatte ved at ændre værdien af disse sandsynligheder). Lad os fastsætte mandaternes varighed til to år, hvor kontingenten af embedsmænd kan fornyes med halvdelen hvert år. Vi har derefter følgende graf:

For at modellere valg, der ikke er årlige, ville det også være nødvendigt at tilføje fiktive stater (valgår, et år siden sidste valg osv.).

Matrixen skrives derefter: $P$ ${\ mathbf {P}} = {\ begin {bmatrix} {\ frac {97} {98}} & {\ frac {1} {98}} & 0 & 0 & 0 \\ {\ frac {2} { 73}} & {\ frac {65} {73}} & {\ frac {6} {73}} & 0 & 0 \\ 0 & 0 & {\ frac {12} {13}} & {\ frac { 1} {13}} & 0 \\ 0 & 0 & 0 & 0 & 1 \ \ 0 & 0 & {\ frac {7} {8}} & {\ frac {1} {8}} & 0 \ end {bmatrix}}$

Som forklaret ovenfor, angiv overgangssandsynlighederne i trin. Så sandsynligheden for at være i staten efter år for en slægt, der er en del af den sociale klasse . For at vide, hvad der bliver af en slave efter år, er det tilstrækkeligt at skrive: $P ^ {{n}}$ $ikke$ $p _ {{ij}} ^ {{n}}$ $j$ $ikke$ $jeg$ $ikke$ ${\ displaystyle {\ begin {bmatrix} 1 & 0 & 0 & 0 & 0 \ end {bmatrix}} \ times \ mathbf {P} ^ {(n)} = {\ begin {bmatrix} p_ {1} ^ { (n)} & p_ {2} ^ {(n)} & p_ {3} ^ {(n)} & p_ {4} ^ {(n)} & p_ {5} ^ {(n)} \ slut {bmatrix}}}$

Hvor er sandsynligheden for at være i den sociale klasse efter år med at vide, at den studerede linje har forladt slavestaten? $p_ {i} ^ {{n}}$ $jeg$ $ikke$

Hvis vi kender antallet af hver social klasse i år 0, er det tilstrækkeligt at beregne: ${\ frac 1 {\ mathrm {lign {\ acute e} es}}} \ times {\ begin {bmatrix} {\ rm {slaver}} & {\ rm {gratis}} & {\ rm {borgere}} & {\ rm {{\ acute e} lus_ {1}}} & {\ rm {{\ acute e} lus_ {2}}} \ end {bmatrix}} \ times {\ mathbf P} ^ {{n}} = Y$

Vi opnår således fordelingen af befolkningen i de forskellige sociale klasser (i slutningen af årene). Ved at gange denne vektor med den samlede størrelse af befolkningen opnår vi størrelsen på hver klasse i slutningen af årene. $ikke$ $Y$ $ikke$

Lad os nu stille os følgende spørgsmål: "I slutningen af årene, hvor mange linjer vil der allerede have haft en højtstående embedsmand, der har afsluttet sit mandat?" " $ikke$

Svaret adskiller sig fra antallet af mandater, der er udført i år, fordi der er mulighed for at blive genvalgt. Det virker vanskeligt at besvare dette spørgsmål (det bør stadig være muligt). Faktisk er det tilstrækkeligt at ændre modelleringen af problemet. Så lad os gå videre til en ny model for at besvare dette spørgsmål. (På den anden side tillader det os ikke at besvare de tidligere spørgsmål, deraf præsentationen af de to modeller.) $ikke$

Det er tilstrækkeligt at ændre grafen som følger:

Vi tilføjer en absorberende top, fordi når en linje er færdig med et mandat, tages den ikke længere i betragtning.

Hvis nogle læsere er kritiske, kan de sige, at modellen er forkert, fordi linjer med en valgt embedsmand ikke længere deltager i valget. Det er ikke sådan. Antallet af valgte embedsmænd er faktisk proportionalt med antallet af borgere. At ikke genindsætte tidligere højtstående embedsmænd blandt kandidaterne ændrer derfor ikke sandsynligheden for, at en borger bliver valgt, fordi antallet af stillinger, der tilbydes, også er antallet af borgere. Denne model giver dig mulighed for nøjagtigt at besvare det stillede spørgsmål.

Vi har derfor en ny overgangsmatrix: ${\ mathbf {Q}} = {\ begin {bmatrix} {\ frac {97} {98}} & {\ frac {1} {98}} & 0 & 0 & 0 & 0 \\ {\ frac {2 } {73}} & {\ frac {65} {73}} & {\ frac {6} {73}} & 0 & 0 & 0 \\ 0 & 0 & {\ frac {12} {13}} & {\ frac {1} {13}} & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \ \ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 \ end {bmatrix}}$

Ved at udføre de samme beregninger som i de foregående spørgsmål opnår vi i den sidste linje i løsningsvektoren procentdelen af linjer, der har afsluttet mindst et mandat eller antallet (hvis vi ganger med det samlede antal af befolkningen). Med andre ord, at modellere problemet igen gør det muligt at besvare spørgsmålet, der syntes så kompliceret ved en simpel beregning af kræfterne i en matrix.

Ansøgninger

En Bernoulli-proces er et simpelt eksempel på en Markov-kæde.
Markoviske systemer er meget til stede i fysik, især i statistisk fysik . Mere generelt påberåbes den markoviske hypotese ofte, når sandsynligheder bruges til at modellere et systems tilstand, forudsat dog at systemets fremtidige tilstand kan udledes fra fortiden med en forholdsvis lav historie.
Den berømte artikel fra 1948 af Claude Shannon , A Mathematical Theory of Communication , som baserer informationsteorien , begynder med at introducere begrebet entropi fra en Markov-modellering af det engelske sprog . Det viser således graden af forudsigelighed af det engelske sprog forsynet med en simpel rækkefølge 1. Selvom sådanne modeller er enkle, gør det det muligt at repræsentere systemernes statistiske egenskaber godt og give effektive forudsigelser uden at beskrive den komplette struktur.
I kompression tillader Markovian-modellering realisering af meget effektive entropikodningsteknikker , såsom aritmetisk kodning . Mange algoritmer i mønstergenkendelse eller i kunstig intelligens såsom Viterbi-algoritmen , der anvendes i langt de fleste mobiltelefonsystemer til fejlkorrektion, antager en underliggende Markovian-proces.
Popularitetsindekset for en webside ( PageRank ) som brugt af Google defineres af en Markov-kæde. Det er defineret af sandsynligheden for at være på denne side fra enhver tilstand i Markov-kæden, der repræsenterer Internettet. Hvis antallet af kendte websider er, og en side har links, så er sandsynligheden for at overgå til en linket side (som den peger på) og for alle andre (ikke-relaterede sider). Bemærk, at vi har . Parameteren er cirka 0,15. $IKKE$ $jeg$ $k_ {i}$ $p_ {i} ^ {l} = {\ tfrac {1-q} {k_ {i}}} + {\ tfrac qN}$ $p_ {i} ^ {{nl}} = {\ tfrac qN}$ $k_ {i} p_ {i} ^ {l} + (N-k_ {i}) p_ {i} ^ {{nl}} = 1$ $q$
Markov-kæder er et grundlæggende værktøj til modellering af processer i køteori og statistik .
Markov-kæder bruges almindeligvis til pålidelighed til beregning af pålidelighed og tilgængelighed af tekniske systemer , især til modellering af fejltype af hændelsessekvenser, reparation, konfigurationsændringer.
Markov-kæderne er grundlaget for Bonus / Malus-systemer udviklet af aktuarer fra bilforsikringsselskaber (sandsynligheden for at have n ulykker i år t er betinget af antallet af ulykker i t-1)
Markov-kæder bruges også i bioinformatik til at modellere forholdet mellem successive symboler i den samme sekvens (f.eks. Af nukleotider ), der går ud over den polynomiske model. Skjulte Markov-modeller har også forskellige anvendelser, såsom segmentering (definerer regionale grænser inden for sekvenser af gener eller proteiner med forskellige kemiske egenskaber), multipel justering , forudsigelse af funktion eller genopdagelse. (De skjulte Markovian-modeller er mere "fleksible" end de strenge definitioner af type startkodon + multiple kodoner + stopkodoner, og de er derfor mere egnede til eukaryoter (på grund af tilstedeværelsen af introner i genomet til disse) eller til opdagelsen af pseudo-gener).

Noter og referencer

Se også

Relaterede artikler

Bibliografi

Bruno Sericola: Markov-kæder - Teori, algoritmer og applikationer . Hermes / Lavoisier, 2013.
Sylvie Méléard: Tilfældige modeller inden for økologi og evolution . Springer, 2016.
Paolo Baldi, Laurent Mazliak, Pierre Priouret, Martingales og Markov kæder. Elementær teori og korrigerede øvelser , ( ISBN 2-7056-6425-4 ) , Hermann (udgaver) , 2001

eksterne links

Philippe Gay, " Markov og sovende skønhed " , på Images des Maths ,5. september 2014
(en) [PDF] Charles M. Grinstead og J. Laurie Snell, kap. “ Markov Chains ”, i Introduktion til sandsynlighed , AMS
(da) Markov Chain Marvelous
Korrigerede øvelser ( wims fra University of Nice Sophia Antipolis )

Markov kæde

Svag Markov-ejendom

Definitioner

Kriterium

Overgangssandsynligheder

Definition

Ejendomme

Overgangsmatrixens beføjelser

Klassificering af stater

Stationær lov

Definition

Eksistens og unikhed

Stærk lov af stort antal og ergodicitet

Konvergens mod den stationære lov

Endelig tilstand plads Markov kæder

Kvasistationelle fordelinger af en absorberet Markov-kæde

Bedømmelse

Eksempel: Hamster Doudou

Diagrammer

Overgangsmatrix

Prognoser

Illustration af virkningen af ​​modellen

Ansøgninger

Noter og referencer

Se også

Relaterede artikler

Bibliografi

eksterne links

Illustration af virkningen af modellen