[PDF] [PDF] Chaînes de Markov

Une chaîne de Markov, de distribution initiale ν et matrice de transition Soit (Xn )n∈N chaîne de Markov (µ,P) avec µ probabilité réversible Alors la chaîne 



Previous PDF Next PDF





[PDF] Chaînes de Markov - DI ENS

Définition 8 1 3 On appelle réversible toute chaıne de Markov de distribution initiale π (une distribution stationnaire) positive telle que pour tout i, j ∈ E, π(i)pij  



[PDF] Introduction aux chaines de Markov - CERMICS

`a valeurs dans E est appelée chaıne de Markov de matrice de transition P si ( Xn,n ∈ N) est une chaıne de Markov réversible par rapport `a π et si la loi de X0  



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

Alors P n'est pas réversible par rapport à π Considérons à présent les deux problèmes suivants : 1 Etant donnée P matrice markovienne irréductible récurrente 



[PDF] Processus de Markov réversibles - Numdam

, lorsque la distribution des états est la distribution stationnaire A de telles chaînes de Markov, on peut associer des systèmes dont la covariance prend une forme 



[PDF] Chaînes de Markov

Une chaîne de Markov, de distribution initiale ν et matrice de transition Soit (Xn )n∈N chaîne de Markov (µ,P) avec µ probabilité réversible Alors la chaîne 



[PDF] Processus markoviens

8 Chaînes de Markov réversibles 33 8 1 Réversibilité Une chaîne de Markov en temps et espace discrets est un processus (Xn)n李0 décrit par un noyau p 



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

1 7 2 Chaîne de Markov en temps continu et espace discret 27 mesure réversible non-triviale pour un noyau irréductible est nécessairement propre



[PDF] Chaˆınes de Markov

2 jan 2010 · On retrouve le fait que la distribution stationnaire du mod`ele d'Ehrenfest est binomiale Les chaınes de Markov réversibles se prêtent mieux `a 



[PDF] Chaînes de Markov : théorie et applications - Département de

Mesures réversibles, II Soit P une matrice stochastique irréductible sur un espace d'états X On suppose que la chaîne de Markov associée est récurrente 

[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

[PDF] Chaînes de Markov

CHAÎNES DEMARKOV.

Alexandre Popier

ENSAI, Bruz

apopier@univ-lemans.fr http://www.univ-lemans.fr/apopier

Janvier-Mars 2011

A. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 1 / 51

PLAN1INTRODUCTION2DÉFINITIONS3CLASSIFICATION DES ÉTATS4CAS PARTICULIER:ESPACE D"ÉTATSEFINI5CHAÎNES DEMARKOV IRRÉDUCTIBLES RÉCURRENTES6CHAÎNES IRRÉDUCTIBLES RÉCURRENTES POSITIVES ET

APÉRIODIQUES7CHAÎNES SIMPLEMENT IRRÉDUCTIBLESA. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 2 / 51

SUITES RÉCURRENTES ALÉATOIRES.DÉFINITIONUnesuite récurrente aléatoire sur un espace E est une suite de v .a.

(Xn)n2Nà valeurs dans E définie sur un espace de probabilité( ;F;P) solution d"une équation récurrente de la forme : X n+1=f(n+1;Xn) où1

1;2;:::sont des v.a. i.i.d. à valeurs dans;2f: E!E est une application mesurable;3X

0(la condition initiale) est une v.a. (éventuellement déterministe)

indépendante de la suite(i)i2N.A. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 3 / 51

BATTRE LES CARTES.

I E: ensemble des permutations (d"un jeu de 52 cartes), de cardinal 52!; I : un sous-ensemble deE; I X0=e: identité (les cartes sont ordonnées),Xn+1=n+1Xn.

HYPOTHÈSES:est mélangeant, i.e. engendreE;la loi desicharge tous les éléments de.THÉORÈMELa suite(Xn)estrécurrente , satisfait uneloi des g randsnombres :

lim n!+11n n X k=11 Xk=x=152!:A. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 4 / 51

BATTRE LES CARTES:COMBIEN DE FOIS?THÉORÈMELa suite(Xn)estrécurrente , satisfait uneloi des g randsnombres :

lim n!+11n n X k=11

Xk=x=152!:I

On a une asymptote de type exponentiel (condition de Doeblin) : 12 X x2E

P(Xn=x)152!

Cn;avec <1:

I

Diaconis a montré qu"il suffit de battre le jeu 7 fois!A. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 5 / 51

MARCHES ALÉATOIRES SURZd.

I e1;:::;ed: base canonique deRd; I E=Zd; I =fe1;:::;ed;e1;:::;edg;ide loi uniforme sur; I

X0=0,Xn+1=Xn+n+1:marche aléatoire symétr iquesur Zd.THÉORÈME(POLYA, 1921)Pourd=1 ou 2, la marche aléatoire(Xn)estrécurrente :

P(9n>0;Xn=0) =1:

Pourd3, elle esttr ansiente: P(9n>0;Xn=0)<1.CONSTANTE DEPOLYAC"estp(d) =P(T0<+1),T0étant le temps de retour à 0. Alors

p(1) =p(2) =1,p(3)0;34,p(4)0;19,p(10)0;06.A. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 6 / 51

MARCHE ALÉATOIRE EN DIMENSION1.A. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 7 / 51 MARCHE ALÉATOIRE EN DIMENSION2.A. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 8 / 51

CONVOLUTION DEBERNOULLI.

I a>0; I E=R; I =f1;1g;ide loi uniforme sur; I X0=0,Xn+1=aXn+n+1.Poura=1, marche aléatoire surZ.Poura>1,P(limn!+1Xn2 f1;+1g) =1.Pour 0XnanX0=an11+:::+n. I

Yn=1+a2+:::+an1nconverge versY12h

11a;11ai

.PROPOSITION(Xn)converge en loi vers Y1:limn!+1E(Xn) =E(Y1).A. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 9 / 51

a=0;25. Comportement p.s. deXnetYn:A. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 10 / 51 a=0;25. Comportement en loi deX100etY100:A. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 10 / 51 a=0;7. Comportement p.s. deXnetYn:A. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 11 / 51 a=0;7. Comportement en loi deX100etY100:A. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 11 / 51

CONVOLUTION DEBERNOULLI:LOI DE LA LIMITE.

I Fa(t) =a(] 1;t]) =P(Y1t).PROPOSITIONPour tout I= [;]R,limn!+11n n1X k=01

