Annee universitaire

Olivier Garet

Description

Niveau: Supérieur
Annee universitaire 2003-2004 UNIVERSITE D'ORLEANS Olivier GARET Chaınes de Markov et algorithmes stochastiques

• application au modele d'ising


• theoreme ergodique des chaınes de markov


• independantes de meme loi


• chaınes de markov


• variables aleatoires


• chaıne de markov de loi initiale


• matrices stochastiques


• algorithme de propp

Sujets

• Chaîne de Markov
• Variable aléatoire

Informations

• Publié par: profil-nechor-2012
• Nombre de lectures: 16

Extrait

Annee universitaire 2003-2004
UNIVERSITE D’ORLEANS
Olivier GARET
Cha^ nes de Markov et algorithmes stochastiques2Table des matieres
Table des matieres i
1 Cha^ nes de Markov 1
1.1 Dynamique markovienne . . . . . . . . . . . . . . . . . . . . . 1
1.2 Matrice stochastique . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.1 Existence des cha^ nes de Markov . . . . . . . . . . . . 3
1.2.2 Puissances des matrices stochastiques . . . . . . . . . . 3
1.3 Graphe associe a une matrice stochastique . . . . . . . . . . . 4
1.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2 Recurrence et mesures invariantes 11
2.1 Temps d’arr^et et propriete de Markov forte . . . . . . . . . . . 11
2.2 Classi cation des etats . . . . . . . . . . . . . . . . . . . . . . 12
2.3 Mesures invariantes . . . . . . . . . . . . . . . . . . . . . . . . 15
2.4 Theoreme de la probabilite stationnaire . . . . . . . . . . . . . 17
2.5 Theoreme ergodique des cha^ nes de Markov . . . . . . . . . . 20
2.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3 Quelques algorithmes stochastiques 25
3.1 Un algorithme de Metropolis . . . . . . . . . . . . . . . . . . . 25
3.1.1 Exemple : mesures de Gibbs associes a une interaction 27
Modele d’Ising en dimension d . . . . . . . . . . . . . . 28
3.2 Echantillonneur de Gibbs . . . . . . . . . . . . . . . . . . . . . 29
3.2.1 Application au modele d’Ising . . . . . . . . . . . . . . 30
3.3 Algorithme de Propp et Wilson . . . . . . . . . . . . . . . . . 30
3.3.1 Loi 0-1 pour l’algorithme de Propp et Wilson . . . . . 31
3.3.2 Algorithme de Propp et Wilson pour des dynamiques
monotones . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.3.3 mise en oeuvre . . . . . . . . . . . . . . . . . . . . . . 33
3.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
iii TABLE DES MATIERES
Index 36Chapitre 1
Cha^ nes de Markov
1.1 Dynamique markovienne
De nition: Soit S un ensemble ni ou denombrable, une mesure de pro-
babilite sur S et P = (p ) une matrice a coe cients positifs. Soiti;j (i;j)2SS
(X ) une suite de variables aleatoires de nies sur un espace ( ;F;P ).n n0
On dit que la suite (X ) est une cha^ ne de Markov de loi initiale et den n0
matrice de passageM si l’on a, pour tout entiern 1 et toute suitex ;:::x0 n
d’elements de S :
n 1Y
P (X =x ;X =x ;:::X =x ) =(x ) p :0 0 1 1 n n 0 x ;xi i+1
i=0
Exemple : une suite (X ) de variables aleatoires independantes den n0
m^eme loi a valeurs dans S denombrable est une cha^ ne de Markov. En
e et, il su t de poser pour ( i;j)2SS p =(j).i;j
Proprietes :
1. Si (X ) est une cha^ ne de Markov de matrice de passage M et quen n0
x ;:::;x sont tels que P (X =x ;X =x ;:::X =x ), alors0 n 1 0 0 1 1 n 1 n 1
P (X = x )jX = x ;X = x ;:::;X = x ) = p . Autre-n n 0 0 1 1 n 1 n 1 X ;xn 1 n
ment dit,
P (X =xjX ;:::;X ) =p : (1.1)n n 0 n 1 X ;xn 1 n
Cela signi e que toute l’information que X ;:::;X peuvent nous0 n 1
apporter sur X est comprise dans X .n n
2. (1.1) implique que P (X =xjX ) =pn n n 1 X ;xn 1 n
Qu’est ce concretement, qu’une cha^ ne de Markov ? On va voir que c’est
une suite de realisations, au cours du temps, des etats d’un systeme soumis a
des transformations aleatoires, la suites des transformations est une suite de
1^2 CHAPITRE 1. CHAINES DE MARKOV
transformations independantes, de m^eme loi. Evidemment, le resultat de la
transformation depend de la transformation choisie et de l’etat du systeme
avant la transformation.
Lemme 1. SoitS un ensemble ni ou denombrable, une loi surS et une
Smesure sur S =F(S;S).
Soit (f ) une suite de v.a.i.i.d. de loi etX une variable aleatoire den n1 0
loi independante de (f ) . On de nit (X ) parn n1 n n1
8n 0 X =f (X )n+1 n+1 n
Alors (X ) est une cha^ ne de Markov de loi initiale et de matrice den n0
transition M, ou M est de nie par
S8(i;j)2SS m =(ff2S ;f(i) =jg):i;j
f0;:::;ngDemonstration. Soit AS .
P (f(X ;:::;X )2Ag\fX =ig\fX =jg)0 n n n+1
= P (f(X ;:::;X )2Ag\fX =ig\ff (i) =jg)0 n n n+1
= P (f(X ;:::;X )2Ag\fX =ig)P (f (i) =j)0 n n n+1
= P (f(X ;:::;X )2Ag\fX =ig)P (f 2S:::fjg:::S)0 n n n+1
= P (f(X ;:::;X )2Ag\fX =ig)(S:::fjg:::S)0 n n
= P (f(X ;:::;X )2Ag\fX =ig)m0 n n i;j
Exemple : la marche de l’ivrogne (ou marche aleatoire surZ)
Un ivrogne sort du cafe passablement emeche. A chaque pas, il prend une
decision (en n, si tant est que cela lui soit possible...) : aller a gauche, ou
aller a droite. Si on repere par X sa position dans la rue au temps n, on an
S =Z,X =f (X ), ouf est une suite de translations independantes :n+1 n+1 n n
P (f = (x7!x + 1)) =P (f = (x7!x 1)) = 1=2.n n
Comme on va le voir, ce procede permet de fabriquer toutes les cha^ nes
de Markov.
1.2 Matrice stochastique
De nition: Soit S un ensemble denombrable et P = (p ) une ma-i;j (i;j)2SS
trice a coe cients positifs. On dit que P est une matrice stochastique si on
a X
8i2S p = 1:i;j
j2S1.2. MATRICE STOCHASTIQUE 3
1.2.1 Existence des cha^ nes de Markov
Theoreme 1. Soit S un ensemble denombrable, P = (p ) unei;j (i;j)2SS
matrice stochastique et une mesure de probabilite sur S. Alors, on peut
construire une cha^ ne de Markov de loi initiale et de matrice de passage
P .
SDemonstration. De nissons une mesure sur S parP

