[PDF] [PDF] Chaˆ?nes de Markov – reversibilité - DI ENS

View - Download [PDF] Chaˆ?nes de Markov – reversibilité - DI ENS

Previous PDF

Next PDF

Modeles et algorithmes de reseaux

Cha^nes de Markov { reversibilite

Ana Busic

Inria Paris - DI ENS

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

Paris, Octobre 2018

Cha^nes de Markov reversibles

SoitfXtgt0une cha^ne de Markov avec l'espace d'etats S=fs1;:::;snget la matrice de transitionP. Une distribution de probabilitessurSest dite reversible si pour touti;j2 f1;:::;ng, iPi;j=jPj;i:Theorem Siest une distribution reversible, alors elle est aussi une distribution stationnaire.Demonstration.

Pour toutj2 f1;:::;ng, on a

j=jn X i=1P j;i=nX i=1 jPj;i=nX i=1 iPi;j:

Cha^nes de Markov reversibles

SoitfXtgt0une cha^ne de Markov avec l'espace d'etats S=fs1;:::;snget la matrice de transitionP. Une distribution de probabilitessurSest dite reversible si pour touti;j2 f1;:::;ng, iPi;j=jPj;i:Theorem Siest une distribution reversible, alors elle est aussi une distribution stationnaire.Demonstration.

Pour toutj2 f1;:::;ng, on a

j=jn X i=1P j;i=nX i=1 jPj;i=nX i=1 iPi;j:

Cha^nes de Markov reversibles

SoitfXtgt0une cha^ne de Markov avec l'espace d'etats S=fs1;:::;snget la matrice de transitionP. Une distribution de probabilitessurSest dite reversible si pour touti;j2 f1;:::;ng, iPi;j=jPj;i:Theorem Siest une distribution reversible, alors elle est aussi une distribution stationnaire.Demonstration.

Pour toutj2 f1;:::;ng, on a

j=jn X i=1P j;i=nX i=1 jPj;i=nX i=1 iPi;j:

Temps inverse

Theorem

SoitfXtgt0une cha^ne de Markov avec l'espace d'etatsSet la matrice de transitionPet la distribution stationnairereversible.

SiX0, alors pour toutk2Net toussi0;si1;:::;sik2S,

P(X0=si0;X1=:::;Xk=sik) =P(X0=sik;X1=sik1;:::;Xk=si0):La probabilite d'un chemin dans un sens est egale a la probabilite du

m^eme chemin dans le sens inverse.

Exemple : processus de naissance et de mort

Matrice de transitionPtelle que :

I

Pi;j>0 sijijj= 1,

I

Pi;j= 0 sijijj 2.

Notons par

i=Q i1 k=1Pk;k+1Q i1 k=1Pk+1;k:

Alors,

= (1;:::;n) = (1;:::;n)=(nX i=1 i) est une distribution de probabilites reversible.

Exemple : marche aleatoire sur un graphe

Un grapheG= (V;E) avec les sommetsV=fv1;:::;vnget les ar^etes

E=fe1;:::;emg. Soitdile degre du sommetvi.Un marcheur qui est au sommetvia l'instanttchange sa position pour

un sommet voisin deviavec la m^eme probabilite pour tous les voisins.Matrice de transitionP: P i;j= 1=di;si(vi;vj)2E et sinonPi;j= 0.Alors, = (d1;:::;dn)=(nX i=1d i) est une distribution de probabilites reversible.

Exemple : marche aleatoire sur un graphe

Un grapheG= (V;E) avec les sommetsV=fv1;:::;vnget les ar^etes

E=fe1;:::;emg. Soitdile degre du sommetvi.Un marcheur qui est au sommetvia l'instanttchange sa position pour

un sommet voisin deviavec la m^eme probabilite pour tous les voisins.Matrice de transitionP: P i;j= 1=di;si(vi;vj)2E et sinonPi;j= 0.Alors, = (d1;:::;dn)=(nX i=1d i) est une distribution de probabilites reversible.

Exemple : marche aleatoire sur un graphe

Un grapheG= (V;E) avec les sommetsV=fv1;:::;vnget les ar^etes

E=fe1;:::;emg. Soitdile degre du sommetvi.Un marcheur qui est au sommetvia l'instanttchange sa position pour

un sommet voisin deviavec la m^eme probabilite pour tous les voisins.Matrice de transitionP: P i;j= 1=di;si(vi;vj)2E et sinonPi;j= 0.Alors, = (d1;:::;dn)=(nX i=1d i) est une distribution de probabilites reversible.

Exemple : marche aleatoire sur un graphe

Un grapheG= (V;E) avec les sommetsV=fv1;:::;vnget les ar^etes

E=fe1;:::;emg. Soitdile degre du sommetvi.Un marcheur qui est au sommetvia l'instanttchange sa position pour

un sommet voisin deviavec la m^eme probabilite pour tous les voisins.Matrice de transitionP: P i;j= 1=di;si(vi;vj)2E et sinonPi;j= 0.Alors, = (d1;:::;dn)=(nX i=1d i) est une distribution de probabilites reversible.

Processus en temps retourne

Processus en temps retourne

SoitfXtgun processus stationnaire et irreductible. On construitfXtgen inversant le temps : X t=XtRemarque :n'est pas important, il determine uniquement l'origine pour le processus retourne.

Applications

I Permet de mieux comprendre les proprietes d'un processus. I Le processus de departs des les plus facile a analyser. Les preuves plus elegantes. I Parfois plus facile de "deviner" la forme de la loi stationnaire.

Processus en temps retourne

En general,fXtgest dierent defXtg.

Exemple :

p rocessuscyclique. Loi stationnaire Thm. Supp oseque fXtga la distribution stationnaire,i=P(Xt=i).

AlorsfXtga aussi une loi stationnaireet

=Preuve.ietirepresentent les proportions de temps quefXtgetfXtg passent en etati. Cette proportion ne depend pas de la direction du temps.

Processus en temps retourne

En general,fXtgest dierent defXtg.

Exemple :

p rocessuscyclique. Loi stationnaire Thm. Supp oseque fXtga la distribution stationnaire,i=P(Xt=i).

AlorsfXtga aussi une loi stationnaireet

=Preuve.ietirepresentent les proportions de temps quefXtgetfXtg passent en etati. Cette proportion ne depend pas de la direction du temps.

Processus en temps retourne

En general,fXtgest dierent defXtg.

Exemple :

p rocessuscyclique. Loi stationnaire Thm. Supp oseque fXtga la distribution stationnaire,i=P(Xt=i).

AlorsfXtga aussi une loi stationnaireet

=Preuve.ietirepresentent les proportions de temps quefXtgetfXtg passent en etati. Cette proportion ne depend pas de la direction du temps.

Temps discret

Prop. Le p rocessusretourn e:::;Xn+1;Xn;Xn1;:::d'une cha^ne de Markov stationnaire en temps discret:::;Xn1;Xn;Xn+1;:::est aussi une cha^ne de Markov stationnaire.

Les probabilites de transitions sont

P i;j=P(Xn=jjXn+1=i) =jPj;i i:

Processus reversible

Def.

Si les p rocessusfXngetfXngsont statistiquement

non-distinguables, on dit quefXngestr eversible(en temps). (Xt1;Xt2;:::;Xtn)(Xt1;Xt2;:::;Xtn) pour toutn,ett1;:::;tn. Intuitivement : un spectateur ne peut pas dire si le "lm" est projete en avant ou en arriere.

CMH reversible

p i;j=pi;j;8i;j, i.e.ipi;j=jpj;i;8i;j

Equations de balance detaillee :

les ots de p robabiliteentre deux etats sont en equilibre.I

Balance detaillee)balance globale

