Chaînes de Markov : Devoir maison 2016-2017

Exercice 1 : Processus de Bessel discret.

Soit (An )n∈N une suite de variables indépendantes de loi P[An = 1] = P[An = −1] = 12 ;
et Xn = A1 + A2 + · · · + An . On rappelle que la marche aléatoire (Xn )n∈N est une chaîne
de Markov sur Z, qui est irréductible récurrente nulle ; on pourra réutiliser ce fait sans
démonstration. On note

Sn = max{Xk , k ∈ [[0, n]]};

Wn = 2Sn − Xn ;
Vn = (Wn , Xn ).

Wn

Sn

Xn

1. Comparer Xn , Sn et Wn . Montrer que (Sn )n∈N et (Wn )n∈N tendent vers l’infini
presque sûrement. Si Wn = k, montrer que les valeurs possibles pour Xn sont

Ik = {−k, −k + 2, −k + 4, . . . , k − 2, k}.

Pour tout l ∈ Ik , dessiner une trajectoire possible pour (Xn )n∈N telle que Wn = k
et Xn = l.
2. On suppose que Wn = Xn = k. Montrer que Vn = (k, k), et que la loi de Vn+1
sachant Vn = (k, k) est
1
P[Vn+1 = (k + 1, k + 1) | Vn = (k, k)] = P[Vn+1 = (k + 1, k − 1) | Vn = (k, k)] = .
2
Si k = Wn > Xn = l, calculer également la loi de Vn+1 sachant Vn = (k, l). En
déduire que (Vn )n∈N est une chaîne de Markov, dont on précisera l’espace des états
et la matrice de transition.
3. Rappeler la valeur de P[Xn = l] (compter les chemins de taille n qui relient 0 à l).
Si k ≥ l a la même parité que l, montrer que
 
k+l
P Sn ≥ et Xn = l = P[Xn = k].
2
 On pourra utiliser la transformation par réflexion suivante, qui établit une bijection
entre  
k+l
trajectoires de taille n dépassant et finissant en l
2
et
{trajectoires de taille n finissant en k} :

k+l k+l
2 2

Sur le dessin, le point marqué est le premier temps où la trajectoire dépasse la valeur
k+l
2
, et on réfléchit la trajectoire après ce point.
4. Déduire de la question précédente que si l ∈ Ik , alors
 
