[PDF] Introduction aux chaines de Markov - CERMICS PDF mod-stoch.pdf

invariante π : (π, f) Ce résultat est l'analogue de la loi forte des grands nombres Nous donnons des exemples importants d'utilisation des chaınes de Markov au

22 fév 2021 · Exercice 2 Soit k ∈ N∗ Soit X = (Xn) une chaîne de Markov (homogène) de loi initiale µ0 et de matrice de transition

[PDF] Chaines de Markov : compléments

de la leçon précédente est une chaıne de Markov irréductible de même que celui des souris dans le labyrinthe {1,2,3,4,5} Mais, si l'on modifie cet exemple en

[PDF] Chaînes de Markov

Exemple On représente usuellement une chaîne de Markov d'espace d'états X par un graphe orienté étiqueté G = (V,E) dont les sommets sont les éléments de

[PDF] Introduction aux chaines de Markov - CERMICS

invariante π : (π, f) Ce résultat est l'analogue de la loi forte des grands nombres Nous donnons des exemples importants d'utilisation des chaınes de Markov au

[PDF] Un exemple de chaîne de Markov dans lindustrie textile - Numdam

modèle en chaîne de Markov, ce qui lui a permis d'obtenir une première série de résultats importants concernant le fonctionnement de la carde (réf 1) Dans un

[PDF] fichier pdf - Loria

valuation de l'arête i → j : pi,j Une chaıne de Markov peut être vue comme une marche aleatoire sur G, connaissant π0 Exemple : 2 0,5 0,25 yyss

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

