[PDF] Chapitre I - Introduction aux chaines de Markov

View - Download Chapitre I - Introduction aux chaines de Markov

Previous PDF

Next PDF

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´e

Les probabilit´es invariantes jouent un rˆole important dans l"´etude des comportements asympto-

tiques des chaˆınes de Markov.

D´efinition I.1.10.Une probabilit´eπsurEest appel´ee probabilit´e invariante, ou probabilit´e station-

naire, d"une chaˆıne de Markov de matrice de transitionPsiπ=πP.

ExerciceI.1.

SoitX= (Xn,n?N) une chaˆıne de Markov de matrice de transitionP.

1. Montrer queZ= (Zn=X2n,n?N) est une chaˆıne de Markov. Pr´eciser sa matrice de transition.

2. V´erifier que toute probabilit´e invariante pourXest une probabilit´e invariante pourZ. En

consid´erant un espace d"´etat `a deux ´el´ements, donner un contre-exemple pour la r´eciproque.

On consid`ere (Xn,n?N) une chaˆıne de Markov de matrice de transtionPissue d"une probabilit´e

invarianteπ. On noteμnla loi deXn. On aμ1=πP=πet, en it´erant, on obtient queμn=π. Pour

toutn?N?,Xna mˆeme loi queX0: la loi deXnest donc constante ou stationnaire au cours du temps. Supposons de plus queπ(x)>0 pour toutx?E. Pourx,y?E, on pose

Q(x,y) =π(y)P(y,x)

π(x)·(I.4)

6CHAPITRE I. INTRODUCTION AUX CHAINES DE MARKOV

Commeπest une probabilit´e invariante, on a? y?Eπ(y)P(y,x) =π(x) pour toutx?E. En parti- culier la matriceQest une matrice stochastique. Pour tousx,y?E,n≥0, on a

P(Xn=y|Xn+1=x) =P(Xn=y,Xn+1=x)

P(Xn+1=x)=Q(x,y).

Autrement ditP(Xn=y|Xn+1) =Q(Xn+1,y) pour touty?E. Plus g´en´eralement, il est facile de v´erifier que pour tousk?N?,y?E, on aP(Xn=y|Xn+1,...,Xn+k) =Q(Xn+1,y). La matriceQ

s"interpr`ete comme la matrice de transition de la chaˆıne de MarkovXapr`es retournement du temps.

D´efinition I.1.11.On dit qu"une chaˆıne de Markov de matrice de transitionP, ou plus simplement

la matriceP, est r´eversible par rapport `a la probabilit´eπsi on a pour tousx,y?E,

π(x)P(x,y) =π(y)P(y,x).(I.5)

En sommant (I.5) surx, on en d´eduit le lemme suivant.

Lemme I.1.12.Si une chaˆıne de Markov est r´eversible par rapport `a la probabilit´eπ, alorsπest une

probabilit´e invariante.

Les exemples I.1.38 et I.1.34 permettent d"illustrer le concept de chaˆınes de Markov r´eversibles.

SiPest r´eversible par rapport `aπ, alorsQd´efinie par (I.4) est ´egal `aP. Donc si une chaˆıne de

Markov est r´eversible par rapport `a une probabilit´e invariante, alors si elle est issue de cette probabilit´e

invariante la chaˆıne et la chaˆıne apr`es retournement du temps ont mˆeme loi. Plus pr´ecis´ement, si

(Xn,n?N) est une chaˆıne de Markov r´eversible par rapport `aπet si la loi deX0estπ, alors les

vecteurs (X0,...,Xn-1,Xn) et (Xn,Xn-1,...,X0) ont mˆeme loi pour toutn?N?. I.1.3 Irreductibilit´e, r´ecurrence, transience, p´eriodicit´e D´efinition I.1.13.SoitX= (Xn,n?N)une chaˆıne de Markov de matrice de transitionP. On dit quexest un ´etat absorbant de la chaˆıneXsiP(x,x) = 1.

En particulier si la chaˆıne de Markov atteint un de ses points absorbants, elle ne peut plus s"en

´echapper. Dans L"exemple I.1.35 sur le mod`ele de Wright-Fisher, on s"int´eresse au temps d"atteinte

des points absorbants.

ExerciceI.2.

SoitX= (Xn,n?N) une chaˆıne de Markov de matrice de transitionP. On utilise la convention inf∅= +∞. On pose

1= inf{k≥1;Xk?=X0}.

1. Soitx?E. Calculer la loi deτ1conditionnellement `aX0=x. V´erifier que, conditionnellement

`aX0=x,τ1= +∞p.s. sixest un point absorbant et sinon p.s.τ1est fini.

