[PDF] 3 Mesures invariantes Une chaîne de. Markov

View - Download 3 Mesures invariantes

Previous PDF

Next PDF

Université Paris 13, Institut Galilée Préparation à l"agrégation

Année universitaire 2013-2014

Fin du cours sur les chaînes de Markov3 Mesures invariantes

Dans toute cette partie, on supposera a priori la chaîne de Markov(Xn)n0irréductible. Dans le cas général,

on pourra néanmoins appliquer les théorèmes suivants à la chaîne de Markovrestreinteà une classe fermée et

en déduire alors des résultats sur certaines chaînes de Markov non irréductibles (voir plus loin).

Ayons en tête le cas récurrent : chaque état est visité infiniment souvent. Les définitions suivantes sont surtout

pertinentes dans ce cas-ci.

Tandis que la question de la récurrence ou la transience ont trait au comportement asymptotique de(Xn)nde

façon qualitative (est-ce queXvisite tel état infiniment souvent?), on s"intéresse maintenant à des questions

plus quantitatives, à savoir :

Com biende temps la suite (Xn)npasse-t-elle dans les divers états? (en proportion, pendant un tempsn! 1)

Com biende temps faut-il à la suite (Xn)npour revenir à son point de départ? (en espérance)

La loi de Xnadmet-elle une limite quandnest grand? Peut-on espérer une propriété de " mélange », à savoir

que la loi deXnne dépend presque plus de celle deX0et s"approche d"un équilibre?

Pour toutn, on noten=?(Xn=x)

x2Ela loi deXn(on considérerancomme un vecteur-ligne). On a vu que, pour toutn2?, n+1=nP:

Ainsi, sin!(etPest continue),doit vérifier=P.

DéfinitionUne mesuresurEestinvariante(pourP) si=P, c"est-à-dire : pour touty2E,(y) =X x2E(x)P(x;y): On parle deloi invariantesi de plusest une probabilité ((E) = 1). (On dit aussiloi/probabilité invariante/stationnaire) Vu la relationn+1=nP, on constate de suite que, siest une loi invariante etX0, alorsXnpour toutn.

3.1 Existence et " unicité » des mesures invariantes

On va voir qu"une chaîne de Markovrécurrenteadmet toujours une mesure invariante (non nulle), et celle-ci

sera unique à un facteur près dès lors que la chaîne de Markov est irréductible.

En particulier, une chaîne de Markov finie irréductible admet toujours une mesure invariante, unique à un

facteur près. On donne un argument direct dans le cas fini, et un argument général ensuite. Cas fini.Dans le cas fini, la relation=Psignifie queest un vecteur propreà gauchedePpour la valeur propre 1, ou encore que test un vecteur propre (à droite) detP. Vu que 1 est valeur propre deP(la somme des lignes vaut 1), on sait que 1 est valeur propre de tP, donc il existe6= 0tel queP=. On définit la mesurepar(x) =j(x)j. Alors on constate que, pour touty2E, vu queest invariante, (y) =j(y)j=X x2E(x)P(x;y)X x2Ej(x)jP(x;y) =X x2E(x)P(x;y) = (P)(y);() et par ailleurs la somme des membres de droite de (), lorsqueyparcourtE, vaut X y2E(P)(y) =X y2EX x2E(x)P(x;y) =X x2E(x)X y2EP(x;y) =X x2E(x) 1

donc est égale à la somme des membres de gauche de (). On en déduit que les deux membres sont égaux pour

chaquey2E, ce qui signifie queP=:est une mesure invariante, non nulle.

SupposonsPirréductible et montrons l"unicité à un facteur près, toujours en exploitant le spectre detP. Il suffit

de montrer que 1 est valeur propre simple deP(à droite) vu quePettPsont semblables. Soitf= (f(x))x2E6= 0