Xk2I=Fa()Fa().PROPRIÉTÉS DEFaF

aest l"unique solution continue de

8t2R;G(t) =12

Gt1a +Gt+1a

:Sia<1=2,aest continue singulière (1935).Sia=1=2,aest la loi uniforme sur[2;2](1935).Pour presque touta>1=2,aest à densité (1995).A. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 12 / 51

SIMULATIONS DE FRACTALES.

I E=Rd; I =f1;:::;kg;ide loi uniforme sur; I

X0=0,Xn+1=A(n+1)Xn+B(n+1).

I

A(1);:::;A(k)matrices,B(1);:::;B(k)vecteurs.THÉORÈMELes conclusions de la convolution de Bernoulli restent les mêmes :

convergence en loi de(Xn), théorème de convergence presque sûre des moyennes de Césaro.SPIRALEd=k=2;A(1) =0;8390;303

0;383 0;924

,A(2) =0;1610;136

0;1380;182

;B(1) =0;232 0;080 ,B(2) =0;921 0;178 A. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 13 / 51 FRACTAL EN SPIRALE.A. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 14 / 51

PLAN1INTRODUCTION2DÉFINITIONS3CLASSIFICATION DES ÉTATS4CAS PARTICULIER:ESPACE D"ÉTATSEFINI5CHAÎNES DEMARKOV IRRÉDUCTIBLES RÉCURRENTES6CHAÎNES IRRÉDUCTIBLES RÉCURRENTES POSITIVES ET

APÉRIODIQUES7CHAÎNES SIMPLEMENT IRRÉDUCTIBLESA. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 15 / 51

