Simulation des chaînes de Markov

pages

Français

Documents

2011

Écrit par
Ana Busic

Publié par
profil-infoe-2012

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

pages

Français

Ebook

2011

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

profil-infoe-2012

Publié le

01 février 2011

Nombre de lectures

Langue

Français

Niveau: Supérieur, Master
Simulation des chaînes de Markov Ana Bu?i? INRIA - ENS Master COSY - UVSQ Versailles, février 2011

x0 ·

temps discret

extension aux séquences

n2 événements

chaîne de markov

simulation des chaînes de markov

x0 selon la distribution pi0

Voir

Publié par

profil-infoe-2012

Publié le

01 février 2011

Nombre de lectures

Langue

Français

Chaîne de Markov

Simulation des chaînes de Markov

Ana Bušić

INRIA - ENS

http://www.di.ens.fr/~busic/

ana.busic@inria.fr

Master COSY - UVSQ

Versailles, février 2011

Système à événements discrets

SED :(X, π0,A,p,∙)

IXest unespace d’étatsﬁni.

Iπ0est unedistribution initiale: πx0≥0est la probabilité que le système soit dans l’étatx∈ X à l’instant0.

IAest unensemble d’événementsﬁni.

Ipest une mesure de probabilité surA: pa>0est laprobabilité de l’événementa∈A.

I∙est un opérateur qui décrit l’action des événements dansA sur les états dansX-fonction de transition:

∙:X ×A→ X,(x,a)7→x∙a.

Fonction de transition

Extension aux séquences (mots) d’événements ﬁni :

∙:X ×An→ X,n∈N.

def Soita1→n=a1. . .andansAn:

def (x,a1→n)7→x∙a1→n=x∙a1∙a2∙. .∙a .n.

Évolution du système

Surnétapes : 1.On choisi

1.On choisit l’état initialX0selon la distributionπ0. 2.Pouri=1ànfaire : IChoisir un événementai∈Aselonp IXi:=Xi−1∙ai=X0∙a1→n

Exemple :

a a

a,b

Soitpa=1/3,pb=2/3, et π0= (1/4,1/4,1/4,1/4).

Unetrajectoirepossible : 1−3−3−2−4−1−3−3− ∙ ∙ ∙ en partant de l’état1et pour la séquence d’événements bbababb. . ..

existeunitionPildetearsnteamrtci1)t(as.Pér)vaniﬁA,0π∙,p,ADES,X(=avecnSEDsteulexiN=i,|i|XeuS.nuqi

Px,y=Xpa. a∈A:x∙a=y

pour toutx,ydansX,

ISoient{an}n∈Nune suitei.i.d.d’événements deAdistribués selonpetX0distribué selonπ0. IAlors{Xnd=efX0∙a1→n}n∈Nest une chaîne de Markov avec la matrice de transitionP:

(1)

SED vs. chaîne de Markov

UnSEDA= (X, π0,A,p,∙)induit unechaîne de Markov (en temps discret homogène) :chaîne de Markov

.tsnemenévé2NsulpuaîaenethckrvoedaMplusDertou,pouninoitub0πelaitiecavieﬁnristdila

SED vs. chaîne de Markov

0 UnSEDA= (X ,, πA,p,∙)induit unechaîne de Markov (en temps discret homogène) :chaîne de Markov

ISoient{an}n∈Nune suitei.i.d.d’événements deAdistribués selonpetX0distribué selonπ0. IAlors{Xnd=efX0∙a1→n}n∈Nest une chaîne de Markov avec la matrice de transitionP:

pour toutx,ydansX,Px,y=Xpa. a∈A:x∙a=y

De plus, pour toute chaîne de Markov ﬁnie avec la distribution initialeπ0et matrice de transitionPil existe un SED A= (X, π0,A,p,∙)vériﬁant (1).Pas unique.

(1)