Chaînes de Markov : une initiation pdf/markov_info1... · Chaînes de Markov : une initiation...

Chaînes de Markov : une initiation

INFO1 - Semaine 22

Guillaume CONNAN

IUT de Nantes - Dpt d'informatique

Dernière mise à jour : 30 mai 2012

(IUT de Nantes - Dpt d'informatique ) 1 / 35

Sommaire

1 Vision dynamique des probabilités -

Automates

Découverte

Premier exemple - Règles de parcours

Deuxième exemple - Valeur moyenne

2 Comportement asymptotique des chaînes de

Markov

Àíäðåé Àíäðååâè÷ ÌÀÐÊÎÂ (1856 - 1922)

Vision dynamique des probabilités - Automates

Sommaire

Automates

Découverte

Markov

Vision dynamique des probabilités - Automates Découverte

Sommaire

Automates

Découverte

Markov

Les boules dans l'urne, deux tirages successifs sans remise...

i jpij

Le présent contient toutes les données du passé...

i jpij

Le présent contient toutes les données du passé...

Vision dynamique des probabilités - Automates Premier exemple - Règles de parcours

Sommaire

Automates

Découverte

Markov

état absorbant

états intérieurs

chaîne absorbante

parcours (promenade) aléatoire

longueur d'un parcours

état absorbant

états intérieurs

chaîne absorbante

état absorbant

états intérieurs

chaîne absorbante

état absorbant

états intérieurs

chaîne absorbante

état absorbant

états intérieurs

chaîne absorbante

état absorbant

états intérieurs

chaîne absorbante

Les règles

1 la probabilité de réaliser un parcours donné à partir d'un point donnéest égale au produit de toutes les probabilités de transition le long dece parcours ;

2 La probabilité d'atteindre un sous-ensemble du bord à partir d'un étatdonné est égale à la somme des probabilités de tous les parcours allantde cet élément aux éléments du sous-ensemble ;

3 la durée moyenne des parcours allant d'un état au bord (le temps

moyen d'absorption) est la moyenne des longueurs des parcours de cesommet au bord pondérée par les probabilités de chaque transition. Sion introduit une variable aléatoire égale au temps de parcours, il s'agitdonc de l'espérance de cette v.a.r.

Les règles

p1 =(1

)︸︷︷︸0 boucle

23+4+ 1

)︸︷︷︸

1 boucle

23+2×4+ 1

24+2×4

)︸︷︷︸

2 boucles

23+3×4+ 1

24+3×4

)︸︷︷︸

3 boucles

+·· ·

p1 =(1

)︸︷︷︸0 boucle

23+4+ 1

)︸︷︷︸

1 boucle

23+2×4+ 1

24+2×4

)︸︷︷︸

2 boucles

23+3×4+ 1

24+3×4

)︸︷︷︸

3 boucles

+·· ·

Faites un calcul similaire pour déterminer la probabilité de perdre : vousconnaissez déjà le résultat donc vous pourrez contrôler vos calculs...

Temps de parcours

1 1→ 0 précédé de k cycles : X = 4k +1,

P([X = 4k +1])=(124

)k × 12 = 1

24k+1 ;

2 1→ 2→ 0 précédé de k cycles : X = 4k +2,

P([X = 4k +2])=(124

)k × (12

)2 = 124k+2 ;

3 1→ 2→ 4→ 5 précédé de k cycles : X = 4k +3,

P([X = 4k +3])=(124

)k × (12

)3 = 124k+3 ;

4 1→ 2→ 4→ 3→ 5 précédé de k cycles : X = 4k +4,

P([X = 4k +4])=(124

)k × (12

)4 = 124k+4 .

Temps de parcours

P([X = 4k +1])=(124

)k × 12 = 1

24k+1 ;

P([X = 4k +2])=(124

)k × (12

)2 = 124k+2 ;

P([X = 4k +3])=(124

)k × (12

)3 = 124k+3 ;

P([X = 4k +4])=(124

)k × (12

)4 = 124k+4 .

Temps de parcours

P([X = 4k +1])=(124

)k × 12 = 1

24k+1 ;

