[PDF] fichier pdf - Loria PDF Markov

valuation de l'arête i → j : pi,j Une chaıne de Markov peut être vue comme une marche aleatoire sur G, connaissant π0 Exemple : 2 0,5 0,25 yyss

22 fév 2021 · Exercice 2 Soit k ∈ N∗ Soit X = (Xn) une chaîne de Markov (homogène) de loi initiale µ0 et de matrice de transition

[PDF] Chaines de Markov : compléments

de la leçon précédente est une chaıne de Markov irréductible de même que celui des souris dans le labyrinthe {1,2,3,4,5} Mais, si l'on modifie cet exemple en

[PDF] Chaînes de Markov

Exemple On représente usuellement une chaîne de Markov d'espace d'états X par un graphe orienté étiqueté G = (V,E) dont les sommets sont les éléments de

[PDF] Introduction aux chaines de Markov - CERMICS

invariante π : (π, f) Ce résultat est l'analogue de la loi forte des grands nombres Nous donnons des exemples importants d'utilisation des chaınes de Markov au

[PDF] Un exemple de chaîne de Markov dans lindustrie textile - Numdam

modèle en chaîne de Markov, ce qui lui a permis d'obtenir une première série de résultats importants concernant le fonctionnement de la carde (réf 1) Dans un

[PDF] fichier pdf - Loria

valuation de l'arête i → j : pi,j Une chaıne de Markov peut être vue comme une marche aleatoire sur G, connaissant π0 Exemple : 2 0,5 0,25 yyss

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

De plus, si les variables Xn sont de même loi µ, alors (Sn) est une chaîne de Markov homogène de matrice de transition Pij = µ(j − i) Exemple 2 (Modèle de

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

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

π(x)=1 − 1 2n−t 2 Exemples classiques de chaˆınes de Markov Exercice 3 1 Soit p ∈ [0,1] fixé

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.

Exemple:

2 0,5 ??0,25 0,25 ??0,1 ??1

0,5??0,5??3

0,6??0,4

??5

0,5??0,5??8/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 ConclusionMatrice de transition et distribution deXt Espace d"´etatsEfini, matrice de transition :P= (pi,j)

Propri´et´es´el´ementaires(cf poly.):la somme des ´el´ements d"une ligne dePvaut 1.

(matricestochastique)P ni,j= Pr(Xt+n=j|Xt=i) (?t)siπ0est la distribution deX0alors la distribution deXn est : n=πn-1P=π0Pn.

9/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 r´eductibles / irr´eductiblesD´efinition Une chaˆıne de Markov estirr´eductiblesi chaque ´etat est accessible `a partir de chaque autre ´etat.Autrement dit,Gest fortement connexe. Sinon elle est diter´eductible, etGadmet plusieurs composantes fortement connexes. Une composante qui ne m`ene `a aucune autre estfinale, sinon les ´etats qui la composent sonttransients(outransitoires) (une fois qu"on a quitt´e la classe d"un ´etat transitoire, on n"y retourne pas).

10/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"

quotesdbs_dbs29.pdfusesText_35

[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