6.1 ´
El´ ements d’analyse asymptotique
157
2
3
1
1/4
1/4
1/2
1/2
1/3
1/3
1/4
1
2
2/3
3/4
1/3
1/4
1/3
1/4
Fig. 6.3. Chaˆ ınes r´ eversibles
Exercice 6.1.5 On munit l’ensemble E = {0, 1}
d , avec d ≥ 1, de la distance
de Hamming
d(x, y) =
n
i=1
(1 − 1 x i (y
i ))
On note V(x) = {y ∈ E : d(x, y) ≤ 1}, l’ensemble des d-uplets ne diff´ erant
de x que de, au plus, une seule coordonn´ ee. On consid` ere la transition de
probabilit´ es
M (x, y) =
1
|V(x)|
1 V(x) (y) =
1
d + 1
1 V(x) (y)
V´ erifier que pour tout couple de points (x, y) ∈ E
2 , on a M
d (x, y) ≥ 1/(d+1)
d .
En d´ eduire que la mesure uniforme η ∞ (x) = 2
−d sur E est l’unique mesure
invariante de M .
Exercice 6.1.6 (Exploration d’un graphe fini) Soit E = (I, V (I)) un
graphe fini sym´ etrique et connexe. Plus pr´ ecis´ ement l’ensemble des sommets
I est un ensemble fini, et l’ensemble des arˆ etes V (I) est une partie de (I × I)
telle que (x, y) ∈ V (I) ⇐⇒ (y, x) ∈ V (I) (dans ce cas, on identifie les arˆ etes
(x, y) = (y, x)). D’autre part, la propri´ et´ e de connexit´ e exprime le fait suivant.
Pour tous x, y ∈ I, il existe un chemin (x p ) 0≤p≤n d’une certaine longueur
n ≥ 1 tel que x 0 = x, x n = y, et (x p , x p+1 ) ∈ V (I), pour tout 0 ≤ p < n. On
associe `
a chaque point x ∈ E, un voisinage
V(x) = {y ∈ E : (x, y) ∈ V (I)} .
On note |V(x)| le cardinal de l’ensemble V(x), et |V (I)| le cardinal de l’ensemble de toutes les arˆ etes. La figure 6.4 repr´ esente un exemple de graphe
fini sym´ etrique et connexe, avec I = {1, . . . , 7}, |V (I)| = 7, |V(1)| = 1,
|V(2)| = |V(3)| = |V(4)| = 2, |V(5)| = 3, et |V(6)| = |V(7)| = 2
1. V´ erifier que (x ∈ V(y)) ⇔ (y ∈ V(x)), et montrer que 2|V (I)| =
x∈I |V(x)|. En d´ eduire que la mesure η ∞ (x) =
|V(x)|
2|V (I)| , est bien une
mesure de probabilit´ e sur E.
2. Soit M (x, y) la transition de probabilit´ es de la marche al´ eatoire simple sur
E donn´ ee par
El´ ements d’analyse asymptotique
157
2
3
1
1/4
1/4
1/2
1/2
1/3
1/3
1/4
1
2
2/3
3/4
1/3
1/4
1/3
1/4
Fig. 6.3. Chaˆ ınes r´ eversibles
Exercice 6.1.5 On munit l’ensemble E = {0, 1}
d , avec d ≥ 1, de la distance
de Hamming
d(x, y) =
n
i=1
(1 − 1 x i (y
i ))
On note V(x) = {y ∈ E : d(x, y) ≤ 1}, l’ensemble des d-uplets ne diff´ erant
de x que de, au plus, une seule coordonn´ ee. On consid` ere la transition de
probabilit´ es
M (x, y) =
1
|V(x)|
1 V(x) (y) =
1
d + 1
1 V(x) (y)
V´ erifier que pour tout couple de points (x, y) ∈ E
2 , on a M
d (x, y) ≥ 1/(d+1)
d .
En d´ eduire que la mesure uniforme η ∞ (x) = 2
−d sur E est l’unique mesure
invariante de M .
Exercice 6.1.6 (Exploration d’un graphe fini) Soit E = (I, V (I)) un
graphe fini sym´ etrique et connexe. Plus pr´ ecis´ ement l’ensemble des sommets
I est un ensemble fini, et l’ensemble des arˆ etes V (I) est une partie de (I × I)
telle que (x, y) ∈ V (I) ⇐⇒ (y, x) ∈ V (I) (dans ce cas, on identifie les arˆ etes
(x, y) = (y, x)). D’autre part, la propri´ et´ e de connexit´ e exprime le fait suivant.
Pour tous x, y ∈ I, il existe un chemin (x p ) 0≤p≤n d’une certaine longueur
n ≥ 1 tel que x 0 = x, x n = y, et (x p , x p+1 ) ∈ V (I), pour tout 0 ≤ p < n. On
associe `
a chaque point x ∈ E, un voisinage
V(x) = {y ∈ E : (x, y) ∈ V (I)} .
On note |V(x)| le cardinal de l’ensemble V(x), et |V (I)| le cardinal de l’ensemble de toutes les arˆ etes. La figure 6.4 repr´ esente un exemple de graphe
fini sym´ etrique et connexe, avec I = {1, . . . , 7}, |V (I)| = 7, |V(1)| = 1,
|V(2)| = |V(3)| = |V(4)| = 2, |V(5)| = 3, et |V(6)| = |V(7)| = 2
1. V´ erifier que (x ∈ V(y)) ⇔ (y ∈ V(x)), et montrer que 2|V (I)| =
x∈I |V(x)|. En d´ eduire que la mesure η ∞ (x) =
|V(x)|
2|V (I)| , est bien une
mesure de probabilit´ e sur E.
2. Soit M (x, y) la transition de probabilit´ es de la marche al´ eatoire simple sur
E donn´ ee par