[PDF] [PDF] Introduction aux chaines de Markov - CERMICS

[PDF] CHAÎNES DE MARKOV - Institut de Mathématiques de Bordeaux

Soit Xn est une chaîne de Markov de matrice de transition P, et soit ν0 la loi de X0 Alors la tout ce chapitre peuvent être résumés dans le théorème suivant :

[PDF] Chaînes de Markov une introduction - De lanalyse de texte à la

De l'analyse de texte `a la physique des particules Jean-Marc est une chaˆıne de Markov de loi initiale π(0) ssi est une chaıne de Markov homog`ene ssi

[PDF] Chaînes de Markov (et applications)

22 fév 2021 · Soit Q la matrice de transition d'une chaîne de Markov homogène Markov lui- même a analysé la succession de voyelles et de consonnes 

[PDF] Introduction aux chaines de Markov - CERMICS

Une chaıne de Markov est une suite de variables aléatoires (Xn,n ∈ N) qui permet de modéliser `a valeurs dans E est appelée chaıne de Markov de matrice de transition P si pour tous n Probabilités, Statistique et Analyse des Données

[PDF] Quelques révisions Définition des chaînes de Markov, usage en

Donner une expression similaire pour la variance de S Définition des chaînes de Markov, usage en modélisation Exercice 4 – Lancers de dés On considère les 

[PDF] Chaînes de Markov et Processus markoviens de sauts Applications

La probabilité µ est appelé loi initiale de la chaîne et la matrice P matrice de transition Proposition 1 (Xn)n≥0 est une chaîne de Markov si et seulement si ∀ n 

[PDF] Chaînes de Markov - DI ENS

fait, les chaınes de Markov sont des processus stochastiques dont l'évolution est régie par une Au lieu de calculer seulement u(a), l'analyse `a un pas calcule

[PDF] Chaînes de Markov - Institut Camille Jordan

1 7 2 Chaîne de Markov en temps continu et espace discret 27 résumer ainsi : lorsque la chaîne est dans l'état x, au cours d'un intervalle de temps

[PDF] Fiche résumée du cours de Processus de Markov, par IKourkova 1

Fiche résumée du cours de Processus de Markov, par I Kourkova 1 Chaînes de Markov à temps continu sur un espace dénombrable 1 1 loi exponentielle

[PDF] chaine de markov matrice de transition

[PDF] exercice corrigé chaine de markov a etat absorbante

[PDF] chaine d'acquisition de données

[PDF] chaine de mesure audioprothèse

[PDF] acquisition de données du capteur ? l ordinateur

[PDF] chaine de mesure pdf

[PDF] chaine d'acquisition capteur

[PDF] les capteurs exercices corrigés

[PDF] chaine de markov apériodique

[PDF] chaine de markov apériodique exemple

[PDF] chaine de markov reversible

[PDF] chaine de markov récurrente

[PDF] chaine de markov exemple

[PDF] chaine de markov irreductible exemple

[PDF] chaine de markov exercice corrigé

Chapitre IIntroduction aux chaines de MarkovI.1 Chaˆınes de Markov

Une chaˆıne de Markov est une suite de variables al´eatoires(Xn,n?N) qui permet de mod´eliser

l"´evolution dynamique d"un syst`eme al´eatoire :Xnrepr´esente l"´etat du syst`eme `a l"instantn. La

propri´et´e fondamentale des chaˆınes de Markov, dite propri´et´e de Markov, est que son ´evolution fu-

ture ne d´epend du pass´e qu"au travers de sa valeur actuelle. Autrement dit, conditionnellement `a

X

n, (X0,...,Xn) et (Xn+k,k?N) sont ind´ependants. Les applications des chaˆınes de Markov sont

tr`es nombreuses (r´eseaux, g´en´etique des populations,math´ematiques financi`eres, gestion de stock,

algorithmes stochastiques d"optimisation, simulation, ...).

nous donnons au paragraphe I.1.1 la d´efinition et des propri´et´es ´elementaires des chaˆınes de Mar-

kov. Nous consid´erons les r´egimes stationnaires ou probabilit´e invariante des chaˆınes de Markov au

paragraphe I.1.2. Nous caract´erisons les propri´et´es des ´etats d"une chaˆıne de Markov, et introduisons

la notion de chaˆıne irr´eductible au paragraphe I.1.3. Intuitivement une chaˆıne de Markov irr´eductible

partant d"un ´etat donn´e peut visiter un autre ´etat au boutd"un certain temps avec probabilit´e stricte-

ment positive. Nous pr´esentons les th´eor`emes asymptotiques fondamentaux pour les chaˆınes de Markov

irr´eductible dans le paragraphe I.1.4. Leur d´emonstration est report´ee au paragraphe I.1.5. Le r´esultat

principal est que pour les chaˆınes de Markov, par exemple `avaleurs dans un espace fini, irr´eductible, la