k+l
P[Wn = k et Xn = l] = P Sn = et Xn = l = P[Xn = k] − P[Xn = k + 2].
2
Expliciter le terme de droite de cette formule.
5. Donner une formule pour P[Wn = k], puis pour P[Xn = l | Wn = k], avec l ∈ Ik .
Montrer que la loi conditionnelle de Xn sachant Wn = k est la loi uniforme sur Ik .
6. On admet le résultat plus général suivant : si (w0 , . . . , wn = k) est une suite d’entiers
positifs, avec P[W0 = w0 , . . . , Wn = wn ] 6= 0, alors
(
1
si l ∈ Ik ,
P[Xn = l | W0 = w0 , . . . , Wn = wn = k] = k+1
0 sinon.
Autrement dit, conditionnellement à Wn , la loi de Xn est indépendante du reste
(W0 , . . . , Wn−1 ) de la trajectoire de W , et uniforme sur IWn . Avec ce résultat, montrer
que (Wn )n∈N est une chaîne de Markov sur N, de matrice de transition
k+2 k
P (k, k + 1) = ; P (k, k − 1) = .
2(k + 1) 2(k + 1)
On pourra décomposer la probabilité P[W0 = w0 , . . . , Wn = k, Wn+1 = k ± 1] en
fonction des valeurs de Xn et Xn+1 .

Exercice 2 : configurations planaires du modèle hard-core.

Pour cet exercice, les programmes peuvent être écrits dans n’importe quel langage, ou en
pseudo-code.
Soit N ≥ 1 un entier, et SN = [[1, N ]] × [[1, N ]] la grille planaire de taille N × N . Deux
points (i, j) et (i0 , j 0 ) sont voisins dans SN si i = i0 et |j −j 0 | = 1, ou si j = j 0 et |i−i0 | = 1.
Une configuration admissible sur SN est une fonction σ : SN → {+1, 0, −1}, telle que si
σ(i, j) = +1, alors aucun voisin (i0 , j 0 ) de (i, j) ne vérifie σ(i0 , j 0 ) = −1. Une configuration
admissible représente la répartition de particules de deux types (+1 et −1) dans le plan,
telle que deux particules +1 et −1 ne peuvent pas être voisines. On note XN l’ensemble
des configurations admissibles de taille N .
 50

40

30

20

10

10 20 30 40 50

Figure 1 – Une configuration admissible de taille 50 × 50, avec les particules +1 en bleu
et les particules −1 en orange.

1. Montrer que
2 2
2N ≤ card XN ≤ 3N .
Écrire un programme ConfigurationAdmissible qui prend en argument une ma-
trice de taille N × N constituée de 0, de +1 et de −1, et qui vérifie si c’est une
configuration admissible. Écrire un autre programme DessinerConfiguration qui
dessine une configuration.
On équipe XN de la probabilité suivante :
q A(σ) q A(σ)
µq (σ) = P A(σ)
= ,
σ∈XN q ZN (q)

P est le nombre de particules +1 ou −1 de la

où q > 0 est un paramètre fixé, et A(σ)
configuration σ, qui est aussi A(σ) = (i,j)∈SN |σ(s)|.
2. Soit P la matrice de transition d’une chaîne de Markov d’espace d’états XN . On
suppose que P a la propriété suivante :

∀σ, σ 0 ∈ Xn , µq (σ) P (σ, σ 0 ) = µq (σ 0 ) P (σ 0 , σ).

Montrer que µq est une mesure de probabilité invariante pour la chaîne de Markov
de matrice P .
3. Si (i, j) ∈ SN , t ∈ {0, +1, −1} et σ ∈ XN , on note σ(i,j),t la configuration qui ne
diffère de σ qu’en (i, j), avec σ(i,j),t (i, j) = t. Cette nouvelle configuration n’est plus
forcément admissible. On introduit ensuite l’application

F(i,j),t : XN → XN
(
σ(i,j),t si σ(i,j),t est admissible,
σ 7→
σ sinon.
 Soit (In , Jn )n∈N une suite de points aléatoires indépendants dans SN et de loi uni-
forme : P[(In , Jn ) = (i, j)] = N12 . On considère également une suite (Tn )n∈N d’élé-
ments indépendants dans {0, +1, −1}, avec
1 q
P[Tn = 0] = ; P[Tn = +1] = P[Tn = −1] = .
1 + 2q 1 + 2q

On définit une suite aléatoire (σn )n∈N dans XN par

σ0 = 0 (configuration dont tous les sites valent 0) ; σn+1 = F(In ,Jn ),Tn (σn ).

Montrer que (σn )n∈N est une chaîne de Markov sur XN , et expliciter sa matrice de
transition.
4. Montrer que la chaîne de Markov précédemment construite est irréductible récur-
rente positive sur XN , et que sa mesure invariante est la loi µq .
5. Si n est assez grand, que peut-on dire de la loi de la configuration aléatoire σn ? Écrire
un programme MarkovConfiguration(N,n,q) qui calcule et affiche une configura-
tion aléatoire σn obtenue par la chaîne de Markov (indication : lorsqu’on vérifie à
chaque étape si (σn )(In ,Jn ),Tn est admissible, il suffit de vérifier le voisinage du point
(In , Jn ), et on n’a pas besoin de regarder toute la grille). Dessiner pour N = 30 et
n = 100000 des configurations σn de paramètre q = 0.5, q = 1, q = 2 et q = 4.
Commenter.
Corrigé de l’exercice 1.

1. Comme Sn = maxk∈[[0,n]] Xk , Sn ≥ Xn . On en déduit que Wn = Sn + (Sn − Xn ) ≥ Sn ,

et on a aussi Wn ≥ −Xn , donc :

−Wn ≤ Xn ≤ Sn ≤ Wn .

Comme (Xn )n∈N est irréductible récurrente, elle visite tous les états presque sûre-
ment, donc ne reste pas bornée supérieurement ; ceci implique limn→∞ Sn = +∞
presque sûrement. Comme Wn ≥ Sn , on a également limn→∞ Wn = +∞.
Supposons Wn = k. Comme Wn = 2Sn − Xn , Wn a la même parité que Xn . De
plus, Xn ∈ [[−Wn , Wn ]], donc si Wn = k, alors Xn ∈ Ik = {−k, −k + 2, . . . , k − 2, k}.
Toutes ces valeurs peuvent être atteintes, car si l ∈ Ik , alors le chemin

k+l
2

vérifie bien Wn = k et Xn = l.

2. Si Wn = Xn = k, alors Vn = (Wn , Xn ) = (k, k), et Sn = k : au temps n, la marche

aléatoire atteint son maximum. Fixons des vecteurs v0 , v1 , . . . , vn dans
∞
G
X= {(k, l) | l ∈ Ik },
k=0

avec vn = (k, k), et P[V0 = v0 , . . . , Vn = vn ] 6= 0. Sachant Vn = (k, k), si An+1 = 1,

alors Xn+1 = k + 1 et la marche aléatoire atteint un nouveau maximum au temps
n + 1, égal à k + 1. On a donc Sn+1 = k + 1, et Wn+1 = 2(k + 1) − (k + 1) = k + 1.
Comme An+1 est indépendant de Fn = σ(A1 , . . . , An ) = σ(V1 , . . . , Vn ),
1
P[Vn+1 = (k + 1, k + 1) | V0 = v0 , V1 = v1 , . . . , Vn = (k, k)] = P[An+1 = 1] = .
2
De même, si An+1 = −1, alors Xn+1 = k − 1 et la marche aléatoire garde le même
maximum, donc Sn+1 = k et Wn+1 = 2k − (k − 1) = k + 1. On obtient donc
1
P[Vn+1 = (k + 1, k − 1) | V0 = v0 , V1 = v1 , . . . , Vn = (k, k)] = P[An+1 = −1] = .
2
Supposons maintenant Vn = (k, l) avec k > l. Alors, Sn = k+l
2
> l, donc la marche
aléatoire n’atteint pas son maximum au temps n. Au temps suivant, elle ne pourra
 pas dépasser le niveau k+l
2
(au mieux, elle pourra de nouveau atteindre ce maximum),
donc Sn+1 = Sn = k+l 2
. De plus, si An+1 = 1, alors Xn+1 = l + 1 et Wn+1 = k − 1,
tandis que si An+1 = −1, Xn+1 = l − 1 et Wn+1 = k + 1. En utilisant de nouveau
l’indépendance de An+1 et de la tribu Fn , on conclut que
1
P[Vn+1 = (k − 1, l + 1) | V0 = v0 , V1 = v1 , . . . , Vn = (k, l)] = P[An+1 = 1] = ;
2
1
P[Vn+1 = (k + 1, l − 1) | V0 = v0 , V1 = v1 , . . . , Vn = (k, l)] = P[An+1 = −1] = .
2
F∞ a donc montré que (Vn )n∈N était une chaîne de Markov d’espace d’états X =
On
k=0 {(k, l) | l ∈ Ik }, et de matrice de transition
1
∀k ∈ N, P ((k, k), (k + 1, k + 1)) = P ((k, k), (k + 1, k − 1)) = ;
2
1
∀k ∈ N, ∀l ∈ Ik \ {k}, P ((k, l), (k − 1, l + 1)) = P ((k, l), (k + 1, l − 1)) = ,
2
toutes les autres valeurs de la matrice de transition étant nulles.
3. Toutes les trajectoires de taille n dont les pas valent ±1 ont même probabilité 21n ,
donc
1
P[Xn = l] = n card {trajectoires de taille n reliant 0 à l}.
2
Si un chemin de taille n relie 0 à l, alors il compte n+l
2
pas vers le haut et n−l
2
pas
n+l
vers le bas, et il est entièrement déterminé par le choix des 2 pas vers le haut
parmi n pas. Donc, (
1 n


2n n+l
si l ∈ In ,
P[Xn = l] = 2

0 sinon.
Calculons maintenant P[Sn ≥ k+l 2
et Xn = l], qui est égal à 21n fois le nombre de
chemins de taille n qui relient 0 à l en dépassant à un moment le palier k+l 2
. Si l’on
réfléchit un chemin valide après le premier passage en k+l 2
, on obtient un chemin
reliant 0 à  
k+l k+l
+ − l = k.
2 2
Réciproquement, tout chemin reliant 0 à k passe par k+l
2
, et donne par réflexion
après ce premier passage un chemin valide. Donc,
 
k+l 1
P Sn ≥ et Xn = l = n card {trajectoires de taille n reliant 0 à k}
2 2
= P[Xn = k].

4. On déduit du calcul précédent la loi de (Sn , Xn ) :

 
k+l
P Sn = et Xn = l
2
   
k+l k+l
= P Sn ≥ et Xn = l − P Sn ≥ + 1 et Xn = l
2 2
= P[Xn = k] − P[Xn = k + 2],
 en supposant k et l de même parité. Cette quantité vaut
     
1 n n 1 k+1 n+1
n+k − n+k = n ,
2n 2 2
+1 2 n + 1 n+k2
+1
et c’est aussi P[Wn = k et Xn = l] (si l’on connaît Sn et Xn , on en déduit Vn =
(Wn , Xn ), et réciproquement). On a donc trouvé la loi de Vn ; notons que le résultat
ne dépend pas de l (si l ∈ Ik ).
5. En sommant sur les valeurs possibles de Xn sachant Wn = k, on obtient
1 (k + 1)2
 
n+1
P[Wn = k] = (card Ik ) P[Wn = k et Xn = l] = n n+k .
2 n+1 2
+1
Puis, (
1
P[Wn = k et Xn = l] k+1
si l ∈ Ik ,
P[Xn = l | Wn = k] = =
P[Wn = k] 0 sinon.
La loi de Xn sachant Wn = k est donc uniforme sur l’ensemble Ik .
6. Soit w0 , w1 , . . . , wn des éléments de N, tels que P[W0 = w0 , . . . , Wn = wn ] 6= 0 et
wn = k. On calcule P[Wn+1 = k ± 1 | W0 = w0 , . . . , Wn = wn ] en décomposant les
probabilités en fonction des valeurs xn et xn+1 = xn ± 1 de Xn et Xn+1 :
P[W0 = w0 , . . . , Wn = k, Wn+1 = k ± 1]
X
= P[W0 = w0 , . . . , Wn−1 = wn−1 , Vn = (k, xn )] ×
xn ∈Ik (P ((k, x ), (k ± 1, x + 1)) + P ((k, x ), (k ± 1, x − 1)))
n n n n
1 X
= P[W0 = w0 , . . . , Wn−1 = wn−1 , Wn = k] ×
k + 1 x ∈I
n k (P ((k, xn ), (k ± 1, xn + 1)) + P ((k, xn ), (k ± 1, xn − 1))).

Par conséquent,
P[Wn+1 = k ± 1 | W0 = w0 , . . . , Wn = wn ]
1 X
= (P ((k, xn ), (k ± 1, xn + 1)) + P ((k, xn ), (k ± 1, xn − 1))).
k + 1 x ∈I
n k

Pour l’événement Wn+1 = k + 1, il y a k + 2 paires ((k, xn ), (k + 1, xn ± 1)) qui

contribuent à la somme (chacune pour 12 ), à savoir ((k, k), (k +1, k +1)), ((k, k), (k +
1, k − 1)), et tous les ((k, l), (k + 1, l − 1)) avec l ∈ Ik \ {k}. Donc,
k+2
P[Wn+1 = k + 1 | W0 = w0 , . . . , Wn = wn ] = .
2(k + 1)
De même, pour l’événement Wn+1 = k − 1, il y a k paires ((k, xn ), (k − 1, xn ± 1))
qui contribuent à la somme, à savoir tous les ((k, l), (k − 1, l + 1)) avec l ∈ Ik \ {k}.
Donc,
k
P[Wn+1 = k − 1 | W0 = w0 , . . . , Wn = wn ] = .
2(k + 1)
On conclut que (Wn )n∈N est une chaîne de Markov sur N, de matrice de transition
k+2 k
P (k, k + 1) = ; P (k, k − 1) = .
2(k + 1) 2(k + 1)
Corrigé de l’exercice 2.

1. Toutes les configurations avec seulement des +1 et des 0 sont admissibles, donc on
2
a au moins 2card SN = 2N configurations admissibles. D’autre part, le nombre total
2
de configurations (admissibles ou non) est 3N , puisqu’on a 3 choix possibles pour
chaque site. Ainsi,
2 2
2N ≤ card SN ≤ 3N .
On définit en Sage une classe Configuration, à laquelle on ajoutera au fur et à
mesure des méthodes :
class Configuration:
def __init__(self,n):
self.size = n
self.matrix = matrix(ZZ,n,n)
Pour tester si une configuration est admissible, on a besoin de savoir identifier les
voisins de chaque site. La méthode suivante, rajoutée à la définition de la classe,
renvoie la liste des voisins d’un site (en prenant en compte les effets de bord) :
def neighbors(self,site):
res = []
n = self.size
if site[0] < n-1:
res.append((site[0]+1,site[1]))
if site[0] > 0:
res.append((site[0]-1,site[1]))
if site[1] < n-1:
res.append((site[0],site[1]+1))
if site[1] > 0:
res.append((site[0],site[1]-1))
return res
On teste alors si une configuration est admissible en vérifiant un à un les sites (on
effectue plus de vérifications que nécessaire, mais ce n’est pas très grave) :
def is_admissible(self):
res = 0
for i in range(self.size):
for j in range(self.size):
if (-1 in [self.matrix[i,j]*self.matrix[n[0],n[1]]
for n in self.neighbors((i,j))]):
res += 1
if res == 0:
return True
else:
return False
Par exemple, le code suivant
 C = Configuration(2) ; C.matrix[0,0] = 1 ; C.matrix[0,1] = 1
C.is_admissible()
renvoie True, tandis que le code
C = Configuration(2) ; C.matrix[0,0] = 1 ; C.matrix[0,1] = -1
C.is_admissible()
renvoie False. Pour dessiner une configuration, on ajoute à la définition de la classe
la méthode :
def plot(self):
G = Graphics()
for i in range(self.size):
for j in range(self.size):
if self.matrix[i,j] == 1:
G += polygon([(i,j),(i,j+1),(i+1,j+1),
(i+1,j)],rgbcolor=(0,0,0.8))
elif self.matrix[i,j] == -1:
G += polygon([(i,j),(i,j+1),(i+1,j+1),
(i+1,j)],rgbcolor=(1,0.5,0))
G.show(axes=False)

2. Montrons que sous la condition de réversibilité, la loi µq est invariante pour la

matrice P . On calcule
X X
(µq P )(σ) = µq (σ 0 ) P (σ 0 , σ) = µq (σ) P (σ, σ 0 )
σ 0 ∈XN σ 0 ∈XN
!
X
= µq (σ) P (σ, σ 0 ) = µq (σ) × 1 = µq (σ).
σ 0 ∈XN

On a donc bien une loi invariante sous P .

3. Le processus aléatoire (σn )n∈N vérifie une équation de récurrence du type σn+1 =
F (σn , ξn ), où les aléas ξn = (In , Jn , Tn ) sont indépendants et identiquement distri-
bués. Par le théorème de représentation des chaînes de Markov, on en déduit que
(σn )n∈N est une chaîne de Markov sur XN . De plus, sa matrice de transition est

P (σ, σ 0 ) = P[{ξ | F (σ, ξ) = σ 0 }].

Par définition, pour tout ξ ∈ SN × {0, +1, −1}, F (σ, ξ) = Fξ (σ) ne peut être égal
qu’à σ ou à une configuration admissible σ 0 qui diffère de σ en un seul site. Dans
ce dernier cas, il y a un seul ξ = (i, j, t) tel que Fξ (σ) = σ 0 , et σ 0 (i, j) = t. La
q
probabilité pour tirer au hasard cet élément ξ est N12 1+2q 1
si t = 0, et N12 1+2q si
0
t = 1 ou t = −1. Ainsi, pour toutes configurations admissibles σ et σ ,
 1
0 0
 N 2 (1+2q) si σ diffère de σ en un seul site (i, j), avec σ (i, j) = 0,

P (σ, σ 0 ) = N 2 (1+2q)
q
si σ 0 diffère de σ en un seul site (i, j), avec σ 0 (i, j) = ±1,

Cσ si σ 0 = σ,

 avec X
Cσ = 1 − P (σ, σ 0 ).
σ 0 6=σ en un seul site

4. À partir de n’importe quelle configuration σ, on peut atteindre la configuration 0

en changeant tous les sites un à un en la valeur 0 (ceci ne crée pas de configuration
non-admissible). Par conséquent, pour toutes configurations σ et σ 0 , on peut trouver
des transitions reliant σ à 0, puis 0 à σ 0 ; la chaîne est donc irréductible, et comme
elle est finie, elle est récurrente positive. Pour montrer que sa mesure invariante est
µq , il suffit de vérifier la condition de réversibilité. Soit σ et σ 0 deux configurations
admissibles dans XN ; pour montrer que µq (σ) P (σ, σ 0 ) = µq (σ 0 ) P (σ 0 , σ), on peut
supposer σ 6= σ 0 car ce cas est trivial, et aussi P (σ, σ 0 ) 6= 0, c’est-à-dire que σ et σ 0
|σ 0 (i,j)|
ne diffèrent qu’en un seul site (i, j). Notons alors que P (σ, σ 0 ) = N12 q 1+2q , de sorte
que
1 P 0
s∈SN |σ(s)|+|σ (i,j)|
µq (σ) P (σ, σ 0 ) = 2
q .
ZN (q) N (1 + 2q)
De même,
1 P
|σ 0 (s)|+|σ(i,j)|
µq (σ 0 ) P (σ 0 , σ) = q s∈SN
,
ZN (q) N 2 (1 + 2q)
et l’égalité des deux quantités vient alors de
X X
|σ(s)| + |σ 0 (i, j)| = |σ(s)| + |σ(i, j)| + |σ 0 (i, j)|
s∈SN s6=(i,j)
X X
= |σ 0 (s)| + |σ(i, j)| + |σ 0 (i, j)| = |σ 0 (s)| + |σ(i, j)|.
s6=(i,j) s∈SN

5. Par le théorème ergodique, si πn désigne la loi de σn , alors πn *n→∞ µq , donc σn a

presque pour loi µq lorsque n est grand. On peut donc utiliser la chaîne de Markov
pour (presque) simuler la loi µq . Concrètement, les deux méthodes
def random_site(self):
n = self.size
return (floor(n*random()),floor(n*random()))
et
def random_sign(self,q):
alea = random()
if alea < q/(1+2*q):
return 1
elif alea < (2*q)/(1+2*q):
return -1
else:
return 0
tirent au hasard un site d’une configuration, et un signe dans {0, +1, −1}. La mé-
thode
def transform(self,site,sign):
if sign == 1:
if not (-1 in [self.matrix[n[0],n[1]] for
n in self.neighbors(site)]):
self.matrix[site[0],site[1]] = 1
elif sign == -1:
if not (1 in [self.matrix[n[0],n[1]] for
n in self.neighbors(site)]):
self.matrix[site[0],site[1]] = -1
else:
self.matrix[site[0],site[1]] = 0
correspond à la transformation F(i,j),t , et finalement,
def markov(self,n,q):
for i in range(n):
self.transform(self.random_site(),self.random_sign(q))
applique n transitions de la chaîne de Markov de paramètre q à une configuration.
On peut donc simuler σn avec :
def MarkovConfiguration(N,n,q):
C = Configuration(N)
C.markov(n,q)
return C
30 30

25 25

20 20

15 15

10 10

5 5

5 10 15 20 25 30 5 10 15 20 25 30
30 30

25 25

20 20

15 15

10 10

5 5

5 10 15 20 25 30 5 10 15 20 25 30
Lorsque q augmente, la mesure µq charge de plus en plus les configurations qui ont
beaucoup de particules et peu de sites laissés vacants (les sites 0). Comme les sites
+1 et −1 ne peuvent pas être contigus, pour q assez grand, ceci restreint le nombre
de zones +1 et −1 disjointes, car elles doivent être séparées par des sites vacants.
Ainsi, pour q suffisamment grand, une configuration typique sous µq contient un
petit nombre de larges domaines +1 ou −1, et très peu de sites vacants entre ces
domaines. On a dessiné ci-dessous un exemple avec N = 50 et q = 100 :

50

40

30

20

10

10 20 30 40 50