= ;P i
i2S
ou est la mesure sur S de nie par (j) = p . Alors veri e (Si i i;j P P
:::fjg:::S) =p et il su t d’appliquer le lemme precedent.i;j
Lorsque la matrice P est xee, on note souvent P une probabilite sous
laquelle (X ) est une cha^ ne de Markov de matrice de transition P telle quen n0
la loi deX sousP est. De m^eme, on noteE l’esperance correspondante.0
Dans le cas ou la loi initiale est une masse de Dirac, on ecrit simplementPi
(resp.E ) au lieu deP (resp.E ).i i i
1.2.2 Puissances des matrices stochastiques
Theoreme 2. Soit (X ) une cha^ ne de Markov de matrice de transition Pn
et de loi initiale P = . Alors, la loi de la cha^ ne au temps n s’ecritX n0
n =P , ou on a ecrit et comme des vecteurs lignes.n n
Demonstration. Il su t de montrer que = P , puis proceder parn+1 n
recurrence sur n. D’apres le principe de partition, on a
(j) = P (X =j)n+1 n+1
X
= P (X =i;X =j) n n+1
i2S
X
= P (X =i; )p n i;j
i2S
X
= (i)pn i;j
i2S
= ( M)(j)n^4 CHAPITRE 1. CHAINES DE MARKOV
1.3 Graphe associe a une matrice stochas-
tique
Soit P = (p ) une matrice stochastique. On peut associer a lai;j (i;j)2SS
matrice P (ou aux cha^ nes de Markov correspondantes) un graphe oriente
G = (S;A) avec
A =f(x;y)2SS;p > 0g:i;j
Considerons une cha^ ne de Markov associee a la matrice stochastique P avec
la condition initiale deterministe x , autrement dit = et notonsP la0 x x0 0
mesure de probabilite correspondante Alors, comme
n 1Y
P (X =x ;X =x ;:::;X =x ) = p ;x 0 0 1 1 n n x ;x0 i i+1
i=0
il est clair queP (X =x ;X =x ;:::;X =x ) est non nul si et seulementx 0 0 1 1 n n0
si (x ;x ;:::;x ) constitue un chemin dans le graphe G.0 1 n
D’apres le principe de partition, on a pour une cha^ ne de Markov avec
une loi initiale
X
P ()(X =x ;X =x ) = P (X =x ;X =X ;:::X =x ;X =x ):1 1 n n i 0 0 2 2 n 1 n 1 n n
n(x ;:::x )2S0 n 1
(1.2)
(n)
En particulier, si l’on pose p =P (X =j), on ai ni;j
X
(n)
p = P (X =x ;X =X ;:::X =x ;X =j):i 1 1 2 2 n 1 n 1 ni;j
n 1x2S
(n)
Donc p > 0, autrement dit il est possible d’aller en n etapes de l’etat i ai;j
l’etat j si et seulement si on peut trouver dans le graphe G un chemin de
longueur n allant de i a j.
On en deduit que
[P (9n> 0X =j) =P ( fX =jg);i n i n
i1
qui represente la probabilte que, partant de i, on puisse arriver a j, est non
nulle si et seulement si il existe dans le graphe G un chemin allant de i a j.
Si il y a a la fois un chemin de i vers j et un chemin de j vers i, on dit
que les etats i et j communiquent et on ecrit i$j. 1.3. GRAPHE ASSOCIE A UNE MATRICE STOCHASTIQUE 5
Si tous les etats communiquent, on dit que la cha^ ne de Markov est
irreductible.
On appelle periode d’un etat x d’une cha^ ne de Markov et on note d(x)
le pgcd (plus grand commun diviseur) des longueurs des circuits du graphe
G contenant x. Lorsque la periode est 1, on dit que l’etat x est aperiodique.
Lemme 2. Si deux etats communiquent, alors ils ont m^eme periode.
0Demonstration. Soient i;j avec i$ j. Soit un chemin de i a j, un
chemin dej ai. SoitC un circuit quelconque (eventuellement vide) contenant
0 0j . et C sont deux circuits contenant i. Donc d(i) divise leurs
longueurs ainsi que la di erence de leurs longueurs, soit la longueur de C.
Ainsi d(i) divise les longueurs de tous les circuits contenant j, donc divise
leur pgcd, soit d(j). De la m^eme maniere, on montre que d(j) divise d(i),
d’ou d(i) =d(j).
De nition: Si une cha^ ne irreductible a ses etats de periode 1, on dit qu’elle
est aperiodique.
Les lemme suivant se revelera tres utile par la suite
Lemme 3. Soit x un etat de periode 1. Il existe un entier N(x) tel que pour
tout nN(x) le graphe associe a la cha^ ne de Markov possede un circuit de
longueur n contenant x
SoitA l’ensemble des valeurs den telles que le graphe associe a la cha^ ne
de Markov possede un circuit de longueur n contenant x. Il est clair que