[PDF] fichier pdf - Loria PDF Markov

de Markov Chaınes réductibles / irréductibles Exemple météorologique Aujourd'hui Une chaıne de Markov est irréductible si chaque état est accessible

Exemple 0 La marche aléatoire sur Z est irréductible (tous les états communiquent) Exemple 1 Considérons la chaîne de Markov, dont l'ensemble des états

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

22 fév 2021 · Parmi les exemples suivants, lesquels peuvent correspondre a une chaîne de Soit Q la matrice de transition d'une chaîne de Markov homogène Si une chaîne de Markov est irréductible, il n'y a qu'une seule classe

[PDF] Chaînes de Markov

EXEMPLE IMPORTANT PROPOSITION Soit (θn)n∈N Une chaîne de Markov irréductible sur un espace E fini est irréductible récurrente A Popier (ENSAI)

[PDF] Chaînes de Markov

Exemple La marche aléatoire sur Z/NZ est récurrente irréductible Plus généra- lement, toute chaîne de Markov finie dont le graphe orienté est connexe est

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

Pour quelles valeurs de p, q la chaıne est-elle irréductible ? aprériodique ? 2 Déterminer 2 Exemples classiques de chaˆınes de Markov Exercice 3 1

[PDF] Introduction aux chaines de Markov - CERMICS

1 35 n'est pas irréductible Exercice I 3 Soit X = (Xn,n ∈ N) une chaıne de Markov de matrice de transition P `a

[PDF] fichier pdf - Loria

de Markov Chaınes réductibles / irréductibles Exemple météorologique Aujourd'hui Une chaıne de Markov est irréductible si chaque état est accessible

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

Exemple 1 (Somme de variables aléatoires) Soit (Xn) une suite de variables aléa - Proposition 4 Une chaîne de Markov irréductible sur un espace d'état E fini

