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 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
CHAÎNES DEMARKOV.
Alexandre Popier
ENSAI, Bruz
apopier@univ-lemans.fr http://www.univ-lemans.fr/apopierJanvier-Mars 2011
A. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 1 / 51PLAN1INTRODUCTION2DÉ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ù11;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 / 51BATTRE 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 / 51BATTRE LES CARTES:COMBIEN DE FOIS?THÉORÈMELa suite(Xn)estrécurrente , satisfait uneloi des g randsnombres :
lim n!+11n n X k=11Xk=x=152!:I
On a une asymptote de type exponentiel (condition de Doeblin) : 12 X x2EP(Xn=x)152!
Cn;avec <1:
IDiaconis 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; IX0=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 / 51CONVOLUTION 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. IYn=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 / 51CONVOLUTION DEBERNOULLI:LOI DE LA LIMITE.
I Fa(t) =a(] 1;t]) =P(Y1t).PROPOSITIONPour tout I= [;]R,limn!+11n n1X k=01Xk2I=Fa()Fa().PROPRIÉTÉS DEFaF
aest l"unique solution continue de8t2R;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; IX0=0,Xn+1=A(n+1)Xn+B(n+1).
IA(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;3030;383 0;924
,A(2) =0;1610;1360;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 / 51PLAN1INTRODUCTION2DÉ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 que8x2E;X
y2EP(x;y) =1:On dit aussi que la matrice est
stochastique A. Popier (ENSAI)Chaînes de Markov.Janvier-Mars 2011 16 / 51CHAÎ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 X0;:::;Xnest égale à sa loi conditionnelle sachant Xn, i.e. pour tout
y0;:::;yn+1dans E :
P(Xn+1=yn+1jX0=y0;:::;Xn=yn) =P(Xn+1=yn+1jXn=yn):IPn(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 / 51DÉ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 :1X0a 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,X0une 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. AlorsP(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 par8k0;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 / 51PROPRIÉ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 sipour 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 toutA2 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 / 51NOTATIONS POUR LA SUITE DU COURS.
IE: espace fini ou dénombrable;
IP: matrice de transition;
IPloi sachant queX0suit la loi;
IE: espérance sousP;
IPxloi sachant queX0=x, i.e.=x
IEx: 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 / 51PLAN1INTRODUCTION2DÉ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 / 51CLASSE 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 étatssont 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 / 51IRRÉ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 / 51PLAN1INTRODUCTION2DÉ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; IP: 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 / 51THÉORÈME ERGODIQUE.THÉORÈMESupposons(Xn)n2Nirréductible de probabilité invariante. Alors1presque sûrement
lim n!+11n n1X k=01Xk=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 / 51CHAÎ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 que8(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,
supAEjP(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 estle 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