moyenne en temps 1 nn k=1f(Xk) converge p.s. vers la moyenne defpar rapport `a l"unique probabilit´e

invarianteπ: (π,f). Ce r´esultat est l"analogue de la loi forte des grands nombres. Nous donnons des

exemples importants d"utilisation des chaˆınes de Markov au paragraphe I.1.6.

I.1.1 D´efinition et propri´et´es

SoitEun espace discret, i.e.Eest un espace au plus d´enombrable muni de la topologie discr`ete, o`u tous les points deEsont isol´es, et donc de la tribuE=P(E). D´efinition I.1.1.Une matriceP= (P(x,y),x,y?E)est dite matrice stochastique si ses coefficients sont positifs et la somme sur une ligne des coefficients est ´egale `a 1 :

P(x,y)≥0et?

z?EP(x,z) = 1,pour tousx,y?E.(I.1) 1

2CHAPITRE I. INTRODUCTION AUX CHAINES DE MARKOV

On rappelle la notation (??). On donne une d´efinition des chaˆınes de Markov apparementplus

faible que celle donn´ee en introduction, voir le th´eor`eme I.1.9 pour la propri´et´e de Markov.

D´efinition I.1.2.SoitPune matrice stochastique surE. Une suite de variables al´eatoires(Xn,n?N)

`a valeurs dansEest appel´ee chaˆıne de Markov de matrice de transitionPsi pour tousn?N,x?E,

on a

P(Xn+1=x|Xn,...,X0) =P(Xn+1=x|Xn) =P(Xn,x).(I.2)

On dit que la chaˆıne de Markov est issue deμ0si la loi deX0estμ0.

Comme l"espace d"´etat est discret l"´equation (I.2) est ´equivalente `a : pour tousx0,...,xn?E, tels

queP(Xn=xn,...,X0=x0)>0, P(Xn+1=x|Xn=xn,...,X0=x0) =P(Xn+1=x|Xn=xn) =P(xn,x). SiP(X0=x) = 1, autrement ditμ0est la masse de Dirac enx, on dira plus simplement que la chaˆıne de Markov est issue dex.

La proposition suivante assure que la matrice de transitionet la loi initiale caract´erisent la loi de

la chaˆıne de Markov.

Proposition I.1.3.La loi d"une chaˆıne de Markov(Xn,n?N)est enti`erement caract´eris´ee par sa

matrice de transition,P, et la loi deX0,μ0. De plus, on a, pour tousn?N?,x0,...,xn?E,

P(X0=x0,...,Xn=xn) =μ0(x0)n?

k=1P(xk-1,xk).(I.3) D´emonstration.Soitn?N?,x0,...,xn?E. SiP(X0=x0,...,Xn-1=xn-1)>0, une utilisation successive de la formule des probabilit´es conditionnelles donne

P(X0=x0,...,Xn=xn)

=μ0(x0)n? k=1P(xk-1,xk). SiP(X0=x0,...,Xn-1=xn-1) = 0, soitP(X0=x0) = 0 i.e.μ0(x0) = 0 et donc (I.3) reste vrai; soit il existem? {1,...,n-1}tel queP(X0=x0,...,Xm-1=xm-1)>0 etP(X0=x0,...,Xm= x m) = 0. Dans ce dernier cas, on peut utiliser (I.3) avecn=met obtenir que

0 =P(X0=x0,...,Xm=xm) =μ0(x0)m?

k=1P(xk-1,xk).

On en d´eduit que (I.3) reste vrai avec les deux membres nuls.En conclusion (I.3) est toujours v´erifi´e.

L"espace produitENest l"espace d"´etat de la chaˆıne de Markov. Il est muni de latribu produit.

En particulier comme la tribu surEest engendr´ee par les singletons, la tribu produit surENest, grˆace `a la d´efinition??, engendr´ee par la collectionC={(x0,...,xn);n?N,x0,...,xn?E}. Le

th´eor`eme de classe monotone et plus particuli`erement lecorollaire??assure que deux probabilit´es qui

co¨ıncident surCsont ´egales. On d´eduit donc de (I.3) que la loi de la chaˆınede Markov (Xn,n?N)

est caract´eris´ee parPetμ0. Donnons quelques exemples de chaˆınes de Markov.

I.1. CHAˆINES DE MARKOV3

ExempleI.1.4.La marche al´eatoire sym´etrique simple surZ,S= (Sn,n≥0), est d´efinie parSn=

S

0+?nk=1Zk, o`uZ= (Zn,n≥1) est une suite de variables al´eatoires ind´ependantes etde mˆeme loi,

