//img.uscri.be/pth/c96118cc7794f862a11cb55584861a5e1b1adbb2
Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Simulation des chaînes de Markov

De
69 pages
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 plus Voir moins
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: πx00est 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énementaA.
Iest 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→xa.
Fonction de transition
Extension aux séquences (mots) d’événements fini :
:X ×An→ X,nN.
def Soita1n=a1. . .andansAn:
def (x,a1n)7→xa1n=xa1a2. .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énementaiAselonp IXi:=Xi1ai=X0a1n
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 : 13324133− ∙ ∙ ∙ en partant de l’état1et pour la séquence d’événements bbababb. . ..
existeunitionPildetearsnteamrtci1)t(as.Pér)vaniA,0π,p,ADES,X(=avecnSEDsteulexiN=i,|i|XeuS.nuqi
Px,y=Xpa. aA:xa=y
pour toutx,ydansX,
ISoient{an}nNune suitei.i.d.d’événements deAdistribués selonpetX0distribué selonπ0. IAlors{Xnd=efX0a1n}nNest 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πelaitiecavienristdila
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}nNune suitei.i.d.d’événements deAdistribués selonpetX0distribué selonπ0. IAlors{Xnd=efX0a1n}nNest une chaîne de Markov avec la matrice de transitionP:
pour toutx,ydansX,Px,y=Xpa. aA:xa=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.