Cours de Tronc Commun Scientifique Recherche Opérationnelle PDF

CHAÎNES DE MARKOV

Evidemment si X0 suit la loi stationnaire ?

IFT-3655 Modèles Stochastiques orange Chaînes de Markov en

On peut vouloir calculer par exemple ? = P[N ? m

Chapitre 2 - Chaines de Markov : compléments

Dans cette leçon nous examinons quelles sont les principales propriétés des cha?nes de. Markov et nous étudions quelques exemples suplémentaires. 2.1

Un exemple de chaîne de Markov dans lindustrie textile

UN EXEMPLE DE CHAINE DE MARKOV. DANS L'INDUSTRIE TEXTILE. F. VROOMEN. Ingénieur A.I.T.V.. (Chercheur de Centexbel au laboratoire A. PELTZER VERVIERS).

Cours de Tronc Commun Scientifique Recherche Opérationnelle

valuation de l'arête i ? j : pij . Une cha?ne de Markov peut être vue comme une marche aleatoire sur G

Chaînes de Markov (et applications)

22 févr. 2021 Soit Q la matrice de transition d'une chaîne de Markov homogène. ... Jusqu'ici on a uniquement pris des exemple où l'état initial était ...

Chaînes de Markov.

Une chaîne de Markov de distribution initiale ? et matrice de transition. P

CHAÎNES DE MARKOV Master MIMSE Bordeaux Dans tout ce cours

appelé processus de Markov et dans le cas où le temps est discret : chaîne de Markov. Exemples : (1) Gestion de stock : Dans de nombreuses situations

Classification des états dune chaîne de Markov

classes s'appellent les classes de communication. Exemple 1. Considérons le graphe suivant associé à une chaîne de Markov homogène dont.

Chaînes de Markov : théorie et applications

CONSTRUCTION ET EXEMPLES DE CHAÎNES DE MARKOV. 7. Définition intuitive. Soit P une matrice stochastique sur un espace d'états X et ?0 une mesure de.

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

Les chaînes de Markov constituent un des exemples les plus simples de suites de variables aléatoires (Xn) Les variables (Xn) sont à valeurs dans un

[PDF] CHAÎNES DE MARKOV - ceremade

5 3 4 Graphe associé à une chaîne de Markov homogène Par exemple on cherche la probabilité que la somme de deux dés lancés au hasard

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

1 2 Exemples Exercice 7 Vérifier qu'une suite de variables aléatoires i i d forme une chaîne de Markov Quels sont la loi initiale et le noyau de

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

Cette technique qui est le moteur de la plupart des calculs en théorie des cha?nes de Markov va être illustrée par les exemple suivants Exemple 8 1 4: La

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

22 fév 2021 · Exemples et définitions Idée : Une chaîne de Markov est une suite de variables aléatoires dans le temps ou conditionnel-

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

comment construire explicitement une chaîne de Markov de loi initiale et matrice de transition données et présenter des exemples

[PDF] Chaînes de Markov

de transition étant l'étiquette de l'arête x ! y Considérons par exemple la chaîne de Markov d'espace d'états [[1N]] et de matrice de transition

[PDF] Chaînes de Markov

Exemples : vérifier dans chacun des exemples suivants que Xn est une chaîne de Markov homogène et préciser sa matrice de transition

[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

[PDF] Chaînes de Markov - Mathieu Mansuy

4 Exemple du Google PageRank 10 Compétences attendues / Savoir écrire la matrice de transition d'une chaîne de Markov

Comment faire une chaîne de Markov ?
Une chaîne de Markov sur X de matrice de transition P est une suite de variables aléatoires (Xn)n2Ndéfinies sur un espace (?, b, P) et à valeurs dans X, telle que pour tout n, et tous points x0,,xn+1, P[Xn+1 = xn+1X0 = x0,,Xn = xn] = P(xn,xn+1).
Comment montrer qu'une chaîne est une chaîne de Markov ?
= 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).
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.
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.

Cours de Tronc Commun Scientifique Recherche Opérationnelle

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] Cours de Tronc Commun Scientifique Recherche Opérationnelle

Comment faire une chaîne de Markov ?

Comment montrer qu'une chaîne est une chaîne de Markov ?

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

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