Simulation des chaînes de Markov

Ana Busic

Description

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

Sujets

• Chaîne de Markov

Informations

• Publié par: profil-infoe-2012
• Publié le: 01 février 2011
• Nombre de lectures: 84
• Langue: Français

Extrait

Simulation des chaînes de Markov

Ana Bušić

INRIA - ENS

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

[e-mail]

Master COSY - UVSQ

Versailles, février 2011

Système à événements discrets

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

I Xest unespace d’étatsfini.

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

I Aest unensemble d’événementsfini.

I pest une mesure de probabilité surA: p a >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 ×A n → X,n∈N.

def Soita 1→n =a 1 . . .a n dansA n :

def (x,a 1→n )7→x∙a 1→n =x∙a 1 ∙a 2 ∙. .∙a . n .

Évolution du système

Surnétapes : 1.On choisi

1.On choisit l’état initialX 0 selon la distributionπ 0 . 2.Pouri=1ànfaire : I Choisir un événementa i ∈Aselonp I X i :=X i−1 ∙a i =X 0 ∙a 1→n

Exemple :

a a

b

a

a,b

b

b

Soitp a =1/3,p b =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. . ..

existeunitionPildetearsnteamrtci 1)t(as.Pér)vanifiA, 0 π∙,p,A DES ,X(= avecnSEDsteulexiN=i,|i|X eu S .nuqi

P x,y = X p a . a∈A:x∙a=y

pour toutx,ydansX,

I Soient{a n } n∈N une suitei.i.d.d’événements deAdistribués selonpetX 0 distribué selonπ 0 . I Alors{X n d = ef X 0 ∙a 1→n } n∈N est 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é 2 Nsulpua îaenethckrvoedaMplusDertou,pou ni noitub 0 πelaiti ecaviefinristdila

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

I Soient{a n } n∈N une suitei.i.d.d’événements deAdistribués selonpetX 0 distribué selonπ 0 . I Alors{X n d = ef X 0 ∙a 1→n } n∈N est une chaîne de Markov avec la matrice de transitionP:

pour toutx,ydansX,P x,y = X p a . a∈A:x∙a=y

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

(1)

SiX||=N,lixesietnuSEDavecualpusN 2 véénements.