P(Zn= 1) =P(Zn=-1) = 1/2, etS0est une variable al´eatoire `a valeurs dansZind´ependante de

Z. On v´erifie facilement que la marche al´eatoire simple est une chaˆıne de Markov `a valeurs dansZde

matrice de transition :P(x,y) = 0 si|x-y| ?= 1 etP(x,y) = 1/2 si|x-y|= 1 pourx,y?Z.♦

ExempleI.1.5.On noteXnl"´etat d"un stock de pi`eces d´etach´ees `a l"instantn,Dn+1la demande

(al´eatoire) formul´ee par des clients, etq?N?la quantit´e (d´eterministe) de pi`eces d´etach´ees fabriqu´ees

entre les instantsnetn+ 1. Alors `a l"instantn+ 1, l"´etat du stock estXn+1= (Xn+q-Dn+1)+, o`ux+d´esigne la partie positive dex?R. Si la demandeD= (Dn,n?N?) est constitu´ee de

variables al´eatoires `a valeurs dansNind´ependantes et de mˆeme loi, et siX0est une variable al´eatoire

ind´ependante deD`a valeurs dansN, alorsX= (Xn,n?N) est une chaˆıne de Markov `a valeurs dans

Nde matrice de transition :P(x,y) =P(D=k) siy=x+q-k >0, etP(x,0) =P(D≥x+q). On

donne quelques simulations de la chaˆıne de MarkovXpour diff´erentes loi deD1dans le graphique

I.1.♦

02505007501000

0 2 4 6 8 10

02505007501000

0 4 8 12 16 20

Fig.I.1 - Plusieurs r´ealisations de l"´evolutaion al´eatoired"un stock de dynamiqueXn+1= (Xn+q-

D n+1)+, avecX0= 0,q= 3 et o`u les variables al´eatoires (Dn,n?N?) sont ind´ependantes de loi de Poisson de param`etreθ(θ= 4 `a gauche etθ= 3 `a droite).

Les deux exemples pr´ec´edents sont des cas particuliers dulemme suivant. Sa d´emonstration est

imm´ediate.

Lemme I.1.6.SoitU= (Un,n?N?)une suite de variables al´eatoires ind´ependantes et de mˆeme loi `a

valeurs dans un espace mesurableF. SoitX0une variable al´eatoire `a valeurs dansEind´ependante de

Uet de loiμ0. Soitfune fonction mesurable d´efinie surE×F`a valeurs dansE. La suite(Xn,n?N) d´efinie parXn+1=f(Xn,,Un+1)pourn?Nest une chaˆıne de Markov issue deμ0et de matrice de transitionPd´efinie parP(x,y) =P? f(x,U1) =y? pour tousx,y?E.

Pour un choix judicieux de suiteUet de fonctionfdans le lemme pr´ec´edent, il est ais´e de v´erifier

que pour toute matrice stochastiquePsurEet toute probabilit´eμ0surE, on peut construire une chaˆıne de Markov issue deμ0et de matrice de transitionP.

Il est facile de calculer des esp´erances ou des lois conditionnelles pour une chaˆıne de Markov `a

l"aide des puissances de sa matrice de transition. Nous introduisons d"abord quelques notations. SoitPetQdeux matrices d´efinies surE. On notePQla matrice d´efinie surEparPQ(x,y) =? z?EP(x,z)Q(z,y). On poseP0la matrice identit´e et pourk≥1,Pk=Pk-1P(on a aussiP= PP k-1). Il est imm´ediat de v´erifier que siPetQsont des matrices stochastiques alorsPQest une matrice stochastique.

4CHAPITRE I. INTRODUCTION AUX CHAINES DE MARKOV

On identifie une probabilit´eμsurEau vecteur (μ(x) =μ({x}),x?E) deRE, et une fonction fd´efinie surE`a valeurs dansRau vecteur (f(x),x?E). Pour une probabilit´eμet une matrice stochastiqueP, on d´efinit le vecteurμPparμP(y) =? x?Eμ(x)P(x,y) pour touty?E. Il est ´evident

de v´erifier, en utilisant (I.1), queμPest ´egalement une probabilit´e. Pour une fonctionfpositive o`u

born´ee et une matrice stochastiqueP, on d´efinit la fonctionPfparPf(x) =? y?EP(x,y)f(y). La proposition suivante permet d"exprimer des esp´eranceset des lois conditionnelles pour une chaˆıne de Markov en fonction de sa matrice de transition. Proposition I.1.7.Soit(Xn,n?N)une chaˆıne de Markov de matrice de transitionP. On noteμn la loi deXn. Soitfune fonction born´ee. On a pourn?N?

1.μn=μ0Pn,

2.E[f(Xn)|X0] =Pnf(X0),

3.E[f(Xn)|X0,...Xn-1] =Pf(Xn-1),