MATRICES DE TRANSITION.DÉFINITION(ESPACE D"ÉTATS,MESURE)DANS TOUT LE COURS, E est un espacedénombr able. Un élément

x2E est unétat . Unemesure = (x;x2E)est un vecteur ligne de nombres réels positifs ou nuls. SiX x2E x=1, la mesure est une probabilité ou distr ibution

.DÉFINITION(MATRICE DE TRANSITION)Unematr icede tr ansitionP sur E est une application de E E dans

[0;1]telle que

8x2E;X

y2EP(x;y) =1:

On dit aussi que la matrice est

stochastique A. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 16 / 51

CHAÎNE DEMARKOVDÉFINITION(CHAÎNE DEMARKOV)Une suite de v.a.(Xn)n2Nà valeurs dans E est appeléechaîne de

Markov

si pour tout n 2Nla loi conditionnelle de Xn+1sachant X

0;:::;Xnest égale à sa loi conditionnelle sachant Xn, i.e. pour tout

y

0;:::;yn+1dans E :

P(Xn+1=yn+1jX0=y0;:::;Xn=yn) =P(Xn+1=yn+1jXn=yn):I

Pn(x;y) =P(Xn+1=yjXn=x):DÉFINITIONSi P

n(x;y) =P(Xn+1=yjXn=x)ne dépend pas de n, on parle de chaîne de Markov homogène . Dans ce cas, la matrice P obtenue est stochastique. A. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 17 / 51

DÉFINITION"ÉQUIVALENTE»DÉFINITION(CHAÎNE DEMARKOV(;P))Unechaîne de Mar kov, dedistr ibutioninitiale etmatr icede tr ansition

P, à valeurs dans E est une suite de v.a.(Xn)n2Ndéfinies sur ;F;P), telle que :1X

0a pour loi,2et pour n0, conditionnellement à Xn=x, la loi de Xn+1est

donnée par(P(x;y);y2E)et est indépendante de X0;:::;Xn1.TRADUCTION MATHÉMATIQUEPour toutn0 et touty0;:::;yn+1dansE:1P(X0=y0) =0;2P(Xn+1=yn+1jX0=y0;:::;Xn=yn) =P(yn;yn+1).A. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 18 / 51

EXEMPLE IMPORTANTPROPOSITIONSoit

(n)n2Nune suite de v.a. i.i.d. à valeurs dans,X

0une v.a. à valeurs dans E, indépendante de la suite(n)n2N,f: E!E une fonction mesurable.

Alors la suite(Xn)n2Nde v.a. à valeurs dans E et définie par la relation de récurrence :

8n2N;Xn+1=f(n+1;Xn)

est une chaîne de Markov homogène.CONSÉQUENCES:tous les suites vues dans la partie 1 sont des

chaînes de Markov. A. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 19 / 51

ÉQUATION DECHAPMAN-KOLMOGOROVTHÉORÈMESoit(Xn)une chaîne de Markov surEde matrice de transitionP, de

distribution initiale. Alors

P(X0=y0;:::;Xn=yn) =(y0)P(y0;y1):::P(yn1;yn):1SiXna pour loin, alors :n+1=nP=Pn+1.2Pour tout(x;y)2E2,P(Xn=yjX0=x) =Pn(x;y).3Pour toute fonctionh:E!Rbornée,

E(h(Xn)jX0=x) =Pnh(x):REMARQUELes fonctions h:E!Rsont représentées par des vecteurs colonnes.A. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 20 / 51

MESURE INVARIANTE,RÉVERSIBLEDÉFINITION(MESURE INVARIANTE)Une mesuresur E est ditein variantesi et seulement si c"est un point

fixe de l"équation Chapman-Kolmogorov, i.e.=P.DÉFINITION(MESURE RÉVERSIBLE)Une mesuresur E est diterév ersiblesi et seulement si

8(x;y)2E2; (x)P(x;y) =(y)P(y;x):PROPOSITIONUne mesure réversible est invariante.

A. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 21 / 51 CHAÎNE RETOURNÉE.LEMMESi(Xn)n2Nest une chaîne de Markov, alors pour tout N2N,

XN=n^XNn=XNn;0nNo

est une chaîne de Markov, appelée chaîne retour née

à par tirde

l"instant N.PROPOSITIONSoit(Xn)n2Nchaîne de Markov(;P)avecprobabilité réversible. Alors la chaîne retournée^XN=f^XNn;0nNgest une chaîne de Markov(;P).A. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 22 / 51 PROPRIÉTÉ DEMARKOV.DÉFINITIONLeprocessus décalé X n+= (Xn+;k)k2Nest défini par

8k0;Xn+;k=Xn+k:THÉORÈMESoit(Xn)une chaîne de Markov surEde matrice de transitionP, de

distribution initiale. Alors conditionnellement àXn=x, le processus X n+est une chaîne de Markov de matrice de transitionP, de distribution initialexet est indépendant des v.a.X0;:::;Xn.I Phénomène sans mémoire!A. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 23 / 51