De plus, si les variables Xn sont de même loi µ, alors (Sn) est une chaîne de Markov homogène de matrice de transition Pij = µ(j − i) Exemple 2 (Modèle de

[PDF] Chaînes de Markov - Université de Lorraine

Exercice 2 8 Soit (Xn,n ≥ 0) une chaine de Markov à valeurs dans E, de loi initiale µ et de probabilité de transition π On considère f : E → F 1 Montrer que ((Xn,f(

[PDF] Exercices : des exemples classiques, quelques calculs explicites, et

π(x)=1 − 1 2n−t 2 Exemples classiques de chaˆınes de Markov Exercice 3 1 Soit p ∈ [0,1] fixé

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

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=

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. D´emonstration.On posep=Px(Tx= +∞) =Px(Nx= 1). On noteTxn= inf{k≥0;?kr=01{Xr=x}= n}len-`eme temps de passage enx. (On aTx2=TxquandX0=x). Remarquons que{Txn<+∞}= {Nx≥n}. En d´ecomposant suivant les valeurs deTxn, il vient pourn?N?: P x(Nx> n) =? r≥nP(Nx> n,Txn=r) r≥nP? r? i=11 {Xi=x}=n,Xr=x,? ??N1 {Xr+?=x}>1? r≥nP? r? i=11 {Xi=x}=n,Xr=x? P x? ??N1 {X?=x}>1? =Px(Nx≥n)Px(Nx>1)(I.6) =Px(Nx> n-1)(1-p).

o`u l"on a utilis´e la propri´et´e de Markov `a l"instantrpour la troisi`eme ´egalit´e. En it´erant et en utilisant

quePx(Nx>0) = 1, on obtientPx(Nx> n) = (1-p)npourn?N, puisPx(Nx=n) =Px(Nx> n-1)-Px(Nx> n) =p(1-p)n-1pourn?N?. Remarquons enfin queEx[Nx] =? n?NPx(Xn= x) =? n?NPn(x,x). Sixest transient, on ap >0 et, conditionnellement `a{X0=x},Nxest de loi g´eom´etrique de param`etrep >0. En particulier son esp´erance est finie. Sixest r´ecurrent, on ap= 0 et doncP(Nx?N) = 0. Ceci implique queP(Nx= +∞) = 1 et son esp´erance est infinie.

Il reste le point 3 `a d´emontrer. Soitx,y?E. Comme la chaˆıne est irr´eductible, il existen1etn2

tels quePn1(y,x)>0 etPn2(x,y)>0. En particulier on a pour toutn?N P n+n1+n2(y,y)≥Pn1(y,x)Pn(x,x)Pn2(x,y) etPn+n1+n2(x,x)≥Pn2(x,y)Pn(y,y)Pn1(y,x).(I.7)

Ceci implique que les deux s´eries

n?NPn(x,x) et? n?NPn(y,y) sont de mˆeme nature. Ainsi les

deux ´etatsxetysont soit tous les deux transients soit tous les deux r´ecurrents. On en d´eduit qu"une

chaˆıne irr´eductible est soit r´ecurrente soit transiente.

Si la chaˆıne est transiente, on a en d´ecomposant suivant lavaleur deTxet en utilisant la propri´et´e

de Markov

P(Nx= +∞) =?

n?NP(Tx=n)Px(Nx= +∞) = 0.

Si la chaˆıne est r´ecurrente, on a en d´ecomposant suivant la valeur deTxet en utilisant la propri´et´e

de Markov

P(Nx<+∞) =P(Tx= +∞) +?

n?NP(Tx=n)Px(Nx<+∞) =P(Tx= +∞).(I.8)

I.1. CHAˆINES DE MARKOV9

Soity?Edistinct dexetNyx= Card ({n < Tx;Xn=y}) le nombre de visites deyavant de visiter x. On notep=Py(Tx< Ty) la probabilit´e de visiterxavant de retourner eny. Un calcul similaire `a (I.6) assure que P y(Nyx> n) =Py(Nyx≥n)Py(Nyx>1) =Py(Nyx> n-1)(1-p). En it´erant et en utilisant quePy(Nyx>0) = 1, on obtientPy(Nyx> n) = (1-p)npourn?Net donc P

y(Nyx= +∞) =1{p=0}. La chaˆıne ´etant irr´eductible, il existen >0 tel quePy(Xn=x)>0. Comme

{Xn=x} ? {Tx<+∞}, on en d´eduit quePy(Tx=∞)<1. Comme{Nyx= +∞}={Tx= +∞}, il vientPy(Nyx= +∞)<1. Ceci impliquep >0 puisPy(Nyx= +∞) = 0 etPy(Tx= +∞) = 0. Comme

P(Tx= +∞) =?

y?EP(X0=y)Py(Tx= +∞) = 0, on d´eduit de (I.8) queP(Nx<+∞) = 0. Ceci termine la d´emonstration du point 3.

ExerciceI.4.

On consid`ere la marche al´eatoire sym´etrique simple surZd,d≥1, d´efinie parS0= 0,Sn=?nk=1Zk

pourn?N?, o`u les variables al´eatoires (Zn,n?N?) sont ind´ependantes de loi uniforme sur{z? Z

d;|z|= 1}, et| · |d´esigne la norme euclidienne surRd. (Le casd= 1 correspond `a l"exemple I.1.4.)

1. V´erifier que la chaˆıne (Sn,n?N) est irr´eductible.

2. On supposed= 1. CalculerP0(S2n= 0). En utilisant la formule de Stirling (n!≂⎷

2πnn+1/2e-n

pourngrand), montrer que la marche al´eatoire est r´ecurrente.

3. On supposed= 2. CalculerP0(S2n= 0) et montrer que la marche al´eatoire est r´ecurrente. On

pourra utiliser que (1 +x)n(1 +x)n= (1 +x)2npour calculer?nk=0(n!)2 k!(n-k)!? 2.

4. On supposed= 3. Montrer que la marche al´eatoire est transiente. On pourra utiliser, apr`es

l"avoir v´erifi´e, que pourn≥3 : i+j+k=n? n!

3ni!j!k!?

2 i+j+k=nn!3ni!j!k!)) maxi+j+k=n? n!3ni!j!k!?

5. D´eduire de la question pr´ec´edente que la marche al´eatoire sym´etrique en dimensiond≥3 est

transiente.

Dans l"exemple I.1.4 de la marche al´eatoire sym´etrique, remarquons que, siS0est pair, alorsSn

est pair si et seulement sinest pair. On assiste `a un ph´enom`ene p´eriodique. En particulierPn(0,0)

est nul sinest impair. Ceci motive la d´efinition suivante.

D´efinition I.1.17.SoitXune chaˆıne de Markov de matrice de transitionP. La p´eriode d"un ´etat

x?Eest le PGCD de{n?N?;Pn(x,x)>0}. Un ´etat est dit ap´eriodique si sa p´eriode est 1, sinon

il est dit p´eriodique. Une chaˆıne de Markov est dite ap´eriodique si tous ses ´etats sont ap´eriodiques.

ExerciceI.5.

Montrer que pour la chaˆıne de Markov de l"urne d"Ehrenfest,voir l"exemple I.1.38, les ´etats sont de

p´eriode 2.?

ExerciceI.6.

On noteJ={n?N?;Px(Tx=n)>0}. Montrer queI={n?N?;Pn(x,x)>0}est stable par addition, et que c"est le plus petit sous-ensemble deN?stable par addition contenantJ.?

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

suivantes.

1. Six?Eest ap´eriodique, alors il existen0?Ntel quePn(x,x)>0pour toutn≥n0.

10CHAPITRE I. INTRODUCTION AUX CHAINES DE MARKOV

2. SiXest irr´eductible, alors elle est ap´eriodique si au moins un ´etat est ap´eriodique.

D´emonstration.Soitx?Eap´eriodique. On noteI={n?N?;Pn(x,x)>0}. CommePn+m(x,x)≥ P n(x,x)Pm(x,x), on en d´eduit queIest stable par addition. Par hypoth`ese, il existen1,...,nK?I

premiers entre eux. Le th´eor`eme de B´ezout assure qu"il existea1,...,aK?Ztel que?Kk=1aknk= 1.

On posen+=?Kk=1;ak>0aknketn-=?Kk=1;ak<0|ak|nk, de sorte quen+,n-?Ietn+-n-= 1. Soitn≥n2-. On consid`ere la division euclidienne denparn-: il exister? {0,...,n--1}etq≥n- entier tels que n=qn-+r=qn-+r(n+-n-) = (q-r)n-+rn+. Commeq-r≥0 et queIest stable par addition, on an?I. Ceci d´emontre le point 1.

SiPn(x,x)>0 pour toutn≥n0, alors par d´efinitionxest ap´eriodique. Le point 2 d´ecoule alors

du point 1 et de (I.7).

ExerciceI.7.

SoitX= (Xn,n?N) une chaˆıne de Markov irr´eductible. Montrer que s"il existexde p´erioded >1,

alors on peut d´ecomposer l"espace d"´etatEen une partition `adsous ensemblesC1,...,Cd=C0, tels

que pour toutk? {1,...,d},

P(X1?Ck|X0?Ck-1) = 1.

Le lemme suivant sera utilis´e au paragraphe I.1.5. Lemme I.1.19.SoitX= (Xn,n?N)etY= (Yn,n?N)deux chaˆınes de Markov ind´ependantes

irr´eductibles `a valeurs dansE. AlorsZ= ((Xn,Yn),n?N)est une chaˆıne de Markov `a valeurs dans

2. Siπ(resp.ν) est une probabilit´e invariante pourX(resp.Y), alorsπ?νest une probabilit´e

invariante pourZ. SiXouYest ap´eriodique, alorsZest irr´eductible.

D´emonstration.Il est ´el´ementaire de v´erifier queZest une chaˆıne de Markov de matrice de transition

P(z,z?) =P1(z1,z?1)P2(z2,z?2) o`uP1(resp.P2) est la matrice de transition deX(resp.Y) etz= (z1,z2),z?= (z?1,z?2)?E2. Siπ(resp.ν) est une probabilit´e invariante pourX(resp.Y), alors on a, pourz= (z1,z2)?E2.

π?νP(z?) =?

1,z2?Eπ(z1)ν(z2)P((z1,z2),(z?1,z?2)) =?

1,z2?Eπ(z1)P1(z1,Z?1)ν(z2)P2(z2,z?2) =π?ν(z).

Et doncπ?νest une probabilit´e invariante pourZ. Supposons queXest ap´eriodique et montrons queZest irr´eductible. Soitz= (z1,z2),z?=

(z?1,z?2)?E2. Les chaˆınesXetY´etant irr´eductibles, il existen1,n2,n3?N?tels quePn11(z1,z?1)>0,

P n22(z2,z?2)>0 etPn32(z?2,z?2)>0. La proposition I.1.18 assure quePkn3+n2-n1(z?1,z?1)>0 pour k?N?suffisament grand. Ainsi, on obtient que P kn3+n2(z,z?) =Pkn3+n21(z1,z?1)Pkn3+n22(z2,z?2)

La chaˆıneZest donc irr´eductible.

I.1. CHAˆINES DE MARKOV11

I.1.4 Th´eor`emes asymptotiques

SoitX= (Xn,n?N) une chaˆıne de Markov `a valeurs dansE. On rappelle la d´efinition du temps d"atteinte dex:Tx= inf{n≥1;Xn=x}. Notons que, commeTx≥1, on aEx[Tx]≥1. On pose

π(x) =1

Ex[Tx]?[0,1].(I.9)

Pour une chaˆıne de Markov irr´eductible transiente on a, pour toutx?E,Px(Tx= +∞)>0 et donc

π= 0.

D´efinition I.1.20.Un ´etatxr´ecurrent est dit r´ecurrent positif siπ(x)>0et r´ecurrent nul si

π(x) = 0. Une chaˆıne est dite r´ecurrente positive (resp. nulle) sitous ses ´etats sont r´ecurrents positifs

(resp. nuls).

On dit qu"un ´ev`enementAest presque sˆur (p.s.) pour une chaˆıne de MarkovXde matrice de

transitionPsiPx(A) = 1 pour toutx?Eet donc siP(A) = 1 quelque soit la loi initiale de la chaˆıne

de Markov.

Les deux th´eor`emes fondamentaux suivants sur le comportement asymptotique d"une chaˆıne de

Markov irr´eductible seront d´emontr´es au paragraphe I.1.5. Th´eor`eme I.1.21.SoitX= (Xn,n?N)une chaˆıne de Markov irr´eductible `a valeurs dansE.

1. La chaˆıne de MarkovXest soit transiente soit r´ecurrente nulle soit r´ecurrente positive.

2. Si la chaˆıne de Markov est transiente ou r´ecurrente nulle, elle ne poss`ede pas de probabilit´e

invariante. De plus on aπ= 0.

3. Pour toutx?E, on a

1 nn k=11

Th´eor`eme I.1.22(Th´eor`eme ergodique).SoitX= (Xn,n?N)une chaˆıne de Markov irr´eductible

`a valeurs dansEr´ecurrente positive.quotesdbs_dbs6.pdfusesText_11

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

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

P(x,y)≥0et?

2CHAPITRE I. INTRODUCTION AUX CHAINES DE MARKOV

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

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

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

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

I.1. CHAˆINES DE MARKOV3

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

I.1.♦

02505007501000

02505007501000

4CHAPITRE I. INTRODUCTION AUX CHAINES DE MARKOV

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).

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

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

I.1. CHAˆINES DE MARKOV5

123456789101112131415

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

ExerciceI.1.

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

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

π(x)·(I.4)

6CHAPITRE I. INTRODUCTION AUX CHAINES DE MARKOV

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

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

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

ExerciceI.2.

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

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

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

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

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

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))

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

ExerciceI.3.

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

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

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

On poseNx=?

8CHAPITRE I. INTRODUCTION AUX CHAINES DE MARKOV

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

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

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

Ceci implique que les deux s´eries

P(Nx= +∞) =?

P(Nx<+∞) =P(Tx= +∞) +?

I.1. CHAˆINES DE MARKOV9

P(Tx= +∞) =?

ExerciceI.4.

1. V´erifier que la chaˆıne (Sn,n?N) est irr´eductible.

2. On supposed= 1. CalculerP0(S2n= 0). En utilisant la formule de Stirling (n!≂⎷

2πnn+1/2e-n

3. On supposed= 2. CalculerP0(S2n= 0) et montrer que la marche al´eatoire est r´ecurrente. On

4. On supposed= 3. Montrer que la marche al´eatoire est transiente. On pourra utiliser, apr`es

3ni!j!k!?

5. D´eduire de la question pr´ec´edente que la marche al´eatoire sym´etrique en dimensiond≥3 est

ExerciceI.5.

ExerciceI.6.

1. Six?Eest ap´eriodique, alors il existen0?Ntel quePn(x,x)>0pour toutn≥n0.

10CHAPITRE I. INTRODUCTION AUX CHAINES DE MARKOV

2. SiXest irr´eductible, alors elle est ap´eriodique si au moins un ´etat est ap´eriodique.

ExerciceI.7.

P(X1?Ck|X0?Ck-1) = 1.

2. Siπ(resp.ν) est une probabilit´e invariante pourX(resp.Y), alorsπ?νest une probabilit´e

π?νP(z?) =?

1,z2?Eπ(z1)ν(z2)P((z1,z2),(z?1,z?2)) =?

1,z2?Eπ(z1)P1(z1,Z?1)ν(z2)P2(z2,z?2) =π?ν(z).

La chaˆıneZest donc irr´eductible.

I.1. CHAˆINES DE MARKOV11