4.E[f(Xn)] = (μn,f) = (μ0Pn,f) = (μ0,Pnf).

On utilise les notationsPxetExquandX0est p.s. ´egal `ax(i.e. la loi deX0est la masse de Dirac enx). Ainsi on aPx(A) =P(A|X0=x) etEx[Z] =E[Z|X0=x]. Avec ces notations, on peut r´e´ecrire la propri´et´e 2 de la proposition :Ex[f(Xn)] =Pnf(x) pour toutx?E. D´emonstration.Le point 1 d´ecoule de (I.3) en sommant surx0,...,xn-1?E. En sommant (I.3) sur x

1,...,xn-1?E, on obtientP(X0=x0,Xn=xn) =μ0(x0)Pn(x0,xn). En mutlipliant parf(xn) et

en sommant surxn?E, on obtientE[f(Xn)1{X0=x0}] =μ0(x0)Pnf(x0). Le point 2 d´ecoule alors de

la d´efinition de l"esp´erance conditionnelle, voir le corollaire??. En multipliant (I.3) parf(xn) et en

sommant surxn?E, on obtient E[f(Xn)1{X0=x0,...,Xn-1=xn-1}] =Pf(xn-1)P(X0=x0,...,Xn-1=xn-1).

Le point 3 d´ecoule alors de la d´efinition de l"esp´erance conditionnelle, voir le corollaire??. Le point 4

d´ecoule du point 1 pour la deuxi`eme ´egalit´e et du point 2 pour la derni`ere.

ExempleI.1.8.Soit (Un,n?N?) une suite de variables al´eatoires ind´ependantes de loi de Bernoulli

de param`etrep?]0,1[. On d´esire calculer la probabilit´ep?,nd"observer une s´equence de 1 cons´ecutifs

de longueur au moins?dans la suite (U1,...,Un). Pour cela, on indroduit la chaˆıne de Markov d´efinie

parX0= 0 etXn+1= (Xn+ 1)1{Un+1=1,Xnl"on observe une s´equence de 1 cons´ecutif de longueur?la chaˆıneXdevient constante ´egale `a?. En

particulier, on ap?,n=P(Xn=?) =Pn(0,?), o`uPest la matrice de transition de la chaˆıne de Markov

(Xn,n?N). On aP(x,0) = 1-petP(x,x+ 1) =ppourx? {0,...,?-1},P(?,?) = 1 et tous les autres termes de la matrice sont nuls. On repr´esente lesvaleurs dep?,npourn= 100 etp= 1/2

dans le graphique I.2. On observe qu"avec une probabilit´e sup´erieure `a 1/2 on a une s´equence de 1

cons´ecutifs de longueur au moins 6 (p6,100?0.55).♦

Le th´eor`eme suivante assure que l"´evolution future d"une chaˆıne de Markov ne d´epend du pass´e

qu"au travers de sa valeur pr´esente. Cette propri´et´e estappel´ee propri´et´e de Markov.

Th´eor`eme I.1.9(Propri´et´e de Markov des chaˆınes de Markov).Soit(Xn,n?N)une chaˆıne de

Markov de matrice de transitionPissue deμ0. Soitn0?N. La loi de(Xn+n0,n?N)sachant (X0,...,Xn0)est une chaˆıne de Markov de matrice de transitionPissue deX0. D´emonstration.On d´eduit de (I.3) que pour tousn≥1,x0,...,xn0+n?E

P(Xn0=xn0,...,Xn0+n=xn0+n|X0=x0,...,Xn0=xn0) =n

0+n? k=n0+1P(xk-1,xk).

I.1. CHAˆINES DE MARKOV5

123456789101112131415

0.00 0.25 0.50 0.75 1.00

Fig.I.2 - Graphe de la fonctionx?→P(Ln≥ ?x?), o`uLnest la longueur maximale des s´equences de

1 cons´ecutifs dans une suite den= 100 variables al´eatoires de Bernoulli ind´ependantes deparam`etre

p= 1/2. Autrement dit, on aP(Xn0=xn0,...,Xn0+n=xn0+n|X0,...,Xn0) =F(Xn0) o`uF(x) =P(X0= x n0,...,Xn=xn0+n|X0=x). On d´eduit donc de la proposition I.1.3 que conditionnellement `a

(X0,...,Xn0), (Xn0,...,Xn0+n) a mˆeme loi que (X0,...,Xn) issu deXn0. Ceci ´etant vrai pour tout

n≥1, on en d´eduit le r´esultat en utilisant la caract´eristation de la loi d"une chaˆıne de Markov par sa

matrice de transition et sa loi initiale. I.1.2 Probabilit´es invariantes, r´eversibilit´equotesdbs_dbs2.pdfusesText_3