vérifiantPf=f. On noteQ=Pnune puissance dePdont tous les coefficients sont strictement positifs (existe

par l"irréductibilité); on a toujoursQf=f. Alors, pour un indicex2Equi rendf(x)maximal, f(x) =X y2EQ(x;y)f(y)X y2EQ(x;y)f(x) =f(x); de sorte que, pour touty2E,f(y) =f(x)vu queQ(x;y)>0. Ceci conclut :f2Vect(1), d"oùdimE1(P) = 1 etdimE1(tP) = 1, ce que l"on voulait. On peut aussi voir ceci comme une conséquence d"un important théorème plus général :

Théorème (de Perron-Frobenius)SoitAune matrice carrée de tailleNà coefficients positifs. On supposeAirréductible : pour tousi;j, il

existen0tel que(An)i;j>0. Alors le rayon spectral deA,= maxfjjj2Sp(A)g, est une valeur propre simple deA, et admet un vecteur propre (non nul) à composantes positives.

Cas général.On peut donner un argument général de nature probabiliste, qui donne même une expression

des mesures invariantes :

PropositionSiXest récurrente irréductible, alors il existe une mesure invariante (non nulle), unique à un facteur près,

et on peut en donner une expression : si on se donnex02E, la mesuremx0définie par m x0(x) =?x0 x01X n=01 fXn=xg où+x

0est le temps de retour enx0, est l"unique mesure invariante telle quem(x0) = 1.

En toutes lettres,mx0(x)est, pour la chaîne de Markov issue dex0, le nombre moyen de visites àxavant de

retourner enx0. m

x0est aussi une mesure invariante si la chaîne n"est pas irréductible; elle donne une masse0hors de la classe

dex0.

La preuve de la proposition consisterait à vérifier que cette mesuremx0est bien invariante (à l"aide de la

propriété de Markov au temps 1, et de la récurrence), et ensuite que c"est bien une mesure (il n"est pas évident

quemx0(x)est fini! Maismx0(x0) = 1évidemment et par l"invariance et l"irréductibilité une valeur infinie en

un état se propagerait à toutEd"où une contradiction en arrivant enx0); l"unicité est plus délicate à expliquer.

PropositionS"il y a un nombre fini d"états transients, alors toute mesure invariante est nulle sur ceux-ci.

Démonstration:En effet, supposons queyest transient et=P. Alors pour toutnon a=Pnet on note que P n(x;y) = 0sixest récurrent, donc (y) =X xtransient(x)Pn(x;y): Et siyest transient alorsPn(x;y)!0(on aPn(x;y) =?x(Xn=y)?x((dernière visite eny)n)&n0car la

dernière visite enyest finie p.s.), donc on peut conclure(y) = 0dès lors que la somme est finie.Attention, il est possible pour une chaîne de Markov transiente d"avoir des mesures invariantes non nulles. Par

exemple, la mesure=1pour la marche aléatoire simple sur?3.

3.2 Mesure réversible

DéfinitionUne mesuresurEestréversible(pourP) si, pour tousx;y2E, (x)P(x;y) =(y)P(y;x): 2 La première remarque est qu"une telle mesure est invariante : pour touty2E, (P)(y) =X x2E(x)P(x;y) =X x2EP(y;x)(x) =(x): Cependant, la plupart des mesures invariantes ne sont pas réversibles.

Un intérêt pour les mesures réversibles vient du fait qu"elles sont plus faciles à trouver (si elles existent) que les

mesures invariantes : le système ci-dessus se résout immédiatement (si on fixe(x), on déduit(y)pour tout

ytel queP(x;y)>0, etc., et il faut juste vérifier que ceci ne mène pas à des incohérences) Il peut donc être

bénéfique de commencer par chercher d"éventuelles mesures réversibles.

L"intérêt principal est cependant théorique : on montre que, siX0suit la loi réversible (donc stationnaire), alors

la suite(X0;X1;:::;Xn)a même loi que la suite(Xn;Xn1;:::;X0), ce qui justifie l"appellation. Une chaîne de

Markov réversible a même loi, sous la probabilité stationnaire, lorsque l"on retourne le temps. Des parallèles

avec l"étude des réseaux électriques existent pour les chaînes de Markov réversibles, et une grande quantité de

résultats, souvent d"inspiration physique, leur sont spécifiques. Exemple : urne d"Ehrenfest.Cherchons les mesures réversibles. Si on fixe(0) = 1, on doit avoir (1) =(0)P(0;1)P(1;0)=N puis (2) =(1)P(1;2)P(2;1)=N(N1)2 et en général (k) =(0)P(0;1)P(1;2)P(k1;k)P(k;k1)P(1;0)=N(N1)(Nk+ 1)k!=N k Les mesures invariantes sont donc les multiples positifs de celle-ci. Exemple : marche aléatoire simple sur un graphe.SoitG= (S;A)un graphe non orienté (Sest

l"ensemble des sommets, etA P2(S)est l"ensemble des arêtes, formées de paires de sommets). Lamarche

aléatoire simplesurGest la chaîne de Markov d"espace d"étatsE=Set de probabilités de transition

P(x;y) =(

1deg(x)sifx;yg 2A

0sinon,

oùdeg(x)est le degré du sommetx, c"est à dire le nombre d"arêtes issues dex:deg(x) = Card(fe2Ajx2eg).

Autrement dit, cette chaîne de Markov choisit à chaque pas une arête de façon uniforme parmi celles issues du

sommet où elle se trouve, et saute vers l"autre sommet de l"arête choisie. On voit immédiatement que(x) = deg(x)est une mesure invariante : sifx;yg 2A, deg(x)P(x;y) = 1 = deg(y)P(y;x):

3.3 Récurrence positive

La formule explicite (}) pour les mesures invariantes a un intérêt fondamental. Pour commencer, on note que

sa masse totale est : (échange espérance/série justifié car v.a. positives) m x0(E) =X x2Em x0(x) =?x0 X n< +x0X x2E1 fXn=xg =?x0 X n< +x01 =?x0[+x 0]: DéfinitionUn étatx2Eestrécurrent positifsi?x0[+x 0]<1. Si un état est récurrent et n"est pas récurrent positif, il est ditrécurrent nul.

Par la remarque précédente, si un étatx0est récurrent positif, la mesure invariantemx0est finie (c"est-à-dire de

masse totale finie), et vice-versa; en particulier, en divisantmx0par cette masse totale?x0[+x

0], on obtient une

loi invariante, unique (tout court) si la mesure invariante est unique à un facteur près. Et(x0) =1?

x0[+x0].

On en déduit la seconde partie de ce qui suit.

3

Proposition

Si xest récurrent positif etx$y, alorsyaussi.

PourPirréductible, on dit quePestrécurrente positivesi un état (ou tous) est récurrent positif.

Si Pest irréductible,Pest récurrente positive si, et seulement s"il existe une loi invariante.

Et, dans ce cas, pour tout étatx,

(x) =1? x[+x]: Dans le cas oùEest fini, la masse totale d"une mesure invariante est toujours finie. Par suite :

CorollaireToute chaîne de Markov irréductible sur un espace d"états fini est récurrente positive.

La proposition s"applique de diverses façons : en supposant la chaîne irréductible,

(le + fréquen t)si on trouv eune loi in variante, alors la chaîne de Markov est récurrente positive, donc

récurrente, et on a x[+x] =1(x):

si les mesures in variantesson tde masse to taleinfinie (ou 0, p ourla mesure n ulle),alors p ourtout x2E

x[+x] =1:

(raremen t)si on sait calc uler?x[+x], et que cette valeur est finie, alors il existe une mesure invariante, donnée

par la formule précédente. Exemple 1 : marche aléatoire simple sur un graphe fini.SiG= (S;A)est un graphe fini (Sest fini)

connexe, alors la marche aléatoire simple surGest une chaîne de Markov irréductible, donc récurrente positive,

et on a vu que(x) = deg(x)est une mesure réversible, donc invariante. En particulier, partant d"un sommetx,

le temps moyen de retour enxest x[+x] =1deg(x): Exemple 2 : urne d"Ehrenfest.On a vu que la mesuredonnée, pour0kN, par(k) =N k, est invariante. Ainsi, la loi= 2N=B(N;12 )(loi binomiale) est invariante. La chaîne de Markov est récurrente positive (on le savait : chaîne finie irréductible) et, par exemple,

0[+0] =1(0)= 2N:

C"est une quantité intéressante : partant d"un récipient vide (et l"autre plein), le temps moyen pour qu"il

redevienne vide croît exponentiellement avec le nombre de particules. Dans la situation réelle (gaz), le nombre

de molécules est de l"ordre deN= 1023(s"il y a 10 litres de gaz dans le récipient plein, par exemple), donc

même si on suppose (largement) queNéchanges ont lieu à chaque seconde, alors le temps moyen avant qu"à

nouveau le premier récipient soit vide est de l"ordre de N

12N= 10log10(N12N)= 10Nlog102log10N'1031022secondes,

ce qui est... colossal (il y a seulement 3 milliards de secondes par siècle). Ceci explique le paradoxe apparent

entre la récurrence de la chaîne de Markov (il y a un retour p.s. à la situation initiale) et l"absence d"observation

de situations où spontanément un récipient se viderait pour remplir l"autre. Le paradoxe est d"ailleurs accru

par le fait que la dynamique de cette chaîne de Markov est réversible, là où l"observation témoigne au contraire

d"une forte irréversibilité.

Exemple 3 : marche aléatoire réfléchie en 0.On cherche les mesures invariantes. Une mesureest

invariante si, et seulement si 8< :(0) =(1)q; (1) =(0) +(2)q; (x) =(x1)p+(x+ 1)qfor allx2: 4

On a donc(x+1)(x) =pq

((x)(x1))et on obtient par récurrence(x+1)(x)puis, pourx1, (x) =(0)q pq x

Sip <12

,pq <1doncP x(x)<1:Xest récurrente positive (donc récurrente, comme on l"a vu plus tôt). Si p=12

, les mesures invariantes ont une masse infinie doncXest récurrente nulle (car on a déjà vu la récurrence).

Sip >12

, les mesures invariantes ont bien sûr une masse totale infinie (la chaîne est transiente).

4 Théorèmes limites

4.1 Comportement presque sûr : théorème ergodique

On considère le temps passé en un état au cours d"une longue trajectoire de la chaîne de Markov.

Le théorème ergodique énonce que, si la chaîne de Markov est récurrente positive, alors elle passe une proportion

strictement positive de son temps dans chaque état, et cette proportion est donnée par sa loi invariante. Si elle

est récurrente nulle, alors elle passe en chaque point une proportion de son temps qui converge vers zéro.

Ceci se comprend via la formule(x) =1?

x[+x]: entre deux visites enx, il se passe un temps moyen?x[+x], donc sur une période de longueurn, on peut s"attendre à ce queXpasse un temps de l"ordre den? x[+x]enx (par la loi des grands nombres).

Théorème (Théorème ergodique, dans le cas récurrent positif)On suppose la chaîne de Markov irréductible et récurrente positive, de probabilité invariante.

Pour tout étatx, pour toute loi initiale,

-p.s.,1n n1X k=01 fXk=xg!n!1(x):

Plus généralement, pour toute fonctionf:E!?intégrable par rapport à, pour toute loi initiale,

-p.s.,1n n1X k=0f(Xk)!n!1Z E fd=X x2Ef(x)(x):

Ce théorème s"applique donc notamment, on le rappelle, aux chaînes de Markov finies irréductibles.

La version dans le cas récurrent nul est nettement moins utile que la précédente. La voici néanmoins :

Théorème (Théorème ergodique, dans le cas récurrent nul)On suppose la chaîne de Markov irréductible et récurrente nulle, ayant une mesure invariante.

Pour tout étatx, pour toute loi initiale,

-p.s.,1n n1X k=01 fXk=xg!n!10: Pour toutes fonctionsf;g:E!?bornées, telles queR

Egd6= 0, pour toute loi initiale,

-p.s.,P n1 k=0f(Xk)P n1 k=0g(Xk)!n!1R EfdR Egd=P x2Ef(x)(x)P x2Eg(x)(x):

Par exemple, la proportion de temps passé enxtend vers0, mais le rapport entre le temps passé enxet le

temps passé enyconverge vers(x)(y)(prendref=1fxgetg=1fyg).

4.2 Convergence en loi

À partir du théorème ergodique dans le cas récurrent positif, le théorème de convergence dominée permet de

déduire (en prenant l"espérance) : 1n n1X k=0? (Xk=x)!n(x): 5

Ainsi, la suite de terme général?(Xn=x)(autrement dit, la loi deXn) converge en moyenne de Cesàro vers

(x)dès que la chaîne de Markov est irréductible et récurrente positive.

Cependant, ceci ne suffit pas à ce que?(Xn=x)converge vers(x). Voici un contre-exemple typique : la

chaîne de Markov surf0;1g, de matrice de transition P=0 1 1 0

vérifie?0(Xn= 0) = 0sinest pair et1sinest impair, et on vérifie immédiatement que=1=2 1=2est

la loi invariante. La chaîne de Markov alterne entre les deux états, donc la fréquence d"occupation de chacun

converge bien sûr vers1=2(c"est ce que dit le théorème ergodique). Néanmoins, la probabilité d"être dans un

état donné au tempsnne converge pas.

Pour un exemple moins artificiel, il suffit de considérer l"urne d"Ehrenfest, où se pose exactement le même

problème : la parité deXnchange à chaque pas donc la suite de terme général?0(Xn=x)ne peut pas

converger. Comme on le voit, un obstacle tient à une notion depériodicité; c"est en fait le seul.

DéfinitionLapérioded"un étatx2Eest

d(x) = pgcd(fn1jPn(x;x)>0g):

Sid(x) = 1,xest ditapériodique.

C"est donc le pgcd des longueurs des chemins depuisxversx(dans le graphe associé à la chaîne de Markov).

On trouve dans l"exemple précédent et l"urne d"Ehrenfest (et les marches aléatoires simples) qued(x) = 2pour

tout étatx. Pour la ruine du joueur,d(x) = 2si1xN1, etd(0) =d(N) = 1. Notons que siP(x;x)>0, alors immédiatementd(x) = 1.

PropositionSix$y, alorsd(x) =d(y): la période est la même pour tous les états d"une même classe.

Démonstration:Soitntel quePn(x;x)>0. Il existek;ltels quePk(x;y)>0etPl(y;x)>0. Alors P n+k+l(y;y)Pl(y;x)Pn(x;x)Pk(x;y)>0 doncd(y)divisen+k+l. Mais on a aussi P k+l(y;y)Pl(y;x)Pk(x;y)>0

doncd(y)divisek+l, de sorte qued(y)divise(n+k+l)(k+l) =n. Ainsid(y)divise tous les multiples ded(x), donc

d(y)d(x). Par symétrie, on a aussid(x)d(y), d"oùd(x) =d(y).Pour une chaîne de Markov irréductible, on pourra donc parler sans ambiguïté de sa période, et de chaîne

apériodiquesi, pour un étatx(et donc pour tous),d(x) = 1.

ThéorèmeOn suppose que la chaîne de Markov(Xn)n0est irréductible, récurrente positive et apériodique. Alors,

pour toute loi initiale, pour tout étatx, (Xn=x)!n(x);

oùest l"unique loi invariante. Autrement dit, la loi deXnconverge vers la loi invariante. En particulier,

pour tousx;y2E, P n(x;y)!n(y); doncPnconverge vers une matrice dont les lignes sont toutes égales au vecteur-ligne. Plus généralement, pour toute loi initiale, pour toute fonction bornéef:E!?, [f(Xn)]!nZ fd=X x2Ef(x)(x): Démonstration:Admis (et la preuve est même officiellement hors-programme).6 1 2 345
1 23
Figure1 - Graphes de chaînes de Markov de période 3 et 1, respectivement

Deux extensions

Et si la chaîne n"est pas irréductible?SiCest une classe fermée, on peut étudier la chaîne de Markov

restreinte àC. Ceci revient à ne garder que les lignes et colonnes dePappartenant àC, et la fermeture garantit

que l"on obtient une matrice stochastique. Tous les théorèmes relatifs aux chaînes irréductibles peuvent donc

être appliqués aux diverses classes récurrentes.

La seule différence vient du fait que si le point de départ est un état transient, et s"il y a plusieurs classes

récurrente, il peut falloir appliquer le théorème à une classe ou à une autre. Attention, pour garantir que la

chaîne de Markov atteigne l"une des classes de récurrence, il faut demander à ce qu"il n"y ait qu"un nombre fini

d"états transients (elle passe un temps fini sur chacun, donc finit par les quitter tous). Voici quelques résultats

de ce type, qui découlent directement des théorèmes précédents.

ThéorèmeSoit(Xn)n0une chaîne de Markov. On noteTl"ensemble des états transients, etC1;:::;CNles classes ré-

currentes. On supposeTfini. Toute classe récurrenteCiadmet une demi-droite?+ide mesures invariantes.

L"ensemble des mesures invariantes de(Xn)n0est alors le cône +1++?+N:

Si chaque classeCiadmet une probabilité invariantei, alors l"ensemble des probabilités invariantes de

(Xn)n0est l"enveloppe convexe def1;:::;Ng, qui s"écrit aussi n

11++NN1;:::;N0et1++N= 1o

ThéorèmeSoit(Xn)n0une chaîne de Markov. On noteTl"ensemble des états transients, etC1;:::;CNles classes

récurrentes. On supposeTfini. On suppose que toute classe récurrenteCiadmet une (unique) probabilité

invariantei. Pour toute loi initiale, on a, pour toutx2 Ci, -p.s.,1n n X k=01 fXk=xg!n1fCi<1gi(x)

(ouCiest le temps d"atteinte de la classeCi) et plus généralement pour toute fonction bornéef:E!?,

-p.s.,1n n X k=0f(Xk)!nN X i=11 fCi<1gZ fdquotesdbs_dbs22.pdfusesText_28

[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

[PDF] exercice corrigé centrale hydraulique

[PDF] chaine énergétique centrale thermique

[PDF] chaine énergétique pile

[PDF] chaine énergétique exercices

[PDF] chaine énergétique éolienne

[PDF] chaine énergétique panneau solaire

[PDF] chaine energetique definition

[PDF] chaine énergétique exemple

[PDF] cours de logistique de distribution pdf