2. Conditionnellement `aX0=x, sixn"est pas un point absorbant, calculer la loi deXτ1.

On poseS0= 0,Y0=X0et on d´efinit par r´ecurrence surn≥1 :Sn=Sn-1+τn, et siSn<∞: Y n=XSnet n+1= inf{k≥1;Xk+Sn?=XSn}.

SoitR= inf{n;τn= +∞}= inf{n;Sn= +∞}.

3. Montrer que siXne poss`ede pas de points absorbants, alors p.s.R= +∞.

I.1. CHAˆINES DE MARKOV7

On suppose queXne poss`ede pas de points absorbants.

4. Montrer queY= (Yn,n?N) est une chaˆıne de Markov. Elle est appel´ee la chaˆıne trace associ´ee

`aX. Montrer que sa matrice de transitionQest d´efinie par :

Q(x,y) =P(x,y)

1-P(x,x)1{x?=y}pourx,y?E.

5. Soitπune probabilit´e invariante pourX. On d´efinit une mesureνsurEpar

ν(x) =π(x)(1-P(x,x))

y?Eπ(y)(1-P(y,y)), x?E. V´erifier queνest une probabilit´e invariante pourY.

D´efinition I.1.14.On dit qu"une chaˆıne de Markov, ou sa matrice de transition,est irr´eductible si

pour tousx,y?E, la probabilit´e partant dexd"atteindreyest strictement positive, autrement dit : si pour tousx,y?E, il existen=nx,y≥1(d´ependant a priori dexety) tel quePn(x,y)>0. La conditionPn(x,y)>0 est ´equivalente `a l"existence den≥1,x0=x,x1, ...,xn=ytels que

P(X1=x1,...,Xn=xn|X0=x0) =?nk=1P(xk-1,xk)>0.

Par exemple, la marche al´eatoire sym´etrique simple surZde l"exemple I.1.4 et la chaˆıne de Markov

de l"urne d"Ehrenfest de l"exemple I.1.38 sont irr´eductibles. Une chaˆıne poss´edant des ´etats absorbants

n"est pas irr´eductible (sauf si l"espace d"´etat est r´eduit `a un point). Ainsi la chaˆıne de Markov du mod`ele

de Wright-Fisher, voir l"exemple I.1.35 n"est pas irr´eductible.

ExerciceI.3.

SoitX= (Xn,n?N) une chaˆıne de Markov de matrice de transitionP`a valeurs dansE. On pose Y n= (Xn-1,Xn) pourn?N?.

1. Montrer queY= (Yn,n?N?) est une chaˆıne de Markov `a valeurs dansE2. Donner sa matrice

de transition,Q.

2. Donner un exemple o`uQn"est pas irr´eductible alors quePest irr´eductible. Changer l"espace

d"´etat deYpour queYsoit irr´eductible siXest irr´eductible.

3. On suppose queXposs`ede une probabilit´e invariante,π. En d´eduire une probabilit´e invariante

pourY. On utilise la convention inf∅= +∞. On d´efinit le temps d"atteinte dexpar T x= inf{n≥1;Xn=x}. D´efinition I.1.15.SoitX= (Xn,n?N)une chaˆıne de Markov. On dit qu"un ´etatx?Eest : - transient siPx(Tx= +∞)>0, - r´ecurrent siPx(Tx= +∞) = 0.

Une chaˆıne de Markov est dite transiente (resp. r´ecurrente) si tous les ´etats sont transients (resp.

r´ecurrents).

On poseNx=?

n?N1{Xn=x}le nombre de visites du pointx. La proposition suivante permet de caract´eriser les points r´ecurrents et transients.

Proposition I.1.16.SoitXune chaˆıne de Markov de matrice de transitionP. On a les propri´et´es

suivantes.

8CHAPITRE I. INTRODUCTION AUX CHAINES DE MARKOV

1. Sixest transient alors on aPx(Nx<+∞) = 1,?

n?NPn(x,x)<∞et conditionnellement `a {X0=x},Nxest de loi g´eom´etrique de param`etrePx(Tx=∞).

2. Sixest r´ecurrent alors on aPx(Nx= +∞) = 1et?

n?NPn(x,x) =∞.

3. SiXest irr´eductible alorsXest soit transiente soit r´ecurrente. Dans le premier cas ona

P(Nx<+∞) = 1pour toutx?Eet dans le secondP(Nx= +∞) = 1pour toutx?E.quotesdbs_dbs28.pdfusesText_34

[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é

[PDF] chaine énergétique barrage hydraulique

[PDF] chaine énergétique d'une éolienne