PROPRIÉTÉ DEMARKOV FORTE.

Pourn0,Fn: tribu des événements déterminés parX0;X1;:::;Xn F n=n f!2 ; (X0(!);:::;Xn(!))2Bng;Bn2 P(En+1)o :DÉFINITION(TEMPS D"ARRÊT)Une v.a.à valeurs dansN[ f+1gest appelée untemps d"arrêt si

pour tout n2N,f=ng 2 Fn.PROPRIÉTÉ DEMARKOV FORTESoit(Xn)une chaîne de Markov(;P)etun temps d"arrêt. Alors

conditionnellement enf <+1g \ fX=xg, le processus(X+n)n2N est une chaîne de Markov(x;P)indépendante deF: pour tout

A2 F,m>0,x1;:::;xmdansE:

P(A\ fX+1=x1;:::;X+m=xmgjX=x; <1)

=P(AjX=x; <1)Px(X1=x1;:::;Xm=xm):A. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 24 / 51

NOTATIONS POUR LA SUITE DU COURS.

I

E: espace fini ou dénombrable;

I

P: matrice de transition;

I

Ploi sachant queX0suit la loi;

I

E: espérance sousP;

I

Pxloi sachant queX0=x, i.e.=x

I

Ex: espérance sousPx;

I (E): ensemble des probabilités surE.LEMME(E) =(

2RE; (x)0;X

x2E(x) =1) A. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 25 / 51

PLAN1INTRODUCTION2DÉFINITIONS3CLASSIFICATION DES ÉTATS4CAS PARTICULIER:ESPACE D"ÉTATSEFINI5CHAÎNES DEMARKOV IRRÉDUCTIBLES RÉCURRENTES6CHAÎNES IRRÉDUCTIBLES RÉCURRENTES POSITIVES ET

APÉRIODIQUES7CHAÎNES SIMPLEMENT IRRÉDUCTIBLESA. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 26 / 51

ÉTATS RÉCURRENTS ET TRANSITOIRES.

TEMPS DE RETOUR:Tx=inffn1;Xn=xg.DÉFINITIONL"état x2E estrécurrent si Px(Tx<+1) =1, et esttr ansitoiresi

P x(Tx<+1)<1.NOMBRE DE RETOURS:Nx=X n11 Xn=x.PROPOSITION1Si x est récurrent,Px(Nx= +1) =1.2Si x est transitoire, P x(Nx=k) = (1x)kx;pour k0; avecx=Px(Tx<+1).A. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 27 / 51

ÉTATS RÉCURRENTS ET TRANSITOIRES.

NOMBRE DE RETOURS:Nx=X

n11 Xn=x.PROPOSITION1Si x est récurrent,Px(Nx= +1) =1.2Si x est transitoire, P x(Nx=k) = (1x)kx;pour k0; avecx=Px(Tx<+1).COROLLAIREL"état x2E est récurrent si et seulement si +1X n=0(Pn)(x;x) = +1:A. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 27 / 51

CLASSE D"ÉQUIVALENCE.DÉFINITIONL"état y2E estaccessib leà par tirde x 2E (notéx !y)s"il

existe n2Ntel quePx(Xn=y)>0.Les états x et ycomm uniquent(noté x $y)si x !y et y!x.CLASSES D"ÉQUIVALENCE:$est une relation d"équivalence qui crée

une partition deEen classes d"équivalence modulo$.THÉORÈMESoitCEune classe d"équivalence modulo$. Alors tous les états

deCsont soit récurrents, soit transitoires.A. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 28 / 51

CLASSES FERMÉES.DÉFINITIONUne classe CE est ditef erméesi pour tous x et y dans E :

x2C et x!y)y2C:PROPOSITIONLa restriction de la chaîne de Markov à une classe fermée C est une

chaîne de Markov d"espace d"états C.SiC=fx0gest fermée, on dit quex0est unétat absorbant .THÉORÈMEToute classe récurrente est fermée.

Toute classe fermée et finie est récurrente. A. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 29 / 51 IRRÉDUCTIBILITÉ.DÉFINITIONUne chaîne de Markov(;P)est I irréductible si E est constitué d"une seule classe d"équiv alence; I irréductible récurrente si elle est irréductib leet si tous les états sont récurrents. I irréductible transiente si elle est irréductib leet si tous les états