[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(

Chaˆınes de Markov

F. Sur - ENSMN

Introduction

Vocabulaire

Chaˆınes de Markov

Chaˆınes r´eductibles /irr´eductibles

Chaˆınes p´eriodiques /ap´eriodiques

Comportement

asymptotique

Comportement

asymptotique des chaˆınes ergodiques

Notion d"ergodicit´e

Th´eor`eme "descoupes"

Comportement

asymptotique des chaˆınes absorbantes

ConclusionCours de Tronc Commun Scientifique

Recherche Op´erationnelle

Les chaˆınes de Markov

Fr´ed´eric Sur

´Ecole des Mines de Nancy

www.loria.fr/≂sur/enseignement/RO/

1/26Chaˆınes de Markov

F. Sur - ENSMN

Introduction

Vocabulaire

Chaˆınes de Markov

Chaˆınes r´eductibles /irr´eductibles

Chaˆınes p´eriodiques /ap´eriodiques

Comportement

asymptotique

Comportement

asymptotique des chaˆınes ergodiques

Notion d"ergodicit´e

Th´eor`eme "descoupes"

Comportement

asymptotique des chaˆınes absorbantes ConclusionLes chaˆınes de Markov1Introduction

2Vocabulaire

Chaˆınes de Markov

Chaˆınes r´eductibles / irr´eductibles

Chaˆınes p´eriodiques / ap´eriodiques

3Comportement asymptotique

4Comportement asymptotique des chaˆınes ergodiques

Notion d"ergodicit´e

Th´eor`eme "des coupes"

5Comportement asymptotique des chaˆınes absorbantes

6Conclusion

2/26Chaˆınes de Markov

F. Sur - ENSMN

Introduction

Vocabulaire

Chaˆınes de Markov

Chaˆınes r´eductibles /irr´eductibles

Chaˆınes p´eriodiques /ap´eriodiques

Comportement

asymptotique

Comportement

asymptotique des chaˆınes ergodiques

Notion d"ergodicit´e

Th´eor`eme "descoupes"

Comportement

asymptotique des chaˆınes absorbantes

ConclusionExemple m´et´eorologique

Aujourd"hui il y a du soleil / il pleut.

Quel temps fera-t-il demain?

Mod´elisation: probabilit´es detransition

Pr ?Xn+1= S|Xn= S?= 0,9 Pr?Xn+1= S|Xn= P?= 0,5

Pr?Xn+1= P|Xn= S?= 0,1 Pr?Xn+1= P|Xn= P?= 0,5

Matrice de transition :P=?0,9 0,1

0,5 0,5?

Repr´esentation:

0,9??0,1??P

0,5??0.5??3/26Chaˆınes de Markov

F. Sur - ENSMN

Introduction

Vocabulaire

Chaˆınes de Markov

Chaˆınes r´eductibles /irr´eductibles

Chaˆınes p´eriodiques /ap´eriodiques

Comportement

asymptotique

Comportement

asymptotique des chaˆınes ergodiques

Notion d"ergodicit´e

Th´eor`eme "descoupes"

Comportement

asymptotique des chaˆınes absorbantes

ConclusionPr´ediction du temps

Initialement il fait beau.X0= S.

R´ealisations possibles de (Xn) :

1)X0= S,X1= S,X2= P,X3= S,X4= S...

2)X0= S,X1= P,X2= S,X3= S,X4= P...Important: le temps qu"il fera `a l"instantn+ 1 ne d´epend

que du temps `a l"instantn.Distribution deXn:πn=?Pr(Xn= S),Pr(Xn= P)?Formule des probabilit´es totales :

Pr(Xn+1= S) = Pr(Xn+1= S etXn= S)+Pr(Xn+1= S etXn= P) = Pr(Xn= S)·Pr(Xn+1= S|Xn= S) +

Pr(Xn= P)·Pr(Xn+1= S|Xn= P)

Conclusion:πn+1=πn·P.Exemple:π0=?1 0?,π1=?0,9 0,1?

2=π1·P=π0·P2=?0,86 0,14?

4/26

Chaˆınes de Markov

F. Sur - ENSMN

Introduction

Vocabulaire

Chaˆınes de Markov

Chaˆınes r´eductibles /irr´eductibles

Chaˆınes p´eriodiques /ap´eriodiques

Comportement

asymptotique

Comportement

asymptotique des chaˆınes ergodiques

Notion d"ergodicit´e

Th´eor`eme "descoupes"

Comportement

asymptotique des chaˆınes absorbantes

Conclusion´

Etat stationnaire du temps?

n=πn-1·P=π0·Pn Question 1: est-ce queπnconverge lorsquen→+∞?

(vers unedistribution stationnaireπ?)Question 2:π?est-elle unique?Question 3: quelle est la typologie des chaˆınes pour

lesquelles on peut pr´evoir le comportement deπn?Ici :π?existe, est unique, et vaut?0,833 0,167?

Veut dire : danstjours (assez grand), il y a 83% de chance qu"il fasse soleil (quelque soit le temps actuel). On pourra aussi dire (grˆace auth´eor`eme ergodique, cf poly) : en moyenne, il fait beau 83% des jours.

5/26Chaˆınes de Markov

F. Sur - ENSMN

Introduction

Vocabulaire

Chaˆınes de Markov

Chaˆınes r´eductibles /irr´eductibles

Chaˆınes p´eriodiques /ap´eriodiques

Comportement

asymptotique

Comportement

asymptotique des chaˆınes ergodiques

Notion d"ergodicit´e

Th´eor`eme "descoupes"

Comportement

asymptotique des chaˆınes absorbantes ConclusionLes chaˆınes de Markov1Introduction

2Vocabulaire

Chaˆınes de Markov

Chaˆınes r´eductibles / irr´eductibles

Chaˆınes p´eriodiques / ap´eriodiques

3Comportement asymptotique

4Comportement asymptotique des chaˆınes ergodiques

Notion d"ergodicit´e

Th´eor`eme "des coupes"

5Comportement asymptotique des chaˆınes absorbantes

6Conclusion

6/26Chaˆınes de Markov

F. Sur - ENSMN

Introduction

Vocabulaire

Chaˆınes de Markov

Chaˆınes r´eductibles /irr´eductibles

Chaˆınes p´eriodiques /ap´eriodiques

Comportement

asymptotique

Comportement

asymptotique des chaˆınes ergodiques

Notion d"ergodicit´e

Th´eor`eme "descoupes"

Comportement

asymptotique des chaˆınes absorbantes

ConclusionChaˆınes de Markov

SoitEun ensemble fini (ou d´enombrable) d"´etats.D´efinition Une suite de variables al´eatoires (Xn) `a valeurs dansEt.q. :

Pr(Xn+1=j|X0=i0,...,Xn=i) = Pr(Xn+1=j|Xn=i)

est unechaˆıne de Markov.D´efinition

Pr(Xn+1=j|Xn=i) =pn(i,j) est laprobabilit´e de

transitionde l"´etati`a l"´etatj.Remarque: on ne consid´erera que des chaˆıneshomog`enes

i.e. telles quepn(i,j) =pi,j. SiEfini,P= (pi,j) est lamatrice de transitionde (Xn).7/26Chaˆınes de Markov

F. Sur - ENSMN

Introduction

Vocabulaire

Chaˆınes de Markov

Chaˆınes r´eductibles /irr´eductibles

Chaˆınes p´eriodiques /ap´eriodiques

Comportement

asymptotique

Comportement

asymptotique des chaˆınes ergodiques

Notion d"ergodicit´e

Th´eor`eme "descoupes"

Comportement

asymptotique des chaˆınes absorbantes

ConclusionRepr´esentation graphique

SoitGle graphe orient´e valu´e tel que :sommets = ´etats (E)arˆete deiversjsipi,j>0.valuation de l"arˆetei→j:pi,j.

Une chaˆıne de Markov peut ˆetre vue comme une marche al´eatoire surG, connaissantπ0.

[PDF] [PDF] fichier pdf - Loria

Chaˆınes de Markov

F. Sur - ENSMN

Introduction

Vocabulaire

Chaˆınes de Markov

Chaˆınes r´eductibles /irr´eductibles

Chaˆınes p´eriodiques /ap´eriodiques

Comportement

Comportement

Notion d"ergodicit´e

Th´eor`eme "descoupes"

Comportement

ConclusionCours de Tronc Commun Scientifique

Recherche Op´erationnelle

Les chaˆınes de Markov

Fr´ed´eric Sur

´Ecole des Mines de Nancy

1/26Chaˆınes de Markov

F. Sur - ENSMN

Introduction

Vocabulaire

Chaˆınes de Markov

Chaˆınes r´eductibles /irr´eductibles

Chaˆınes p´eriodiques /ap´eriodiques

Comportement

Comportement

Notion d"ergodicit´e

Th´eor`eme "descoupes"

Comportement

2Vocabulaire

Chaˆınes de Markov

Chaˆınes p´eriodiques / ap´eriodiques

3Comportement asymptotique

4Comportement asymptotique des chaˆınes ergodiques

Notion d"ergodicit´e

Th´eor`eme "des coupes"

5Comportement asymptotique des chaˆınes absorbantes

6Conclusion

2/26Chaˆınes de Markov

F. Sur - ENSMN

Introduction

Vocabulaire

Chaˆınes de Markov

Chaˆınes r´eductibles /irr´eductibles

Chaˆınes p´eriodiques /ap´eriodiques

Comportement

Comportement

Notion d"ergodicit´e

Th´eor`eme "descoupes"

Comportement

ConclusionExemple m´et´eorologique

Aujourd"hui il y a du soleil / il pleut.

Quel temps fera-t-il demain?

Mod´elisation: probabilit´es detransition

Pr?Xn+1= P|Xn= S?= 0,1 Pr?Xn+1= P|Xn= P?= 0,5

Matrice de transition :P=?0,9 0,1

0,5 0,5?

Repr´esentation:

0,9??0,1??P

0,5??0.5??3/26Chaˆınes de Markov

F. Sur - ENSMN

Introduction

Vocabulaire

Chaˆınes de Markov

Chaˆınes r´eductibles /irr´eductibles

Chaˆınes p´eriodiques /ap´eriodiques

Comportement

Comportement

Notion d"ergodicit´e

Th´eor`eme "descoupes"

Comportement

ConclusionPr´ediction du temps

Initialement il fait beau.X0= S.

R´ealisations possibles de (Xn) :

1)X0= S,X1= S,X2= P,X3= S,X4= S...

2)X0= S,X1= P,X2= S,X3= S,X4= P...Important: le temps qu"il fera `a l"instantn+ 1 ne d´epend

Pr(Xn= P)·Pr(Xn+1= S|Xn= P)

2=π1·P=π0·P2=?0,86 0,14?

Chaˆınes de Markov