150
6 M´ ethodes de Monte Carlo par chaˆ ınes de Markov (MCMC)
– Montrer que pour toute fonction born´ ee f sur E, nous avons
E
(η
n (f ) − η(f ))
2
=
1
n
η([f − η(f )]
2 )
– V´ erifier l’in´ egalit´ e de Markov
P(Y > a) ≤ E(Y )/a
valable pour toute variable r´ eelle positive Y , et pour tout nombre a > 0.
En d´ eduire que l’on a, pour toute marge d’erreur > 0, et pour toute
fonction born´ ee f sur E
P(|η
n (f ) − η(f )| > >) ≤
1
n n 2 η([f − η(f )]
2 )
Nous terminerons cette discussion par une illustration imag´ ee de la loi des
grands nombres. Nous allons supposer que les variables al´ eatoires (X n ) n≥1
repr´ esentent les visites al´ eatoires des pixels d’une image. Rappelons qu’un
pixel correspond `
a un petit domaine du plan. On effectue un grand nombre
d’it´ erations, et on note le nombre de fois que chaque pixel a ´ et´ e visit´ e. On
colorie ensuite chaque pixel par des niveaux de gris proportionnels au nombre
de fois que le pixel a ´ et´ e visit´ e. On obient ainsi une image en noir et blanc.
Les r´ egions plus ou moins grises correspondent ` a des fr´ equences empiriques de
visite des pixels plus ou moins grandes. Lorsque les v.a. sont i.i.d. de mˆ eme loi
η, la loi des grands nombres nous permet d’interpr´ eter les diff´ erents niveaux
de gris d’une partie A de l’image en terme de la mesure η
1
n
n
p=1
1 A (X p ) → n→∞ η(1 A ) =
R 2
1 A (x) η(dx) = η(A) ∈ [0, 1]
Le niveau de gris d’une r´ egion A peut ainsi s’interpr´ eter comme la probabilit´ e
de visite de A. Il y a donc en ce sens, une correspondance exacte entre l’image
color´ ee et la mesure de probabilit´ e η.
6.1.2 Le th´ eor` eme ergodique
Le th´ eor` eme ergodique est l’extension de la loi des grands nombres ` a
des chaˆ ınes de Markov (X n ) n≥0 homog` enes et suffisamment r´ eguli` eres. Commen¸ cons par un ´ enonc´ e assez vague de ce th´ eor` eme :
Lorsque la chaˆ ıne de Markov (X n ) n≥0 est homog` ene et suffisamment
m´ elangeante sur un espace d’´ etat E, il existe une mesure de probabilit´ e
η telle que
Loi(X n ) −→ η et
1
n
n
p=1
δ Xp −→ η
6 M´ ethodes de Monte Carlo par chaˆ ınes de Markov (MCMC)
– Montrer que pour toute fonction born´ ee f sur E, nous avons
E
(η
n (f ) − η(f ))
2
=
1
n
η([f − η(f )]
2 )
– V´ erifier l’in´ egalit´ e de Markov
P(Y > a) ≤ E(Y )/a
valable pour toute variable r´ eelle positive Y , et pour tout nombre a > 0.
En d´ eduire que l’on a, pour toute marge d’erreur > 0, et pour toute
fonction born´ ee f sur E
P(|η
n (f ) − η(f )| > >) ≤
1
n n 2 η([f − η(f )]
2 )
Nous terminerons cette discussion par une illustration imag´ ee de la loi des
grands nombres. Nous allons supposer que les variables al´ eatoires (X n ) n≥1
repr´ esentent les visites al´ eatoires des pixels d’une image. Rappelons qu’un
pixel correspond `
a un petit domaine du plan. On effectue un grand nombre
d’it´ erations, et on note le nombre de fois que chaque pixel a ´ et´ e visit´ e. On
colorie ensuite chaque pixel par des niveaux de gris proportionnels au nombre
de fois que le pixel a ´ et´ e visit´ e. On obient ainsi une image en noir et blanc.
Les r´ egions plus ou moins grises correspondent ` a des fr´ equences empiriques de
visite des pixels plus ou moins grandes. Lorsque les v.a. sont i.i.d. de mˆ eme loi
η, la loi des grands nombres nous permet d’interpr´ eter les diff´ erents niveaux
de gris d’une partie A de l’image en terme de la mesure η
1
n
n
p=1
1 A (X p ) → n→∞ η(1 A ) =
R 2
1 A (x) η(dx) = η(A) ∈ [0, 1]
Le niveau de gris d’une r´ egion A peut ainsi s’interpr´ eter comme la probabilit´ e
de visite de A. Il y a donc en ce sens, une correspondance exacte entre l’image
color´ ee et la mesure de probabilit´ e η.
6.1.2 Le th´ eor` eme ergodique
Le th´ eor` eme ergodique est l’extension de la loi des grands nombres ` a
des chaˆ ınes de Markov (X n ) n≥0 homog` enes et suffisamment r´ eguli` eres. Commen¸ cons par un ´ enonc´ e assez vague de ce th´ eor` eme :
Lorsque la chaˆ ıne de Markov (X n ) n≥0 est homog` ene et suffisamment
m´ elangeante sur un espace d’´ etat E, il existe une mesure de probabilit´ e
η telle que
Loi(X n ) −→ η et
1
n
n
p=1
δ Xp −→ η