sont transitoires.PROPOSITIONUne chaîne de Markov irréductible sur un espace Efiniest irréductible

récurrente. A. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 30 / 51

IRRÉDUCTIBILITÉ.DÉFINITIONUne chaîne de Markov(;P)estirréductib lesi, pour tout couple

(x;y)2E2, il existeun entier k=k(x;y)et une suite finie x=x0;x1;:::;xk1;xk=y tels que P(xi;xi+1)>0pour i=0;:::;k1.

C"est-à-dire :P(Xk=yjX0=x) =Pk(x;y)>0:THÉORÈMESi(Xn)n2Nest irréductible,1les fonctionsP-invariantes (i.e.Pf=f) sont les fonctions

constantes.2Padmet au plus une probabilité invariante. De plus(x)>0 pour toutx2E.A. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 31 / 51 CLASSIFICATION.1x6!x:xtransitoire.2Les étatsxt.q.x!xpeuvent être classés en classes d"équivalence irréductibles par la relation$: I classes irréductibles non fermées : transitoires;

Iclasses irréductibles fermées : récurrentes ou transitoires.3À partir d"un état récurrent,

I la chaîne restreinte à la classe d"équivalence de cet état est irréductible.

IChaque état de cette classe est visité une infinité de fois.4À partir d"un état transitoire,

I soit la chaîne finit par atteindre une des classes récurrentes; Isoit elle part à l"infini après être passée un nombre fini de fois par les états de la classe transitoire. A. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 32 / 51

PLAN1INTRODUCTION2DÉFINITIONS3CLASSIFICATION DES ÉTATS4CAS PARTICULIER:ESPACE D"ÉTATSEFINI5CHAÎNES DEMARKOV IRRÉDUCTIBLES RÉCURRENTES6CHAÎNES IRRÉDUCTIBLES RÉCURRENTES POSITIVES ET

APÉRIODIQUES7CHAÎNES SIMPLEMENT IRRÉDUCTIBLESA. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 33 / 51

EXISTENCE D"UNE MESURE INVARIANTE.

DANS CE PARAGRAPHE,

I E: espace fini de cardinald, donc en bijection avecf1;:::;dg; I

P: matrice de transition de tailledd;

I

(E): ensemble des probabilités surE.THÉORÈMEL"ensemble des probabilités invariantes pourPest un sous-ensemble

non vide, compact et convexe de(E).REMARQUEPas d"unicitéen génér al! A. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 34 / 51

THÉORÈME ERGODIQUE.THÉORÈMESupposons(Xn)n2Nirréductible de probabilité invariante. Alors1presque sûrement

lim n!+11n n1X k=01

Xk=x=(x):2Pour toutx2E,

(x) =1E x(Tx)>0;

avecTx=inffk1;Xk=xginstant de premier retour enx.COROLLAIRESi la chaîne est irréductible, alors elle visite infiniment souvent tous les

points de l"espace d"états E. A. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 35 / 51

CHAÎNE FORTEMENT IRRÉDUCTIBLE.PROPOSITIONSupposons la chaîne irréductible de probabilité invariante. Alors pour

toute probabilitésur E, lim n!+1n1X k=0Pk=;ou encorelimn!+1n1X k=0P (Xk=x) =(x):DÉFINITIONUne chaîne de Markov(;P)estf ortementirréductib les"il e xisteun entier k tel que

8(x;y)2E2;Pk(x;y)>0:A. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 36 / 51

CHAÎNE FORTEMENT IRRÉDUCTIBLE.THÉORÈMESupposons(Xn)n2Nfortement irréductible de probabilité invariante.

Soitkl"entier de la définition précédente et =(P) =X y2E infx2EPk(x;y) >0:

Alors pour toute probabilitésurEet toutn2N,

sup

AEjP(Xn2A)(A)j (1)[n=k];

avec[a]la partie entière dea. Ainsi limn!+1Pn=.A. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 36 / 51

APÉRIODICITÉ(1).DÉFINITIONSoit x2E et R(x) =fn2N;Pn(x;x)>0g. Lapér iodep (x)de x est

le plus grand commun diviseur de R(x).PROPOSITIONSupposons la chaîne irréductible. Alors tous les points de E ont la

même période.DÉFINITIONCette période commune est lapér iodede la chaîne ;chaîne qui est

quotesdbs_dbs29.pdfusesText_35