I Si les conditions de balance detaillee sont veriees pour un vecteur positif et tel queP ii<1, alorsnormalise tel queP ii= 1 est la loi stationnaire. I Mais balance globale6)balance detaillee (tous les processus de

Markov ne sont pas reversibles).

Exemple : les arbres sont reversibles

Prop. Si une CMH est reversible, alo rsson graphe de tra nsitionest symetrique.Prop.Si le graphe de tra nsitionnon-o riented'une CMH est un a rbre, alors le processus reversible.Preuve.En utilisant la propriete suivante (en exercice) Pour une CMH avec espace d'etatsS, les equations d'equilibre global (P=) sont equivalentes a : 8IS;P i2IP j62IiPi;j=P i2IP j62IjPj;i:Cor.T ousles CMH de naissance et de mo rtsont r eversibles.

Exemple : les arbres sont reversibles

Prop. Si une CMH est reversible, alo rsson graphe de tra nsitionest symetrique.Prop.Si le graphe de tra nsitionnon-o riented'une CMH est un a rbre, alors le processus reversible.Preuve.En utilisant la propriete suivante (en exercice) Pour une CMH avec espace d'etatsS, les equations d'equilibre global (P=) sont equivalentes a : 8IS;P i2IP j62IiPi;j=P i2IP j62IjPj;i:Cor.T ousles CMH de naissance et de mo rtsont r eversibles.

Exemple : les arbres sont reversibles

Prop. Si une CMH est reversible, alo rsson graphe de tra nsitionest symetrique.Prop.Si le graphe de tra nsitionnon-o riented'une CMH est un a rbre, alors le processus reversible.Preuve.En utilisant la propriete suivante (en exercice) Pour une CMH avec espace d'etatsS, les equations d'equilibre global (P=) sont equivalentes a : 8IS;P i2IP j62IiPi;j=P i2IP j62IjPj;i:Cor.T ousles CMH de naissance et de mo rtsont r eversibles.

Exemple : les arbres sont reversibles

Prop. Si une CMH est reversible, alo rsson graphe de tra nsitionest symetrique.Prop.Si le graphe de tra nsitionnon-o riented'une CMH est un a rbre, alors le processus reversible.Preuve.En utilisant la propriete suivante (en exercice) Pour une CMH avec espace d'etatsS, les equations d'equilibre global (P=) sont equivalentes a : 8IS;P i2IP j62IiPi;j=P i2IP j62IjPj;i:Cor.T ousles CMH de naissance et de mo rtsont r eversibles.quotesdbs_dbs29.pdfusesText_35

[PDF] chaine de markov récurrente

[PDF] chaine de markov exemple

[PDF] chaine de markov irreductible exemple

[PDF] chaine de markov exercice corrigé

[PDF] chaine énergétique barrage hydraulique

[PDF] chaine énergétique d'une éolienne

[PDF] exercice corrigé centrale hydraulique

[PDF] chaine énergétique centrale thermique

[PDF] chaine énergétique pile

[PDF] chaine énergétique exercices

[PDF] chaine énergétique éolienne

[PDF] chaine énergétique panneau solaire

[PDF] chaine energetique definition

[PDF] chaine énergétique exemple

[PDF] cours de logistique de distribution pdf