Simulation des chaînes de Markov
69
pages
Français
Documents
2011
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe en t'inscrivant gratuitement
Découvre YouScribe en t'inscrivant gratuitement
69
pages
Français
Documents
2011
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Niveau: Supérieur, Master
Simulation des chaînes de Markov Ana Bu?i? INRIA - ENS Master COSY - UVSQ Versailles, février 2011
Voir
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
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’étatsfini.
Iπ0est unedistribution initiale: πx0≥0est la probabilité que le système soit dans l’étatx∈ X à l’instant0.
IAest unensemble d’événementsfini.
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 fini :
∙: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
b
a
a,b
b
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. . ..
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πelaitiecaviefinristdila
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 finie avec la distribution initialeπ0et matrice de transitionPil existe un SED A= (X, π0,A,p,∙)vérifiant (1).Pas unique.
(1)
SiX||=N,lixesietnuSEDavecualpusN2véénements.