P([X = 4k +2])=(124

)k × (12

)2 = 124k+2 ;

P([X = 4k +3])=(124

)k × (12

)3 = 124k+3 ;

P([X = 4k +4])=(124

)k × (12

)4 = 124k+4 .

Temps de parcours

P([X = 4k +1])=(124

)k × 12 = 1

24k+1 ;

P([X = 4k +2])=(124

)k × (12

)2 = 124k+2 ;

P([X = 4k +3])=(124

)k × (12

)3 = 124k+3 ;

P([X = 4k +4])=(124

)k × (12

)4 = 124k+4 .

Rappel

Nous avons prouvé au module précédent que :

∀q ∈R, |q| < 1=⇒ S = ∑nÊ0

qn = 1

Pour |q| < 1, notons T = ∑nÊ1

nqn−1 en supposant que cette écriture a un

sens.Calculer (1−q)T en fonction de S

Rappel

∀q ∈R, |q| < 1=⇒ S = ∑nÊ0

qn = 1

Rappel

∀q ∈R, |q| < 1=⇒ S = ∑nÊ0

qn = 1

Vision dynamique des probabilités - Automates Deuxième exemple - Valeur moyenne

Sommaire

Automates

Découverte

Markov

Départ

P PP PPP PPPP

F FF FFP FFPP

probabilité pi pour un état i d'être � absorbé � dans un sous-ensembleSB du bord ;

pi = 1 ;

pi = 0

pi =∑k∈S

pi =∑k∈Ei

pi = 1 ;

pi = 0

pi =∑k∈S

pi =∑k∈Ei

pi = 1 ;

pi = 0

pi =∑k∈S

pi =∑k∈Ei

pi = 1 ;

pi = 0

pi =∑k∈S

pi =∑k∈Ei

pi = 1 ;

pi = 0

pi =∑k∈S

pi =∑k∈Ei

y 1+y2 1

y 1+y2

1+y2 1

y 1+y2

1+y2 1

Durée moyenne

La valeur du délai d'absorption est égal à 1 augmenté de la moyennepondérée des délais d'absorption en les états voisins.

mi = 1+ ∑kÊ1

Durée moyenne

La valeur du délai d'absorption est égal à 1 augmenté de la moyennepondérée des délais d'absorption en les états voisins.

mi = 1+ ∑kÊ1

Xi =∑kÊ1

1ik(1+Yk)

Départ

P PP PPP PPPP

F FF FFP FFPP

Comportement asymptotique des chaînes de Markov

Sommaire

Automates

Découverte

Markov

matrice de transition

On notera x(k)i

la proportion de tra�quants qui se trouvent au matin dujour k dans la ville Vi .

