[PDF] Chaînes de Markov. Si Pn(xy) = P(Xn+





Previous PDF Next PDF



Chaînes de Markov

Une chaîne de Markov est un processus aléatoire (Xn)n2N Une chaîne de Markov finie est dite apériodique si la période de sa matrice de transition est 1.



CHAÎNES DE MARKOV

A toute matrice de transition on peut associer un graphe dirigé



Chaînes de Markov.

Si Pn(xy) = P(Xn+1 = y



Xn = x) ne dépend pas de n

la matrice P obtenue est stochastique. A. Popier (ENSAI).



Cours de Tronc Commun Scientifique Recherche Opérationnelle

Conséquence 2 : d`es que le graphe d'une cha?ne de Markov irréductible a une boucle sur un sommet alors la cha?ne est apériodique. 13/26. Châ?nes de Markov. F.



Chaînes de Markov et Processus markoviens de sauts. Applications

Théorème 7 Soit (Xn)n?N une chaîne de Markov de matrice de transition P irréductible récurrente positive apériodique. Soit ? la probabilité invariante.



Chaînes de Markov

chaînes de Markov irréductibles et apériodiques. Exercice 70 Reprendre tous les exemples de noyaux de transition vus précédemment et étudier leur période.



1 Définition

Dans le cas où il y a plusieurs classes fermées se pose la question de savoir dans quelle classe la chaîne de Markov va ultimement être « bloquée ». Définition.



Chaînes de Markov (et applications)

22 févr. 2021 En particulier étant donné Q une matrice stochastique



3 Mesures invariantes

Fin du cours sur les chaînes de Markov. 3 Mesures invariantes. Dans toute cette partie on supposera a priori la chaîne de Markov (Xn)n?0 irréductible.



Classification des états de la Chaîne de Markov Classification des

ergodiques. ? Pour toute chaîne de Markov irréductible et ergodique il existe une distribution stationnaire dont la distribution de ses états.



[PDF] CHAÎNES DE MARKOV - Institut de Mathématiques de Bordeaux

Soit Xn est une chaîne de Markov de matrice de transition P Une chaîne apériodique est une chaîne de dont tous les états sont apériodiques



[PDF] Chaînes de Markov

Une chaîne de Markov finie est dite apériodique si la période de sa matrice de transition est 1 On peut montrer que si la période d'une matrice 



[PDF] CHAÎNES DE MARKOV - ceremade

CHAÎNES DE MARKOV Spécialité : INGENIEUR 1ère année Béatrice de Tilière La partie “Rappels de probabilités” est basée sur des notes écrites en 



[PDF] Chaînes de Markov (et applications)

22 fév 2021 · On appelle graphe d'une chaîne de Markov (ou d'une matrice de transition ) le graphe dont les sommets sont les états possibles et étant donné x 



[PDF] Chapitre 8 Chaˆ?nes de Markov - DI ENS

Si d = 1 la matrice de transition et la cha?ne sont dites apériodiques Théor`eme 8 1 10 Soit P une matrice stochastique irréductible de période d Alors



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

chaînes de Markov irréductibles et apériodiques Exercice 70 Reprendre tous les exemples de noyaux de transition vus précédemment et étudier leur période



[PDF] Introduction aux chaines de Markov - CERMICS

Soit P une matrice stochastique sur E Une suite de variables aléatoires (Xnn ? N) `a valeurs dans E est appelée cha?ne de Markov de matrice de transition P 



[PDF] Chaînes de Markov

On notera (?A P?) l'espace probabilisé adapté à la chaîne de Markov homo- gène de matrice de transition P donnée et de loi initiale ? (? probabilité donnée



[PDF] Chaînes de Markov

Si Pn(xy) = P(Xn+1 = yXn = 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)



[PDF] Les cha?nes de Markov - Loria

Pr(Xn+1 = jXn = i) = pn(i j) est la probabilité de transition de l'etat i `a l'etat j Remarque : on ne considérera que des cha?nes homog`enes i e telles 

  • Quel est le principe Sous-jacent de la technique des chaines de Markov ?

    Si une chaîne de Markov est irréductible et si son espace d'états est fini, tous ses états sont récurrents positifs. La loi forte des grands nombres est alors en vigueur. Plus généralement, tous les éléments d'une classe finale finie sont récurrents positifs, que l'espace d'états soit fini ou bien infini dénombrable.

  • C'est quoi une chaîne de Markov ergodique ?

    est indépendant de l'état de départ. Pour les chaînes ergodiques, on demande simplement que tout état soit atteignable depuis tout autre, mais le nombre de pas n'est pas nécessairement fixé.

  • Comment calculer la période d'une chaîne de Markov ?

    Cela conduit au calcul suivant : P(X2 = s/X0 = m) = P(X2 = s/X1 = m) · P(X1 = m/X0 = m) + P(X2 = s/X1 = s) · P(X1 = s/X0 = m) = 0,15 · 0,0,55 + 0,15 · 0,1=0,0975. La cha?ne n'est pas périodique comme on peut le voir facilement sur son diagramme en points et fl`eches.
  • = P(Xn+1 = yXn = xn). Cette preuve permet de montrer rigoureusement que la marche aléatoire sur Zd est bien une chaîne de Markov. Dans le monde déterministe, cela revient à étudier les suites (xn)n?0 définies par ré- currence de la manière suivante : xn+1 = f(xn,n).
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;quotesdbs_dbs28.pdfusesText_34
[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

[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