Dé�nition 1 (Vecteur d'état)

On appelle vecteur d'état tout élément (x1, ...,xn) de Rn tel quex1+·· ·+xn = 1.

Ainsi, x (k) =(x(k)1 ,x

(k)2 ,x

)est un vecteur d'état (pourquoi ?).

Démontrez que :∀k ∈ �1,n�, x (k) = x (k−1) ·P

puis que :

∀k ∈ �1,n�, x (k) = x (0) ·Pk

On notera x(k)i

(k)2 ,x

puis que :

∀k ∈ �1,n�, x (k) = x (0) ·Pk

On notera x(k)i

(k)2 ,x

puis que :

∀k ∈ �1,n�, x (k) = x (0) ·Pk

Supposons que le chef de la ma�a locale dispose de 1000 tra�quants quipartent tous le matin du jour 0 de la ville de Zlot. Quelle sera la proportionde tra�quants dans chacune des villes au bout d'une semaine ? d'un an ?Il s'agit donc de calculer des puissances successives de P.On obtient les proportions au bout d'une semaine en calculant x (0) ·p7 avecx (0) = (1000,0,0).Nous allons utiliser SCILAB pour les longs calculs.

Dé�nition 2 (Matrice de transition régulière)

Une matrice de transition A est dite régulière si, et seulement si, il existe unentier naturel r tel que Ar a ses coe�cients tous strictement positifs.

Théorème 3 (Théorème des chaînes de Markov régulières)

Soit A une matrice régulière. Il existe une matrice stochastique :

A∞ =

a1 a2 · · · an

a1 a2 · · · an...

......

a1 a2 · · · an

telles que lim

n→+∞An =A∞.

De plus, v = (a1,a2, · · · ,an) est l'unique vecteur d'état stationnaire (tel que

v ·A= v).

Chaînes de Markov : une initiation pdf/markov_info1... · Chaînes de Markov : une initiation...

Documents

CHAÎNES DE MARKOV ANALYSE DE SÉQUENCES … · CHAÎNES DE MARKOV ANALYSE DE SÉQUENCES BIOLOGIQUES L3 Génie Biologique et Informatique – Second semestre 2012-2013 MIKAEL FALCONNET

2-Chaînes de Markov - bunnyup.free.frbunnyup.free.fr/4a/PS/ps-02-chaine de Markov.pdf · B.A. Ferrif 24/07/01 53 I-Introduction La structure de chaîne de Markov modélise un type

III – Convergence Asymptotique 1 – Chaînes de Markov 2 – Conditions de convergence

Le formalisme BDMP ( Boolean logic Driven Markov Process) · Modèles dynamiques ou comportementaux - graphes et chaînes de Markov - files d'attente - réseaux de Petri stochastiques

Chaînes de Markov et systèmes d’équations

Contrôle de chaînes de Markov - CERMICS – Centre d ...cermics.enpc.fr/~cohen-g/coursEDF/control_Markov.pdf · Cha^ nes de Markov Contr^ole de cha^ nes de Markov Annexe : Un exemple

Identification du nombre de composants dun mélange gaussien Sous la direction de Bernard Garel par chaînes de Markov à sauts réversibles dans le cas multivarié

Chaînes de Markov - math.u-psud.frmeliot/agreg/markov.pdf · Chapitre 2 Chaînes de Markov Résumé. Une chaîne de Markov est un processus aléatoire (Xn)n2N dont les transitions

Chaînes de Markov et files d'attente

Méthodes de Monte Carlo et Chaînes de Markov pour la simulation

les méthodes de Monte Carlo : exposé introductif · 2008. 12. 11. · Campillo, Rossi Méthodes de Monte Carlo. intro Monte Carlo MCMC chaînes Markov Metropolis-Hastings Gibbs

INTRODUCTION AUX CHAÎNES DE MARKOV€¦ · INTRODUCTION AUX CHAÎNES DE MARKOV L3 Génie Biologique et Informatique – Second semestre 2013-2014 MIKAEL FALCONNET mikael.falconnet@genopole.cnrs.fr

cours sur les chaînes de Markov

Processus stochastiques Chaînes de Markov Chaînes …pageperso.lif.univ-mrs.fr/~alexis.nasr/Ens/M17b/hmm.pdf · Un MMC est déﬁni par un quintuplet hS,A,π,T,Ei où : Eest la

Chaînes et arbres de Markov évidentiels avec … · Chaînes et arbres de Markov évidentiels avec applications à la segmentation des processus non stationnaires Evidential Markov

Chaînes de Markov cachées - univ-lille.frmath.univ-lille1.fr/~calgaro/TER_2018/wa_files/guilbaut... · 2018. 5. 26. · Université de Lille 1 Sciences et Technologies Master 1

Chaînes de Markov (et applications)w3.mi.parisdescartes.fr/~rlachiez/enseignement/markov/...Qest la matrice de transition de la chaîne X, on dit aussi noyau de transition quand E

Chaînes de Markov - IECL | Institut Élie Cartan de … · Plan 1 Déﬁnitionetexemples 2 PropriétésdeMarkov Tempsd’arrêt PropriétésdeMarkov 3 Classiﬁcationdesétats 4

Modèles stochastiques Chaînes de Markov discrètesferland/ift6575/contenu_cours/4_Mo... · Équations de Chapman-Kolmogorov équations de Chapman ns) | | , 0, , ... n-Kolmo onsécut

Processus de Markov et applications - paestel.fr · de Monte Carlo, le chapitre 2 sur les chaînes de Markov en temps discret à valeurs dans un ensemble ˝ni ou dØnombrable, et