Chapitre 8

Chaı̂nes de Markov

8.1 La matrice de transition

Une suite de variables aléatoires {Xn }n≥0 à valeurs dans l’espace dénombrable E est
appelé processus stochastique (à temps discret) (à valeurs dans E). L’ensemble E est
l’espace d’état, dont les éléments seront notés i, j, k... Lorsque Xn = i, le processus est
dit être dans, ou visiter, l’état i au temps n.
Les suites de variables aléatoires iid sont bien des processus stochastiques, mais du
point de vue de la modélisation, elles ne sont pas satisfaisantes, ne prenant pas en compte
la dynamique des systèmes en évolution, du fait de l’indépendance. Pour introduire
cette dynamique, il faut tenir compte de l’influence du passé, ce que font les chaı̂nes
de Markov, à la façon des équations de récurrence dans les systèmes déterministes. En
fait, les chaı̂nes de Markov sont des processus stochastiques dont l’évolution est régie
par une équation de récurrence du type Xn+1 = f (Xn , Zn+1 ), où {Zn }n≥1 est une suite
iid indépendante de la valeur initiale X0 (voir plus bas). Cette structure extrêmement
simple suffit à générer une grande variété de comportements. C’est pour cela que les
chaı̂nes de Markov trouvent des applications dans beaucoup de domaines comme, par
exemple, la biologie, la physique, la sociologie, la recherche opérationnelle et les sciences
de l’ingénieur, où elles donnent des réponses qualitatives aussi bien que quantitatives
aux problèmes posés.
Voici la définition :
Définition 8.1.1 Si pour tout entier n ≥ 0 et tous états i0 , i1 , . . . , in−1 , i, j ∈ E,
P (Xn+1 = j | Xn = i, Xn−1 = in−1 , . . . , X0 = i0 ) = P (Xn+1 = j | Xn = i) , (8.1)
le processus {Xn }n≥0 est appelé chaı̂ne de Markov. Celle-ci est dite homogène si le
second membre de (8.1) ne dépend pas de n.

203
204 CHAPITRE 8. CHAÎNES DE MARKOV

On abrègera “chaı̂ne de Markov homogène” par “cmh”.

La propriété (8.1) est la propriété de Markov .
La matrice P = {pij }i,j∈E , où

pij = P (Xn+1 = j | Xn = i)

est la probabilité de transition de i vers j, est appellée matrice de transition de la chaı̂ne.

Comme ses éléments sont des probabilités et puisqu’une transition a nécessairement lieu
d’un état vers un autre état, on a

pij ≥ 0, et pik = 1
k∈E

pour tous états i, j. Une matrice P indexée par E et satisfaisant les propriétés ci-dessus
est appelée matrice stochastique.
L’espace d’état peut être infini et par conséquent une telle matrice n’est pas du type
étudié en algèbre linéaire. Toutefois, l’addition et la multiplication sont définies par les
mêmes règles formelles. Par exemple, avec A = {aij }i,j∈E et B = {bij }i,j∈E , le produit
C = AB est la matrice {cij }i,j∈E , où cij = k∈E aik bkj . La notation x = {xi }i∈E
représente formellement un vecteur colonne et xT est donc un vecteur ligne,  le transposé
de x. Par exemple, y = {yi }i∈E donné par y T = xT A est défini par  i y = k∈E xk aki .
Semblablement, z = {zi }i∈E donné par z = Ax est défini par zi = k∈E aik zk .
Une matrice de transition P est parfois représentée par son graphe de transition G,
un graphe dont les nœuds sont les états de E et qui a une arête orientée de i vers j si et
seulement si pij > 0, auquel cas cette arête est ornée de l’étiquette pij .
La propriété de Markov (8.1) s’étend facilement (voir l’Exercice 8.5.2) comme suit

P (Xn+1 = j1 , . . . , Xn+k = jk | Xn = i, Xn−1 = in−1 , . . . , X0 = i0 )

= P (Xn+1 = j1 , . . . , Xn+k = jk | Xn = i) (8.2)

pour tous i0 , . . . , in−1 , i, j1 , . . . , jk . En notant

A = {Xn+1 = j1 , . . . , Xn+k = jk }, B = {X0 = i0 , . . . , Xn−1 = in−1 },

la dernière égalité se lit P (A | Xn = i, B) = P (A | Xn = i), et celle-ci se lit à son tour

P (A ∩ B | Xn = i) = P (A | Xn = i)P (B | Xn = i).

Donc, A et B sont conditionnellement indépendants sachant Xn = i. Tel est le contenu

du :
Théorème 8.1.1 Pour tout i ∈ E, n ≥ 1, le futur au temps n et le passé au temps n
sont conditionnellement indépendants étant donné l’état présent Xn = i.
Voir cependant l’Exercice 8.5.1.
Le Théorème 8.1.1 montre en particulier que la propriété de Markov est indépendante
de la direction du temps.
8.1. LA MATRICE DE TRANSITION 205

La distribution d’une cmh

La distribution au temps n de la chaı̂ne est le vecteur νn = {νn (i)}i∈E , où

νn (i) = P (Xn = i).


La règle des causes totales donne νn+1 (j) = i∈E νn (i)pij , c’est-à-dire, sous forme ma-
T
tricielle, νn+1 = νnT P. En itérant cette égalité, on obtient pour tout n ≥ 1 :

νnT = ν0T Pn . (8.3)

La matrice Pn est appelée matrice de transition en n étapes car son terme général n’est
autre que
pij (n) = P (Xn+m = j | Xm = i).

En effet, d’après la règle de Bayes séquentielle et en tenant compte de la propriété de

Markov, on trouve pour le second membre de la dernière égalité

pii1 pi1 i2 · · · pin−1 j ,
i1 ,...,in−1 ∈E

qui est bien le terme général de la n-ème puissance de la matrice P.

Par convention, P0 = la matrice identité (pi,j (0) = 1{i=j} ).
La variable X0 est l’état initial, et sa distribution de probabilité ν0 est la distribution
initiale. La règle de Bayes séquentielle donne :

P (X0 = i0 , X1 = i1 , . . . , Xk = ik )
= P (X0 = i0 )P (X1 = i1 | X0 = i0 ) · · · P (Xk = ik | Xk−1 = ik−1 , . . . , X0 = i0 ) ,

et donc, dans le cas d’une cmh,

P (X0 = i0 , X1 = i1 , . . . , Xk = ik ) = ν0 (i0 )pi0 i1 · · · pik−1 ik . (8.4)

La donnée de (8.4) pour tout k ≥ 0 et tous états i0 , i1 , . . . , ik constitue la distribution de

probabilité de la cmh. Donc :

Théorème 8.1.2 La distribution de probabilité d’une cmh est entièrement déterminée

par sa distribution initiale et sa matrice de transition.

Notation. On abrègera
 P (A | X0 = i) en Pi (A). Pour toute probabilité µ sur E, on
notera Pµ (A) = i∈E µ(i)P (A|X0 = i). C’est la probabilité qui régit l’évolution de la
chaı̂ne lorsque la distribution initiale est µ.
206 CHAPITRE 8. CHAÎNES DE MARKOV

Récurrences markoviennes
Nombre de cmh sont décrites par une équation de récurrence contrôlée par un “bruit
blanc”. Plus précisément,
Théorème 8.1.3 Soit {Zn }n≥1 une suite iid de variables aléatoires à valeurs dans un
espace arbitraire G. Soit E un espace dénombrable, et soit une fonction f : E × G → E.
Soit X0 une variable aléatoire à valeurs dans E, indépendante de la suite {Zn }n≥1 .
L’équation de récurrence
Xn+1 = f (Xn , Zn+1 ) (8.5)
définit alors une cmh.

Démonstration. L’itération de (8.5) montre que pour tout n ≥ 1, il existe une fonc-
tion gn telle que Xn = gn (X0 , Z1 , . . . , Zn ), et donc P (Xn+1 = j | Xn = i, Xn−1 =
in−1 , . . . , X0 = i0 ) = P (f (i, Zn+1 ) = j | Xn = i, Xn−1 = in−1 , . . . , X0 = i0 ) =
P (f (i, Zn+1 ) = j), puisque l’événement {X0 = i0 , . . . , Xn−1 = in−1 , Xn = i} est ex-
primable en termes de X0 , Z1 , . . . , Zn et est donc indépendant de Zn+1 . Semblablement,
P (Xn+1 = j | Xn = i) = P (f (i, Zn+1 ) = j). On a donc une chaı̂ne de Markov, qui est
de plus homogène, puisque le second membre de la dernière égalité ne dépend pas de n.
Explicitement :
pij = P (f (i, Z1 ) = j). (8.6)


Exemple 8.1.1: Marche aléatoire sur Z, take 1. Soit X0 une variable à valeurs
dans Z. Soit {Zn }n≥1 une suite de variables iid indépendante de X0 , prenant les valeurs
+1 ou −1, et de distribution de probabilité commune

P (Zn = +1) = p,

où 0 < p < 1. Le processus {Xn }n≥1 défini par

Xn+1 = Xn + Zn+1

est, au vu du Théorème 8.1.3, une cmh, appelée marche aléatoire sur Z.

Exemple 8.1.2: Automates stochastiques. Un automate fini (E, A, f ) peut lire

les lettres d’un alphabet fini A écrites sur un ruban infini. Cet automate se trouve à un
instant donné dans un quelconque des états d’un ensemble fini E, et son évolution est
régie par une fonction f : E × A → E comme suit. Quand l’automate est dans l’état
i ∈ E et lit la lettre a ∈ A, il passe de l’état i à l’état j = f (i, a) et lit sur le ruban la
prochaine lettre à droite de celle qu’il vient de lire.
Un automate est représenté par son graphe de transition G ayant pour nœuds les états
de E. Il y a une arête orientée du nœud (état) i au nœud j si et seulement s’il existe a ∈ A
8.1. LA MATRICE DE TRANSITION 207

1
0 1 1 1
0 0 1 2 3

0
0

a
1 0 0 1 1 1 1 0 0 1 1 1 1 1 1 0 1 0

3 3 3
b
1
2
1 1 1
1 2 2 2
2
0 1 1 2 3
2
1
2
1
2

c
Un automate stochastique
tel que j = f (i, a), et cette arête reçoit alors l’étiquette a. Si j = f (i, a1 ) = f (i, a2 ) pour
a1 = a2 , il y a alors 2 arêtes orientées de i vers j avec les étiquettes a1 et a2 , ou, plus
économiquement, une seule arête orientée avec l’étiquette (a1 , a2 ). Plus généralement,
une arête orientée donnée peut avoir des étiquettes multiples à tous ordres.
Considérons à titre d’exemple l’automate avec l’alphabet A = {0, 1} correspondant
au graphe de transition de la Figure a. L’automate, initialisé dans l’état 0, lit la suite de
la Figure b de gauche à droite, passant successivement dans les états (y compris l’état
initial 0)
0100123100123123010.
Il apparaı̂t que l’automate est dans l’état 3 après avoir lu trois 1 successifs qui ne che-
vauchent pas un bloc de trois 1 consécutifs précédemment enregistré (voir Figure b), et
seulement dans cette circonstance.
Si la suite de lettres lues par l’automate est {Zn }n≥1 , la suite des états {Xn }n≥0 est
alors donnée par l’équation de récurrence Xn+1 = f (Xn , Zn+1 ) et donc, si {Zn }n≥1 est
iid et indépendante de l’état initial X0 , alors {Xn }n≥1 est, au vu du Théorème 8.1.3,
une cmh. Son graphe de transition est représenté dans la Figure c.

Toutes les cmh ne reçoivent pas une description “naturelle” du type de celle du Théorème
8.1.3. Cependant une telle description est toujours possible dans le sens suivant :
208 CHAPITRE 8. CHAÎNES DE MARKOV

Théorème 8.1.4 À toute matrice stochastique P sur E, on peut associer une cmh
{Xn }n≥0 avec cette matrice pour matrice de transition, et admettant une représentation
comme dans le Théorème 8.1.3.
Démonstration. On identifiera E à N. On pose

j−1
 j

Xn+1 = j si pXn k < Zn+1 ≤ pX n k ,
k=0 k=0

où {Zn }n≥1 est iid, uniformément distribuée sur (0, 1]. On peut appliquer le Théorème
8.1.3, et on vérifie que cette cmh a la matrice de transition requise (Formule (8.6)). 

Cette représentation est utile pour simuler de petites (avec un petit espace d’état) cmh.
Elle a également un intérêt théorique. En particulier, lorsqu’on cherche à démontrer une
propriété qui concerne la distribution d’une cmh, on peut toujours supposer que celle-ci
admet une représentation comme dans le Théorème 8.1.3. Cette remarque sera utile à
plusieurs reprises.
Toutes les cmh ne reçoivent pas de manière “naturelle” une description du type
donné dans le Théorème 8.1.3. Une légère modification de ce théorème en élargit
considérablement la portée.
Théorème 8.1.5 Considérons la situation du Théorème 8.1.3, sauf en ce qui concerne
la distribution de X0 , Z1 , Z2 , . . .. On suppose à la place que F est dénombrable et que
pour tout n ≥ 0, Zn+1 est conditionnellement indépendant de Zn , . . . , Z1 , Xn−1 , . . . , X0
sachant Xn , c’est-à-dire : pour tout k, k1 , . . . , kn ∈ F , i0 , i1 , . . . , in−1 , i ∈ E,

P (Zn+1 = k | Xn = i, Xn−1 = in−1 , . . . , X0 = i0 , Zn = kn , . . . , Z1 = k1 )

= P (Zn+1 = k | Xn = i),

où la dernière quantité est indépendante de n. Alors, {Xn }n≥0 est une cmh dont les
probabilités de transition sont données par la formule :

pij = P (f (i, Z1 ) = j | X0 = i).

Démonstration. Exercice 8.5.3. 

Exemple 8.1.3: L’urne d’Ehrenfest, take 1. Ce modèle simplifié de diffusion à

travers une membrane poreuse fut proposé en 1907 par les physiciens autrichiens Ta-
tiana et Paul Ehrenfest pour décrire en termes de physique statistique les échanges de
chaleur entre deux systèmes à différentes températures, et ainsi de mieux comprendre le
phénomène d’irréversibilité thermodynamique (Exemple 8.3.1).
Il y a N particules qui peuvent se trouver dans le compartiment A ou le compartiment
B. Supposons qu’au temps n ≥ 0, Xn = i particules sont dans A. On choisit alors une
particule au hasard, et cette particule est alors transférée du compartiment où elle se
trouvait dans l’autre. Le prochain état du système, Xn+1 , est donc, soit i−1 (la particule
8.1. LA MATRICE DE TRANSITION 209

i
déplacée fut trouvée dans le compartiment A) avec la probabilité N, soit i + 1 (elle fut
trouvée dans B) avec la probabilité NN−i .
Ce modèle relève du Théorème 8.1.5. Pour tout n ≥ 0,

Xn+1 = Xn + Zn+1 ,

où Zn ∈ {−1, +1} et P (Zn+1 = −1 | Xn = i) = Ni . Les termes non nuls de la matrice

de transition sont donc
N −i i
pi,i+1 = , pi,i−1 = .
N N

Analyse à un pas
Certaines fonctionnelles  de cmh, en particulier les probabilités d’absorption par un
ensemble d’états A fermé ( j∈A pij = 1 pour tout i ∈ A) et les temps moyens avant
absorption, peuvent être évalués grâce à la méthode appelée analyse à un pas. Cette
technique, qui est le moteur de la plupart des calculs en théorie des chaı̂nes de Markov,
va être illustrée par les exemple suivants.

Exemple 8.1.4: La ruine du joueur, take 1. Deux joueurs A et B jouent à pile ou

face, où la probabilité de face est p ∈ (0, 1), et les tirages successifs sont iid. Si on note
Xn la fortune du joueur A au temps n, alors Xn+1 = Xn + Zn+1 , où Zn+1 = +1 (resp.,
−1) avec probabilité p (resp., q = 1 − p), et {Zn }n≥1 est iid. En d’autres mots, A parie 1
euro sur face à chaque lancer, et B parie la même chose sur pile. Le processus {Xn }n≥1
est donc la marche aléatoire de l’Exemple 8.1.1. Les fortunes initiales de A et B sont
respectivement a et b. Le jeu se termine dès qu’un des deux joueurs est ruiné.
La durée du jeu est T , le premier temps n auquel Xn = 0 ou c, et la probabilité que
A gagne est u(a) = P (XT = c | X0 = a).
A gagne
c=a+b

0
1 2 3 4 5 6 7 8 9 10 T = 11
La ruine du joueur B
210 CHAPITRE 8. CHAÎNES DE MARKOV

Au lieu de calculer seulement u(a), l’analyse à un pas calcule

u(i) = P (XT = c | X0 = i)

pour tout i, 0 ≤ i ≤ c, et pour ce faire, elle génère une équation de récurrence pour les
u(i) en décomposant l’événement “A gagne” selon les éventualités du premier lancer, et
en utilisant la règle des causes totales. Si X0 = i, 1 ≤ i ≤ c − 1, alors X1 = i + 1 (resp.,
X1 = i − 1) avec probabilité p (resp., q), et la probabilité de ruine de B sachant que A
a une fortune initiale i + 1 (resp., i − 1) est u(i + 1) (resp., u(i − 1)). Donc, pour tout i,
1 ≤ i ≤ c − 1,
u(i) = pu(i + 1) + qu(i − 1),
avec les conditions aux frontières u(0) = 0, u(c) = 1.
L’équation caractéristique associée à cette équation de récurrence linéaire est
pr2 − r + q = 0. Elle a deux racines distinctes, r1 = 1 et r2 = pq , si p = q, et une racine
+ ,i
double, r1 = 1, si p = q = 21 . La solution générale est donc u(i) = λr1i + µr2i = λ + µ pq
quand p = q, et u(i) = λr1i + µir1i = λ + µi lorsque p = q = 21 . Tenant compte des
conditions aux frontières, on peut calculer λ et µ. Le résultat est, pour p = q,

1 − ( pq )i
u(i) = ,
1 − ( pq )c

et pour p = q = 12 ,
i
u(i) = .
c

Dans le cas p = q = 21 , la probabilité v(i) que B gagne quand la fortune initiale de B

est c − i est obtenue en remplaçant i par c − i dans l’expression de u(i). Ce qui donne
v(i) = c−i i
c = 1 − c . On vérifie que u(i) + v(i) = 1, ce qui signifie en particulier que la
probabilité pour que le jeu ne s’éternise pas est 1. Le lecteur est invité à vérifier qu’il en
est de même pour p = q.

Exemple 8.1.5: La ruine du joueur, take 2. (suite de l’Exemple 8.1.4) La durée

m(i) = E[T | X0 = i] du jeu quand la fortune initiale du joueur A est i vérifie l’équation
de récurrence
m(i) = 1 + pm(i + 1) + qm(i − 1)
lorsque 1 ≤ i ≤ c − 1. En effet, la pièce doit être lancée au moins une fois, et avec la
probabilité p (resp., q) la fortune de A sera i + 1 (resp., i − 1), et donc m(i + 1) (resp.,
m(i − 1)) lancers supplémentaires seront en moyenne nécessaires pour finir le jeu. Les
conditions aux frontières sont

m(0) = 0, m(c) = 0.
8.1. LA MATRICE DE TRANSITION 211

Réécrivons l’équation de récurrence sous la forme −1 = p(m(i + 1) − m(i)) − q(m(i) −

m(i − 1)). Notant
yi = m(i) − m(i − 1),
on a, pour 1 ≤ i ≤ c − 1,
−1 = pyi+1 − qyi
et
m(i) = y1 + y2 + · · · + yi .
Nous allons résoudre cette équation de récurrence avec p = q = 12 . Pour cela, on la réécrit

1 1
−1 = y2 − y1 ,
2 2
1 1
−1 = y3 − y2 ,
2 2
..
.
1 1
−1 = yi − yi−1 ,
2 2
et donc, en sommant,
1 1
−(i − 1) = yi − y1 ,
2 2
c’est-à-dire, pour 1 ≤ i ≤ c,
yi = y1 − 2(i − 1).

Reportant cette expression dans m(i) = y1 + y2 + · · · + yi , et observant que y1 = m(1),

on obtient

m(i) = im(1) − 2[1 + 2 + · · · + (i − 1)] = im(1) − i(i − 1).

La condition m(c) = 0 donne cm(1) = c(c − 1) et donc, finalement,

m(i) = i(c − i).

Exemple 8.1.6: Récréation : Tennis. Au tennis, si on ignore les “tie-breaks”, un

“jeu” peut être modélisé par une cmh dont le graphe de transition est donné par la
figure ci-dessous, où p est la probabilité que le serveur A gagne le point, et q = 1 − p.
On veut calculer la probabilité pour que B remporte le jeu.
On voit sur la figure qu’un jeu comporte deux étapes : on atteint d’abord un des états
supérieurs du graphe et ensuite, on reste dans les états supérieurs jusqu’à l’absorption
en “jeu pour A” ou “jeu pour B.” En modifiant les noms des états supérieurs, le graphe
de la cmh de la deuxième étape est donné par la Figure b.
212 CHAPITRE 8. CHAÎNES DE MARKOV

p p
p q
JEU A AV. A ÉGALITÉ AV. B JEU B

q q
q p
p q

p 40 − 15 q p 15 − 40 q

q p q p

40 − 0 30 − 15 15 − 30 0 − 40

p q p q p q

30 − 0 15 − 15 0 − 30

p q p q

15 − 0 0 − 15

p q

0−0

a
q q q

1 5 4 3 2 1 1

p p p

b
Tennis : un jeu sans la règle du tie-break
8.1. LA MATRICE DE TRANSITION 213

L’analyse à un pas donne pour bi , la probabilité pour que B gagne sachant que la
deuxième étape débute en i,
b1 = 1 , b 5 = 0
et

b2 = q + pb3 ,
b3 = qb2 + pb4 ,
b4 = qb3 .

pour p = q,

1 − pq q2 q3
(b1 , b2 , b3 , b4 , b5 ) = 1 , q , , ,0 .
1 − 2pq 1 − 2pq 1 − 2pq

Si on débute en 0-0, B gagne avec la probabilité 5i=1 p(i)bi , où p(i) est la probabilité
que la deuxième étape débute en i. Une simple énumération des chemins allant de 0-0 à
l’état supérieur 1 donne p(1) = q 4 + q 3 pq + q 2 pq 2 + qpq 3 + pq 4 , c’est-à dire,

p(1) = q 4 (1 + 4p).

Le lecteur pourra terminer les calculs.

Distribution stationnaire
Définition 8.1.2 Une distribution de probabilité π satisfaisant l’equation de balance
globale
πT = πT P (8.7)
est appelée distribution stationnaire de la matrice de transition P, ou de la cmh.

L’equation de balance globale dit que pour tout état i,


π(i) = π(j)pji .
j∈E

L’itération de (8.7) donne π T = π T Pn pour tout n ≥ 0, et donc, au vu de (8.3), si la dis-

tribution initiale ν = π, alors νn = π pour tout n ≥ 0 : si une chaı̂ne a pour distribution
initiale la distribution stationnaire, elle garde cette distribution pour toujours. Mais il y
a plus. En effet, dans ce cas,

P (Xn = i0 , Xn+1 = i1 , . . . , Xn+k = ik ) = P (Xn = i0 )pi0 i1 . . . pik−1 ik

= π(i0 )pi0 i1 . . . pik−1 ik

ne dépend plus n. C’est dans ce sens qu’on dit que la chaı̂ne est stationnaire. On dit
aussi qu’elle se trouve en régime stationnaire, ou en équilibre. En résumé :
214 CHAPITRE 8. CHAÎNES DE MARKOV

Théorème 8.1.6 Si la distribution initiale d’une cmh est la distribution stationnaire,

la cmh est stationnaire.
L’équation de balance globale π T P = π T , et la relation π T 1 = 1 (où 1 est un vecteur
colonne dont toutes les coordonnées sont égales à 1) qui exprime que π est une proba-
bilité, donnent, lorsque E est fini, |E| + 1 équations avec |E| variables. Une de ces |E|
équations est superflue sous la contrainte π T 1 = 1. En effet, si on fait la somme des
équations de π T P = π T on obtient π T P1 = π T 1, c’est-à-dire, π T 1 = 1.

Exemple 8.1.7: Chaı̂ne à 2 états. L’espace d’état est E = {1, 2} et la matrice de

transition est 
1−α α
P= ,
β 1−β
où α, β ∈ (0, 1). Les équations de balance globale sont

π(1) = π(1)(1 − α) + π(2)β,

π(2) = π(1)α + π(2)(1 − β).

Ce système dépendant se réduit à une seule équation π(1)α = π(2)β, à laquelle il faut
ajouter π(1) + π(2) = 1 qui exprime que π est une probabilité. On obtient

β α
π(1) = , π(2) = .
α+β α+β

Exemple 8.1.8: L’urne d’Ehrenfest, take 2. (suite de l’Exemple 8.1.3) Les

équations de balance globale sont pour i, 1 ≤ i ≤ N − 1,

i−1 i+1
π(i) = π(i − 1) 1 − + π(i + 1)
N N

et pour les états extrêmes,

1 1
π(0) = π(1) , π(N ) = π(N − 1) .
N N
Laissant π(0) indéterminé, on résout les équations pour i = 0, 1, . . . , N successivement
pour obtenir 
N
π(i) = π(0) .
i
La quantité π(0) est alors déterminée en écrivant que π est un vecteur de probabilité :
N
 N 
 N
1= π(i) = π(0) = π(0)2N .
i
i=0 i=0
8.1. LA MATRICE DE TRANSITION 215

1
Ceci donne pour π distribution binomiale de taille N et de paramètre 2 :

1 N
π(i) = N .
2 i

C’est la distribution qu’on obtiendrait en plaçant indépendamment les particules dans

les compartiments avec la probabilité 12 pour chaque compartiment.

Les distributions stationnaires peuvent être nombreuses. Ainsi, si on prend la matrice de

transition qui est la matrice unité, toute probabilité sur l’espace d’état est une probabilité
stationnaire. Il se peut aussi qu’il n’y ait pas de probabilité stationnaire (voir l’Exercice
8.5.10).

Exemple 8.1.9: processus de naissance et de mort, I. De tels processus

généralisent le modèle de diffusion d’Ehrenfest. L’espace d’état est E = {0, 1, . . . , N }, et
la matrice de transition :
 
0 1
 q 1 r1 p1 
 
 q r p 
 2 2 2 
 . .. 
 
P=  ,
q r p 
 i i i 
 . .. . .. . .. 
 
 
 qN −1 rN −1 pN −1 
1 0

où pi > 0 et qi > 0 pour tout état i tel que 1 ≤ i ≤ N − 1. Les équations de balance
globale pour les états i = 0, N sont :

π(i) = pi−1 π(i − 1) + ri π(i) + qi+1 π(i + 1),

et pour les états 0 et N :

π(0) = π(1)q1 , π(N ) = π(N − 1)pN −1

(barrières réfléchissantes). En remarquant que ri = 1 − pi − qi et en regroupant des

termes, on a, pour 2 ≤ i ≤ N − 1,

π(i + 1)qi+1 − π(i)pi = π(i)qi − π(i − 1)pi−1

et

π(1)q1 − π(0) = 0,
π(2)q2 − π(1)p1 = π(1)q1 − π(0).
216 CHAPITRE 8. CHAÎNES DE MARKOV

Donc, π(1)q1 = π(0), et pour 2 ≤ i ≤ N − 1,

π(i)qi = π(i − 1)pi−1 .

Ceci donne
1
π(1) = π(0) ,
q1
et pour 2 ≤ i ≤ N ,
p1 p2 · · · pi−1
π(i) = π(0) . (8.8)
q1 q2 · · · qi

L’inconnue π(0) est déterminée par l’égalité N i=0 π(i) = 1 (π est une probabilité), ce
qui donne, 0 1
1 p1 p1 p2 · · · pN −1
π(0) 1 + + + ··· + = 1. (8.9)
q1 q1 q2 q1 q2 · · · qN −1 qN

Retournement du temps
Les notions de retournement de temps et de réversibilité sont très productives en
théorie des chaı̂nes de Markov.
Soit {Xn }n≥0 une cmh de matrice de transition P admettant une distribution sta-
tionnaire π positive (π(i) > 0 pour tout état i). La matrice Q, indexée par E, définie
par
π(i)qij = π(j)pji , (8.10)
est une matrice stochastique. En effet,
  π(j) 1  π(i)
qij = pji = π(j)pji = = 1,
π(i) π(i) π(i)
j∈E j∈E j∈E

où la troisième égalité tient compte des équations de balance globale. Elle reçoit l’in-
terprétation suivante : supposons que la distribution initiale soit π, auquel cas pour tout
n ≥ 0, tout i ∈ E,
P (Xn = i) = π(i).
Alors la formule de rétrodiction de Bayes donne
P (Xn+1 = i | Xn = j)P (Xn = j)
P (Xn = j | Xn+1 = i) = ,
P (Xn+1 = i)

c’est-à-dire, au vu de (8.10),

P (Xn = j | Xn+1 = i) = qji .

On voit que Q est la matrice de transition de la chaı̂ne quand on “retourne le temps”.

L’observation qui suit est promue au rang de théorème à cause de son efficacité.
8.1. LA MATRICE DE TRANSITION 217

Théorème 8.1.7 Soit P une matrice stochastique indexée par l’ensemble dénombrable
E, et soit π une distribution de probabilité positive sur E. Si la matrice Q indexée par
E et définie par (8.10) est une matrice stochastique (la somme de chacune des lignes
est égale à 1), alors π est une distribution stationnaire de P.

Démonstration. Pour i ∈ E fixé, on somme les égalités (8.10) par rapport à j ∈ E, ce

qui donne  
π(i)qij = π(j)pji .
j∈E j∈E

Mais le membre de gauche de cette égalité égale π(i) j∈E qij = π(i), et donc, pour tout
i ∈ E, 
π(i) = π(j)pji .
j∈E

Définition 8.1.3 On appelle réversible toute chaı̂ne de Markov de distribution initiale

π (une distribution stationnaire) positive telle que pour tout i, j ∈ E,

π(i)pij = π(j)pji . (8.11)

Dans ce cas, qij = pij , et donc la chaı̂ne et la chaı̂ne retournée ont la même distribution
puisque celle-ci est entièrement déterminée par la distribution initiale et la matrice de
transition. Les équations (8.11) sont appelées les équations de balance detaillée. Le
résultat suivant est un corollaire immédiat du Théorème 8.1.7.

Théorème 8.1.8 Soit P une matrice de transition sur E, et soit π une distribution de
probabilité sur E. Si pour tout i, j ∈ E, les équations de balance détaillée (8.11) sont
vérifiées, alors π est une distribution stationnaire de P.

Exemple 8.1.10: L’urne d’Ehrenfest, take 3. (suite des Exemples 8.1.3 et 8.1.8)
On rappelle qu’on avait obtenu l’expression

1 N
π(i) =
2N i
pour la distribution stationnaire. La vérification des équations de balance détaillée

π(i)pi,i+1 = π(i + 1)pi+1,i

est immédiate. L’urne d’Ehrenfest est donc réversible.

Exemple 8.1.11: Marche aléatoire sur un graphe. Soit un graphe non orienté où
on note E l’ensemble de ses sommets, ou nœuds. Soit di le nombre d’arêtes adjacentes
218 CHAPITRE 8. CHAÎNES DE MARKOV

au sommet i. Transformons ce graphe en un graphe orienté en décomposant chacune de

ses arêtes en deux arêtes orientées de directions opposées, et faisons en un graphe de
transition en associant à l’arête orientée de i vers j la probabilité de transition d1i .
On supposera que di > 0 pour tout état i (pas de nœud isolé). Une distribution
stationnaire (en fait, la distribution stationnaire comme nous le verrons bientôt) est
donnée par
di
π(i) =  .
j∈E dj

Pour cela on utilise le Théorème 8.1.8, en faisant le pari que la chaı̂ne est réversible. Il
nous faut juste vérifier que
1 1
π(i) = π(j) ,
di dj
ce qui est bien le cas.

1 1 1
3
1
1 2

1 1
2 4 2 2 2 4
1 1
3 2
1
3
3 3

Marche aléatoire sur un graphe

Communication
Les propriétés que l’on va définir dans cette fin de section (communication et période)
sont purement topologiques, en ce sens qu’elles concernent le graphe de transition “nu”,
c’est-à-dire sans les étiquettes indiquant les probabilités de transition.

Définition 8.1.4 L’état j est dit accessible depuis l’état i s’il existe un entier M ≥ 0
tel que pij (M ) > 0. En particulier, un état i est toujours accessible depuis lui-même,
puisque pii (0) = 1. Les états i et j sont dits communiquer si i est accessible depuis j et
si j est accessible depuis i. On note ceci i ↔ j.

Pour M ≥ 1, pij (M ) = i1 ,...,iM −1 pii1 · · · piM −1 j , et donc pij (M ) > 0 si et seulement
si il existe au moins un chemin i, i1 , . . . , iM −1 , j de i à j tel que

pii1 pi1 i2 · · · piM −1 j > 0,

8.1. LA MATRICE DE TRANSITION 219

ou, de manière équivalente, si il existe un chemin orienté de i vers j dans le graphe de

transition G. On vérifie immédiatement que

i↔i (reflexivité),
i↔j⇒j↔i (symétrie),
i ↔ j, j ↔ k ⇒ i ↔ k (transivité).

Donc la relation de communication (↔) est une relation d’équivalence. Elle engendre
une partition de l’espace d’état E en classes d’équivalences appelées classes de commu-
nication.

Définition 8.1.5Un état i tel que pii = 1 est dit fermé. Plus généralement, un ensemble
C d’états tel que j∈C pij = 1 pour tout i ∈ C est dit fermé.

3 5 7

1 4

2 6 8

Un graphe de transition avec 3 classes de communications

Exemple 8.1.12: Un graphe de transition. Le graphe de transition de la figure

ci-dessous a trois classes de communication : {1, 2, 3, 4}, {5, 7, 8}, et {6}. L’état 6 est
fermé. La classe de communication {5, 7, 8} n’est pas fermée, mais l’ensemble {5, 6, 7, 8}
l’est.
On observe sur cet exemple qu’il peut y avoir des arêtes orientées reliant deux classes
de communication différentes Ek et E . Cependant, toutes les arêtes orientées entre deux
classes de communication données ont la même orientation, toutes de Ek à E ou toutes
de E à Ek .

Définition 8.1.6 S’il n’y a qu’une seule classe de communication, la chaı̂ne, sa matrice
de transition et son graphe de transition sont dits irréductibles.
220 CHAPITRE 8. CHAÎNES DE MARKOV

Période
Considérons la marche aléatoire sur Z (Exemple 8.1.1). Comme 0 < p < 1, elle est
irréductible. On observe que E = C0 + C1 , où C0 et C1 , l’ensemble des entiers relatifs
pairs et impairs respectivement, ont la propriété suivante. Si on part de i ∈ C0 (resp., C1 ),
on ne peut se rendre en une seule étape que dans un état j ∈ C1 (resp., C0 ). La chaı̂ne
passe alternativement d’une classe à l’autre. En ce sens, la chaı̂ne a un comportement
périodique, correspondant à la période 2. Voici la définition exacte.

Définition 8.1.7 La période di de l’état i ∈ E est par définition,

di = pgcd{n ≥ 1 ; pii (n) > 0},

avec la convention di = +∞ s’il n’y a pas d’indice n ≥ 1 tel que pii (n) > 0 (on ne revient
pas en i). Si di = 1, l’état i est dit apériodique.

Théorème 8.1.9 Si les états i et j communiquent, ils ont la même période.

Démonstration. Comme i et j communiquent, il existe des entiers M et N tels que

pij (M ) > 0 et pji (N ) > 0. Pour tout k ≥ 1,

pii (M + nk + N ) ≥ pij (M )(pjj (k))n pji (N )

(en effet, un chemin tel que X0 = i, XM = j, XM +k = j, . . . , XM +nk = j, XM +nk+N = i

est un des moyens parmi d’autres d’aller de i à i en M + nk + N étapes).
Donc, pour tout k ≥ 1 tel que pjj (k) > 0, on a pii (M + nk + N ) > 0 pour tout n ≥ 1.
Par conséquent, di divise M + nk + N pour tout n ≥ 1, et en particulier, di divise k. On
a donc montré que di divise tout k tel que pjj (k) > 0, et en particulier, di divise dj . Par
symétrie, dj divise di , et donc, finalement di = dj . 

Définition 8.1.8 Si la chaı̂ne est irréductible, la période d commune à tous les états
est appelée la période de P, ou de la chaı̂ne. Si d = 1, la matrice de transition et la
chaı̂ne sont dites apériodiques.

Théorème 8.1.10 Soit P une matrice stochastique irréductible, de période d. Alors,

pour tous états i, j ∈ E il existe des entiers (dépendant de i, j) m ≥ 0 et n0 ≥ 0 tels que

pij (m + nd) > 0, pour tout n ≥ n0 .

Démonstration. Il suffit de prouver le théorème pour i = j. En effet, il existe m tel que

pij (m) > 0, parce que j est accessible depuis i, la chaı̂ne étant irreductible, et donc, si
pour un n0 ≥ 0 on a pjj (nd) > 0 pour tout n ≥ n0 , alors pij (m+nd) > pij (m)pjj (nd) > 0
pour tout n ≥ n0 .
8.1. LA MATRICE DE TRANSITION 221

Le reste de la preuve découle d’un résultat classique de la théorie des nombres : tout
ensemble A d’entiers positifs qui est fermé par addition et de pgcd d (comme c’est bien
le cas pour A = {k ≥ 1; pjj (k) > 0}) contient tous les multiples de d, sauf peut-être un
nombre fini d’entre eux. En d’autres termes, dans le cas qui nous intéresse, il existe n0
tel que n > n0 entraı̂ne pjj (nd) > 0. 

Au vu du résultat précédent, il est clair que pour une cmh irréductible de période d, on
peut trouver une unique partition de E en d classes C0 , C1 , . . ., Cd−1 telles que pour
tout k, 0 ≤ k ≤ d, et tout i ∈ Ck ,

pij = 1,
j∈Ck+1

où par convention Cd = C0 . Les classes C0 , C1 , . . . , Cd−1 sont les classes cycliques.
Considérons une cmh irréductible de période d dont les classes cycliques sont C0 ,
C1 ,. . . ,Cd . En renumérotant les états de E si nécessaire, la matrice de transition a la
structure de blocs ci-dessous (où on a choisi d = 4 pour être explicite),

C0 C1 Cd−2 Cd−1

Cycles

C0 C1 C2 C3
 
C0 0 A0 0
C1 
 0 0 A1 0 ,
P=
C2  0 0 0 A2 
C3 A3 0 0 0

et donc P2 , P3 , et P4 ont aussi une structure de blocs correspondant aux classes C0 ,

C1 , C2 , C3 :
   
0 0 B0 0 0 0 0 D0
 0 0 0 B1   D1 0 0 0 
P2 =  B2 0
 P3 =   ,
0 0   0 D2 0 0 
0 B3 0 0 0 0 D3 0
222 CHAPITRE 8. CHAÎNES DE MARKOV

et finalement  
E0 0 0 0
 0 E1 0 0 
P4 = 
 0
.
0 E2 0 
0 0 0 E3

On observe deux phénomènes : le décalage des blocs et le fait que P4 est bloc-diagonale.
Ceci est évidemment général : Pd est bloc-diagonale relativement aux classes cycliques
C0 , C1 , . . . , Cd−1 . La matrice de transition à d étapes, Pd , est aussi une matrice stochas-
tique, et les classes cycliques sont des classes de communication de Pd comme le montre
la forme bloc-diagonale de cette dernière matrice.

8.2 Récurrence
Cette section et la suivante sont consacrées à l’étude du comportement à long terme
des chaı̂nes de Markov homogènes. Les notions importantes sont celles d’état récurrent
et d’état transitoire. Soit {Xn }n≥0 une cmh de matrice de transition P. On définit le
temps de retour en i par
Ti = inf{n ≥ 1; Xn = i},
avec la convention usuelle : inf ∅ = ∞ (Ici : Ti = ∞ si Xn = i pour tout n ≥ 1).

Définition 8.2.1 On dit que l’état i est récurrent si Pi (Ti < ∞) = 1. Un état i
récurrent est dit récurrent positif si de plus Ei [Ti ] < ∞, récurrent nul si Ei [Ti ] = ∞.
Un état qui n’est pas récurrent est dit transitoire.

Pour un état i fixé, notons {τk }k≥1 la suite des temps de retour successifs dans l’état i.
Formellement :
τ 1 = Ti
...
τk+1 = inf{n > τk ; Xn = i}
...

Le résultat suivant est intuitif. Sa démonstration fait l’objet de l’Exercice 8.5.14.

Théorème 8.2.1 Sachant que τk < ∞, le processus {Xτk +n }n≥0 est une cmh de ma-
trice de transition P indépendante de {Xn∧τk }n≥0 .
En particulier, si l’état i est récurrent, les “cycles” {Xn+τk }0≤n<τk+1 , k ≥ 1, sont
indépendants et identiquement distribués.
Notons fji = Pj (Ti < ∞) la probabilité de retourner en i en partant de j, et notons
∞

Ni = 1{Xn =i}
n=1
8.2. RÉCURRENCE 223

le nombre total de visites en i à partir de n = 1. On a

Pj (Ni = 0) = 1 − fji

et, lorsque r ≥ 1,
Pj (Ni = r) = fji × (fi i)r−1 × (1 − fii ).

En effet, en utilisant le Théorème 8.2.1, cette probabilité est égale à la probabilité de

visiter i au moins une fois (fji ) multiplié par la probabilité de visiter i encore r − 1
fois (fii )r−1 ) en succession, et enfin après la r-ème visite, de ne plus jamais revenir en i
(probabilité 1 − fii ). En particulier :

Pi (Ni = r) = (fii )r × (1 − fii ).

On en déduit que :

(a) Si fii = 1, Pi (Ni = r) = 0 pour tout r ≥ 0, et donc Pi (Ni = ∞) = 1, et bien entendu

Ei [Ni ] = ∞.

(b) Si fii < 1, on a ∞ r=0 Pi (Ni = r) = 1, et donc Pi (Ni = ∞) = 0 ; d’autre part un
fii
calcul élémentaire donne : Ei [Ni ] = 1−f ii
< ∞.

En particulier :
Théorème 8.2.2 Pour que l’état i soit récurrent, il faut et il suffit que
∞

pii (n) = ∞.
n=1

Démonstration. Les remarques précédant l’énoncé du théorème montrent que fii =

1 ⇔ Ei [Ni ] = ∞. D’autre part,
& ∞
'

Ei [Ni ] = Ei 1{Xn =i}
n=1
∞

= Ei [1{Xn =i} ]
n=1
∞ ∞

= Pi (Xn = i) = pii (n) .
n=1 n=1


224 CHAPITRE 8. CHAÎNES DE MARKOV

Le critère de récurrence ci-dessus s’appelle le critère de la matrice potentiel car

 ∞
n=0 pii (n) est le terme (i, i) de la matrice potentiel
∞

G= Pn .
n=0

Exemple 8.2.1: Marche aléatoire sur Z, take 2. (suite de l’Exercice 8.1.1) Comme
0 < p < 1, cette chaı̂ne est irréductible et tous ses états sont de même nature (transitoires
ou récurrents). Considérons par exemple l’état 0. On a p00 (2n + 1) = 0 et
(2n)! n
p00 (2n) = p (1 − p)n .
n!n!
√
D’après la formule d’équivalence de Stirling (n! ∼ (n/e)n 2πn), la quantité ci-dessus
est équivalente à
[4p(1 − p)]n
√ . (8.12)
πn

La nature de la série ∞ n=0 p00 (n) est donc la même que celle de la série de terme général
(8.12). Si p = 2 , auquel cas 4p(1 − p) < 1, cette dernière converge, et si p = 12 , auquel
1

cas 4p(1 − p) = 1, elle diverge. Donc, la marche aléatoire sur Z est transiente si p = 21 ,
récurrente si p = 21 .

Les exemples où l’on peut utiliser le critère de la matrice potentiel pour vérifier si un
état est récurrent ou non sont rares. Ce critère va cependant nous servir à démontrer
l’important résultat suivant, à savoir que la récurrence est une “propriété de classe” (de
communication).
Théorème 8.2.3 Soit une cmh de matrice de transition P. Deux états qui commu-
niquent sont, soit tous deux récurrents, soit tous deux transitoires. En particulier, si P
est irréductible, les états sont soit tous récurrents, soit tous transitoires. La chaı̂ne (ou
sa matrice de transition) est alors dite, respectivement, récurrente, transiente.

Démonstration. Si i et j communiquent, il existe M et N tels que pij (M ) > 0 et

pji (N ) > 0. Posons α = pij (M )pji (N ) > 0. On a l’inégalité
pii (M + n + N ) ≥ pij (M )pjj (n)pji (N ) = αpjj (n) .
(En effet, le premier membre est la probabilité d’aller de i en j en exactement M + n + N
étapes, tandis que le second membre est la probabilité d’aller de i en j en exactement M +
n + N étapes, mais de façon particulière, avec la contrainte que XM = j et XM +n = j.)
De même :
pjj (N + n + M ) ≥ αpii (n).
 ∞
Donc, si i et j communiquent, les séries ∞ n=1 pii (n) et n=1 pjj (n) ont le même com-
portement. Les états i et j sont donc, d’après le Théorème 8.2.2, ou bien tous deux
transitoires, ou bien tous deux récurrents. 
8.2. RÉCURRENCE 225

Critère de la probabilité stationnaire

Le but que l’on se fixe maintenant est de démontrer un critère plus maniable que celui
de la matrice potentiel, à savoir, le critère de la probabilité stationnaire, qui dit qu’une
cmh irréductible est récurrente positive si et seulement si elle admet une distribution
stationnaire.
La démonstration passe par des préliminaires concernant la mesure invariante d’une
cmh irréductible récurrente.

Définition 8.2.2 Un vecteur non nul x = {xi }i∈E de coordonnées non négatives est
appelé mesure invariante de la matrice stochastique P = {pij }i,j∈E si pour tout i ∈ E,

xi = xj pji . (8.13)
j∈E

(En notation abrégée, 0 ≤ x < ∞ et xT P = xT .)

Théorème 8.2.4 A. Soit P la matrice de transition d’une cmh irréductible récurrente

{Xn }n≥0 . Soit 0 un état arbitraire et soit T0 le temps de retour en 0. On définit, pour
tout i ∈ E, la quantité &T '
0

x i = E0 1{Xn =i} . (8.14)

n=1

Alors, pour tout i ∈ E,

0 < xi < ∞, (8.15)
et x est une mesure invariante de P.
B. La mesure invariante d’une matrice stochastique irréductible récurrente est unique à
une constante multiplicative près.
C. Une cmh irréductible récurrente est récurrente positive si et seulement si sa mesure
invariante x vérifie 
xi < ∞. (8.16)
i∈E

Démonstration.
A. Faisons deux observations préliminaires. Premièrement, quand 1 ≤ n ≤ T0 , Xn = 0
si et seulement si n = T0 , et donc
x0 = 1.
Deuxièmement,
T0 T0
  T0
   
1{Xn =i} = 1{Xn =i} = 1 = T0 ,
i∈E n=1 n=1 i∈E n≥1
226 CHAPITRE 8. CHAÎNES DE MARKOV

et donc 
xi = E0 [T0 ]. (8.17)
i∈E

Passons à la démonstration de (8.13). Pour cela, on introduit la quantité

0 p0i (n) := E0 [1{Xn =i} 1{n≤T0 } ] = P0 (X1 = 0, · · · , Xn−1 = 0, Xn = i).

C’est la probabilité que, partant de l’état 0, on visite i au temps n sans être au préalable
retourné en 0. On a  

x i = E0  1{Xn =i} 1{n≤T0 }  ,
n≥1

et donc, 
xi = 0 p0i (n). (8.18)
n≥1

On observe que
0 p0i (1) = p0i .
D’autre part, en utilisant la méthode d’analyse à un pas, pour tout n ≥ 2,

0 p0i (n) = 0 p0j (n − 1)pji . (8.19)
j
=0

En faisant la somme de toutes ces égalités, et en tenant compte de (8.18), on obtient


xi = p0i + xj pji ,
j
=0

c’est-à-dire (8.13), puisque x0 = 1.

Ensuite, nous montrons que xi > 0 pour tout i ∈ E. En effet, en itérant (8.13), on a
xT = xT Pn , c’est-à-dire, puisque x0 = 1,
 
xi = xj pji (n) = p0i (n) + xj pji (n).
j∈E j
=0

Si xi était nul pour un i ∈ E, i = 0, cela impliquerait que p0i (n) = 0 pour tout n ≥ 0, et
donc que 0 et i ne communiquent pas, en contradiction avec l’hypothèse d’irréductibilité.
Il reste à montrer que xi < ∞ pour tout i ∈ E. Comme précédemment, on trouve que

1 = x0 = xj pj0 (n)
j∈E

pour tout n ≥ 1, et donc, si xi = ∞ pour un i, nécessairement pi0 (n) = 0 pour tout

n ≥ 1, et ceci contredit à nouveau l’hypothèse d’irréductibilité.
8.2. RÉCURRENCE 227

B. Dans la preuve de la partie A, on a montré que pour toute mesure invariante y d’une
matrice stochastique irréductible, yi > 0 pour tout i ∈ E. On peut donc définir, pour
tout i, j ∈ E, la matrice Q par
yi
qji = pij . (8.20)
yj
  y
C’est une matrice de transition, puisque i∈E qji = y1j i∈E yi pij = yjj = 1. Le terme
général de Qn est
yi
qji (n) = pij (n). (8.21)
yj
En effet, en supposant (8.21) vraie pour n,
  yk yi
qji (n + 1) = qjk qki (n) = pkj pik (n)
yj yk
k∈E k∈E
yi  yi
= pik (n)pkj = pij (n + 1),
yj yj
k∈E

et (8.21) suit par induction.

La matrice Q est irréductible, puisque P est irréductible. En effet, auvu de (8.21),
qji (n) > 0 si et seulement si pij (n) > 0. Aussi, pii (n) = qii (n), et donc n≥0 qii (n) =
n≥0 ii (n), et ceci garantit que Q est récurrente d’après le critère de la matrice po-
p
tentiel. Notons gji (n) la probabilité, relative à la chaı̂ne de matrice de transition Q, de
retourner dans l’état i pour la première fois à l’étape n en partant de j. L’analyse à un
pas donne : 
gi0 (n + 1) = qij gj0 (n) . (8.22)
j
=0

En multipliant les deux membres par yi et en utilisant (8.20), on obtient


yi gi0 (n + 1) = (yj gj0 (n))pji .
j
=0

Rappelons que 0 p0i (n + 1) = j
=0 0 p0j (n)pji , ou encore :

y0 0 p0i (n + 1) = (y0 0 p0j (n))pji .
j
=0

On voit donc que les suites {y0 0 p0i (n)} et {yi gi0 (n)} vérifient la même équation
de récurrence. Leurs premiers termes (n = 1), respectivement y0 0 p0i (1) = y0 p0i et
yi gi0 (1) = yi qi0 , sont égaux, d’après (8.20). Donc, pour tout n ≥ 1,
yi
0 p0i (n) = gi0 (n).
y0

En sommant par rapport à n ≥ 1 et en utilisant l’égalité n≥1 gi0 (n) = 1 (Q est
récurrente), on obtient le résultat annoncé : xi = yy0i .
228 CHAPITRE 8. CHAÎNES DE MARKOV

C. La preuve découle immédiatement de l’égalité (8.17) et de la définition de la récurrence

positive. 

Voici enfin le critère de récurrence positive de la probabilité stationnaire.

Théorème 8.2.5 1. Une cmh irréductible est récurrente positive si et seulement si elle
admet une probabilité stationnaire π. Dans ce cas, la probabilité stationnaire est unique,
et π(i) > 0 pour tout i ∈ E.
2. Soit π l’unique distribution stationnaire d’une chaı̂ne irréductible récurrente positive,
et soit Ti le temps de retour en i. Alors

π(i)Ei [Ti ] = 1. (8.23)

3. Toute cmh irréductible d’espace d’état fini est récurrente positive.

Démonstration.
1. La partie directe est une conséquence immédiate du Théorème 8.2.4. Pour la
réciproque, supposons l’existence d’une distribution stationnaire π. En itérant π T =
π T P, on obtient π T = π T Pn , c’est-à-dire, pour tout i ∈ E,

π(i) = π(j)pji (n).
j∈E

Si la chaı̂ne était transiente, on aurait, pour tous états i, j,

lim pji (n) = 0.

n↑∞

(En effet, limn↑∞ pji (n) = limn↑∞ Ej [1{Xn =i} ]. D’autre part, limn↑∞ 1{Xn =i} = 0 (j est
transient) et 1{Xn =i} ≤ 1, et donc, par convergence dominée, limn↑∞ Ej [1{Xn =i} ] = 0.)
Puisque pji (n) est uniformément (en j et n) bornée par 1, on a, par convergence dominée
à nouveau, 
 
π(i) = lim π(j)pji (n) = π(j) lim pji (n) = 0.
n↑∞ n↑∞
j∈E j∈E

Ceci contredit i∈E π(i) = 1. La chaı̂ne ne peut donc être que récurrente, et d’après le
Théorème 8.2.4, partie C, elle est récurrente positive.
La distribution stationnaire π d’une chaı̂ne irréductible récurrente positive est unique
(d’après le Théorème 8.2.4, partie B, et le fait que le seul choix du facteur multiplicatif
est 1). Aussi, on rappelle que π(i) > 0 pour tout i ∈ E (Théorème 8.2.4, partie A).
2. Cette égalité est une conséquence directe de l’expression (8.14) de la mesure invariante.
En effet, π est obtenue par normalisation de x : pour tout i ∈ E,
xi
π(i) =  ,
j∈E xj
8.2. RÉCURRENCE 229

et en particulier, pour i = 0, en se rappelant que x0 = 1 et en utilisant (8.17),

x0 1
π(0) =  = .
j∈E xj E0 [T0 ]
L’état 0 ne jouant pas un rôle spécial dans cette analyse, (8.23) est vraie pour tout i ∈ E.
3. On prouve d’abord la récurrence. Si la chaı̂ne était transiente, alors, pour tout i, j ∈ E,
lim pij (n) = 0,
n↑∞

et donc, puisque l’espace d’état est fini,


lim pij (n) = 0.
n↑∞
j∈E

Mais pour tout n, 

pij (n) = 1,
j∈E
une contradiction. Donc, la chaı̂ne est récurrente. D’après le Théorème 8.2.4 elle ad-
met une mesure invariante x. Puisque E est fini, i∈E xi < ∞, et donc la chaı̂ne est
récurrente positive, d’après le Théorème 8.2.4, partie C. 

Exemple 8.2.2: processus de naissance et de mort, II. Le modèle est le même

que celui de l’Exemple 8.1.9, sauf que l’espace d’état est E = N. Les mêmes calculs que
précédemment conduisent à l’expression (8.8). Pour que cette solution soit une probabi-
lité, on doit avoir π(0) > 0. Aussi en écrivant que ∞ i=1 π(i) = 1, on obtient
 
 1 ∞
p1 p2 · · · pj 
π(0) 1 + + = 1. (8.24)
 q1 q1 q2 · · · qj+1 
j=1

Donc une distribution stationnaire existe si et seulement si

∞
p1 p2 · · · pj
< ∞. (8.25)
q1 q2 · · · qj+1
j=1

Dans ce cas π(i) est donné par (8.8), où π(0) est déterminé par (8.24).
Un cas particulier important est
E = N, pi = p, qi = 1 − p, ri = 0
où 0 < p < 1. Il s’agit d’une marche aléatoire du type de l’Exemple 8.1.1 où l’état 0 est
“réfléchissant”. La condition (8.25) se lit
  p i
< ∞,
1−p
j

c’est-à-dire : la chaı̂ne est récurrente positive si et seulement si p < 21 .

230 CHAPITRE 8. CHAÎNES DE MARKOV

Exemple 8.2.3: L’atelier de réparation. Durant le jour n, Zn+1 machines tombent

en panne, et elles sont admises dans l’atelier de réparation dans la journée n + 1. Chaque
jour, une machine parmi celles qui attendent est réparée. Donc, en notant Xn le nombre
de machines dans l’atelier au jour n,

Xn+1 = (Xn − 1)+ + Zn+1 , (8.26)

oùa+ = max(a, 0). En particulier, si {Zn }n≥1 est une suite iid indépendante de l’état
initial X0 , alors {Xn }n≥0 est une cmh. En termes de la distribution de probabilité

P (Z1 = k) = ak , k ≥ 0,

la matrice de transition de cette chaı̂ne est

 
a0 a1 a2 a3 ···
 a0 a1 a2 a3 ··· 
 
 ··· 
P =  0 a0 a1 a2 .
 0 0 a0 a1 ··· 
 
.. .. .. ..
. . . .
En effet, la formule (8.6) donne,

pij = P ((i − 1)+ + Z1 = j) = P (Z1 = j − (i − 1)+ ) = aj−(i−1)+ .

Nous allons montrer qu’une condition nécessaire et suffisante d’irréducibilité est que
P (Z1 = 0) > 0 (a0 > 0) et P (Z1 ≥ 2) > 0 (a0 + a1 < 1).
L’équation de récurrence (8.26) nous permet de faire les observations suivantes. Si
a0 = 0, alors Xn+1 ≥ Xn et il y a donc une probabilité nulle d’aller de i à i − 1 quel que
soit i ≥ 1. Si a0 + a1 = 1, alors Xn+1 ≤ Xn et il y a donc une probabilité nulle d’aller
de i à i + 1 quel que soit i ≥ 0. Donc les deux conditions a0 > 0 et a0 + a1 < 1 sont
nécéssaires pour l’irréductibilité.
Elles sont également suffisantes. En effet, s’il existe k ≥ 2 tel que P (Zn+1 = k) > 0,
alors on peut aller de n’importe quel i > 0 à i + k − 1 > i ou de i = 0 à k > 0 avec une
probabilité positive. De plus, si P (Zn+1 = 0) > 0, on peut aller de i > 0 à i − 1 avec
une probabilité positive. En particulier, on peut aller de i à j < i avec une probabilité
positive. Donc, pour aller de i à j ≥ i, on peut procéder par sauts vers le haut de
hauteur strictement positive, pour atteindre un état l ≥ i, et ensuite, dans le cas où
l > i, descendre par sauts d’une unité vers le bas de l à i. Tout ceci avec une probabilité
positive.
Supposons que la chaı̂ne soit irréductible récurrente positive, avec la distribution
stationnaire π. Soit z un nombre complexe de module ≤ 1. De (8.26), on tire
+ +
,
z Xn+1 +1 = z (Xn −1) +1 z Zn+1
 
= z Xn 1{Xn >0} + z1{Xn =0} z Zn+1
 
= z Xn − 1{Xn =0} + z1{Xn =0} z Zn+1 ,
8.2. RÉCURRENCE 231

et donc
zz Xn+1 − z Xn z Zn+1 = (z − 1)1{Xn =0} z Zn+1 .
Comme Xn et Zn+1 sont indépendantes, E[z Xn z Zn+1 ] = E[z Xn ]gZ (z), où gZ (z) est la
fonction génératrice de Zn+1 , et E[1{Xn =0} z Zn+1 ] = π(0)gZ (z), où π(0) = P (Xn = 0).
Donc,
zE[z Xn+1 ] − gZ (z)E[z Xn ] = (z − 1)π(0)gZ (z).
Si on est en régime stationnaire, alors E[z Xn+1 ] = E[z Xn ] = gX (z), et donc :

gX (z) (z − gZ (z)) = π(0)(z − 1)gZ (z). (8.27)

∞ i
Ceci nous donne gX (z) = i=0 π(i)z , du moins si on dispose de π(0). Pour obtenir
π(0), on dérive (8.27) :

   
gX (z) (z − gZ (z)) + gX (z) 1 − gZ (z) = π(0) gZ (z) + (z − 1)gZ (z) , (8.28)

et on fait z = 1, pour obtenir, en tenant compte des identités gX (1) = gZ (1) = 1 et

gZ (1) = E[Z],
π(0) = 1 − E[Z].
Comme π(0) doit être non négative, ceci conduit à la condition nécessaire de récurrence
positive : E[Z] ≤ 1. En fait, on a nécessairement E[Z] < 1. En effet, si E[Z] = 1, ce qui
implique π(0) = 0, il découle de (8.27) que

gX (x)(x − gZ (x)) = 0

pour tout x ∈ [0, 1]. Mais comme la chaı̂ne est supposée irréductible, le cas Zn+1 ≡ 1
(c’est-à-dire, gZ (x) ≡ x) est exclus et l’équation x − gZ (x) = 0 a seulement x = 1 comme
solution quand gZ (1) = E[Z] ≤ 1. Donc gX (x) ≡ 0 pour tout x ∈ [0, 1), et en conséquence
gX (z) ≡ 0 sur {|z| < 1} (une fonction analytique sur un ouvert ne peut avoir de points
d’accumulation de zéros à l’intérieur de cet ouvert, sauf si elle est identiquement nulle).
Ceci mène à une contradiction puisque la fonction génératrice d’une variable à valeurs
entières ne peut être identiquement nulle.
On a donc démontré qu’une condition nécessaire de récurrence positive est E[Z] < 1.
Nous allons voir que c’est aussi une condition suffisante. On commence par vérifier que
la condition E[Z] < 1 entraı̂ne la récurrence. Il suffit de montrer que la probabilité de
l’événement A = “non retour en 0 en partant de 0” est nulle. En effet dans A, pour
tout n,
n
Xn = 1 + (Zk − 1)  1
k=1
et en particulier n
k=1 Zk
− 1 > 0,
n
ce qui donne, en faisant tendre n vers l’infini, d’après la loi forte des grands nombres,
E[Z] ≥ 1. Une contradiction.
232 CHAPITRE 8. CHAÎNES DE MARKOV

Supposons la récurrence, c’est-à-dire, supposons que le temps de retour T0 est presque

sûrement fini. On a l’égalité :
T0
Zn = (T0 − 1). (8.29)
n=1
Observons que

E [Zn 1n≤T0 ] = E [Zn ] − E [Zn 1n>T0 ]

= E [Zn ] − E [Zn ] E [1n>T0 ]
= E [Zn ] E [1n≤T0 ] ,

où on a utilisé le fait que l’événement {n > T0 }, qui ne dépend que de Z1 , . . . , Zn−1 , est
indépendant de Zn . On a donc, à partir de (8.29)
&∞ '

E0 [T0 ] = 1 + E0 Zn 1n≤T0
n=1
∞

=1+ E0 [Zn 1n>T0 ]
n=1
∞
=1+ E0 [Zn ] E [1n≤T0 ]
n=1
∞

= 1 + E [Z1 ] E0 [1n≤T0 ]
n=1
& ∞
'

= 1 + E [Z1 ] E0 1n≤T0
n=1
= 1 + E [Z1 ] E0 [T0 ] ,

et donc, si E[Z] < 1 (en particulier, la chaı̂ne est récurrente),

E0 [T0 ] = (1 − E [Z1 ])−1 < ∞ ,

et donc la chaı̂ne est récurrente positive.

Si E[Z] = 1 (en particulier, la chaı̂ne est récurrente), on ne peut avoir E0 [T0 ] < ∞,
car alors on aurait E0 [T0 ] = 1 + E0 [T0 ]. La chaı̂ne récurrente est donc dans ce cas
récurrente nulle.
Reste à examiner le cas E[Z] > 1. On sait que cela exclue la récurrence positive. Il
se trouve qu’en fait, la chaı̂ne est alors transiente, mais nous ne le démontrerons pas ici.
En résumé, sous la condition d’irréductiblité (P (Z = 0) > 0 et P (Z ≥ 2) > 0) :
A. Si E[Z] < 1, la chaı̂ne est récurrente positive et la fonction génératrice de sa distri-
bution stationnaire est
∞
 (z − 1)gZ (z)
π(i)z i = (1 − E[Z]) .
z − gZ (z)
i=0
8.2. RÉCURRENCE 233

B. Si E[Z] = 1, la chaı̂ne est récurrente nulle.

C. Si E[Z] > 1, la chaı̂ne est transiente.

Exemple 8.2.4: Instabilité du protocole aloha. Le protocole aloha est une

méthode d’accès à un canal satellite. C’est un protocole distribué, en ce sens que les uti-
lisateurs du canal ne se concertent pas pour éviter les collisions (plus d’un message trans-
mis en même temps, auquel cas aucun de ces messages n’est considéré comme transmis,
et chacun des messages en collision redemande la transmission à un temps ultérieur, de
manière suffisamment intelligente — évidemment pas de retransmission immédiate). Plus
précisément, on considère le protocole aloha avec fenêtres de transmission périodiques.
Ce protocole impose les règles suivantes (voir aussi la figure ci-dessous) :
(i) Les transmissions et retransmissions des messages ont lieu dans des intervalles de
temps équidistants, les slots, dont la durée est supérieure à celle du temps nécessaire
pour transmettre un message. (Ici un message est une suite de longueur fixe de symboles
binaires).
(ii) Les messages qui au début d’un slot sont en attente de retransmission demandent leur
retransmission indépendamment les uns des autres chacun avec la probabilité ν ∈ (0, 1).
(iii) Les messages frais—ceux qui se présentent pour la première fois— tentent
immédiatement de passer.

message frais
message en attente, non autorisé à retransmettre
message en attente, autorisé à retransmettre

transmission réussie
Le protocole aloha

Soit Xn le nombre de messages en attente de retransmission au début du slot n. La

probabilité pour que i parmi Xn = k messages en attente de retransmission demandent
la retransmission dans le slot suivant est donc
234 CHAPITRE 8. CHAÎNES DE MARKOV

k i
bi (k) = ν (1 − ν)k−i .
i
Soit An le nombre de requêtes nouvelles dans le n-ème slot. La suite {An }n≥0 est supposée
iid avec la distribution
P (An = j) = aj .
La quantité
∞

λ = E[An ] = iai
i=1
est l’intensité de trafic. On suppose que 0 < a0 + a1 < 1, ce qui garantit que {Xn }n≥0
est une cmh irréductible. Sa matrice de transition est :

pij = b1 (i)a0 si j = i − 1,
= [1 − b1 (i)]a0 + b0 (i)a1 si j = i,
= [1 − b0 (i)]a1 si j = i + 1,
= aj−i si j ≥ i + 2.

La preuve consiste à comptabiliser les possibilités. Par exemple, la première ligne cor-
respond à un parmi les i messages en attente (de transmission ou de retransmission) qui
réussit à passer, et pour cela il faut qu’il y ait soit pas de message nouveau (probabilité
a0 ) et un seul parmi les i messages en attente qui est admis à retransmettre (probabilité
b1 (i)). La seconde ligne correspond à un des deux événements suivants : (1), “pas de
nouveau message et zéro ou plus de deux requêtes de retransmission parmi les messages
en attente” et (2), “un nouveau message et zéro requête de retransmission parmi les
messages en attente”.
Le but de cet exemple est de démontrer que ce protocole n’est pas stable, en ce
sens que la cmh {Xn }n≥0 n’est pas récurrente positive. Pour cela, il suffit, d’après le
Théoreme 8.3.1 de contredire l’existence d’une distribution stationnaire π.
Si une telle distribution stationnaire existait, elle satisferait aux équations de balance
globale

π(i) = π(i){[1 − b1 (i)]a0 + b0 (i)a1 } + π(i − 1)[1 − b0 (i − 1)]a1

∞

+π(i + 1)b1 (i + 1)a0 + π(i − )a
=2

(où π(i) = 0 si i < 0). Posons

N

PN = π(i)
i=0
et faisons la somme des équations de balance globale de i = 0 à N . On obtient :
N

PN = π(N )b0 (N )a1 + π(N + 1)b1 (N + 1)a0 + a PN − ,
=0
8.3. COMPORTEMENT ASYMPTOTIQUE 235

qui donne à son tour :

N

PN (1 − a0 ) = π(N )b0 (N )a1 + π(N + 1)b1 (N + 1)a0 + a PN − .
=1
N ∞
Mais comme PN croit avec N et =1 a ≤ =1 a = 1 − a0 , nous avons
N

a PN − ≤ PN −1 (1 − a0 ),
=1

et donc

PN (1 − a0 ) ≤ π(N )b0 (N )a1 + π(N + 1)b1 (N + 1)a0 + PN −1 (1 − a0 ),

d’où il suit que

π(N + 1) 1 − a0 − b0 (N )a1
≥ .
π(N ) b1 (N + 1)a0
Faisant usage de la forme explicite des bi (k), on obtient

π(N + 1) (1 − a0 ) − (1 − ν)N a1
≥ .
π(N ) (N + 1)ν(1 − ν)N a0
Pour toutes les valeurs de ν ∈ (0, 1), le membre de droite de cette inégalité tend vers
l’infini, ce qui contredit ∞
N =1 π(N ) = 1 et les inégalités π(N ) > 0 que π doit vérifier
en tant que distribution stationnaire d’une cmh irréductible.

8.3 Comportement asymptotique

Convergence vers l’équilibre
Considérons une cmh irréductible et récurrente positive. En particulier, si la distri-
bution initiale est la distribution stationnaire, elle conserve cette distribution pour tous
les temps. La chaı̂ne est alors dite en régime stationnaire.
Quel est son comportement à long terme quand la distribution initiale est arbitraire ?
Le résultat fondamental est le suivant :
Théorème 8.3.1 Soit une cmh de matrice de transition P irréductible, récurrente
positive et apériodique. Alors, pour tout j ∈ E, et toute distribution initiale µ,

lim P (Xn = j) = π(j) ,

n↑∞

où π est la distribution stationnaire de la chaı̂ne.

Définition 8.3.1 Une cmh irréductible récurrente positive et apériodique est dite
ergodique.
236 CHAPITRE 8. CHAÎNES DE MARKOV

D
Supposons que l’on trouve un processus {Xn }n≥0 tel que Xn ∼ Xn pour tout n ≥ 0,
D
et un processus {Xn }n≥0 tel que Xn ∼ π pour tout n ≥ 0. Alors, le résultat sera démontré
si l’on peut prouver que

lim |P (Xn = i) − P (Xn = i)| = 0. (8.30)

n↑∞

Nous allons construire {Xn }n≥0 et {Xn }n≥0 pour que cette situation ait bien lieu. Nous
allons le faire de telle sorte qu’il existe un temps aléatoire presque sûrement fini τ tel
que Xn = Xn pour tout n ≥ τ . On montrera ci-dessous que, dans ce cas,

|P (Xn = i) − P (Xn = i)| ≤ P (τ > n). (8.31)

Alors, la finitude de τ entraı̂ne que limn↑∞ P (τ > n) = 0, et le résultat sera donc prouvé.
Voici la démonstration de (8.31) :

P (Xn = j) − P (Xn = j) = P (Xn = j, τ ≤ n) + P (Xn = j, τ > n)

− P (Xn = j, τ ≤ n) − P (Xn = j, τ > n)
= P (Xn = j, τ > n) − P (Xn = j, τ > n)
≤ P (Xn = j, τ > n)
≤ P (τ > n).

De même, P (Xn = j) − P (Xn = j) ≤ P (τ > n).

Il nous reste à construire {Xn }n≥0 et {Xn }n≥0 avec les propriétés annoncées.
(1) (2)
Théorème 8.3.2 Soit {Xn }n≥0 et {Xn }n≥0 deux cmh ergodiques indépendantes de
même matrice de transition P et de distributions initiales µ et ν, respectivement. Soit
(1) (2)
τ = inf{n ≥ 0; Xn = Xn }, avec τ = ∞ si les deux chaı̂nes ne se recoupent jamais.
Alors τ est en fait presque sûrement fini et, de plus, le processus {Xn }n≥0 défini par
 (1)
 Xn if n ≤ τ,
Xn = (2) (8.32)
Xn if n ≥ τ

(voir la figure ci-dessous) est une cmh de matrice de transition P.

(1) (2)
Démonstration. Considérons la cmh {Zn }n≥0 définie par Zn = (Xn , Xn ) ( chaı̂ne
produit), prenant ses valeurs dans E × E. Sa probabilité de transition de (i, k) à (j, )
en n étapes est pij (n)pk (n), elle est irréductible, et elle admet {π(i)π(j)}(i,j)∈E 2 comme
distribution stationnaire (voir l’Exercice 8.5.16, où le rôle de l’hypothèse d’apériodicité
est mis en évidence). D’après le critère de la distribution stationnaire, la chaı̂ne produit
est récurrente positive. En particulier, elle atteint la diagonale de E 2 en temps fini, et
donc P (τ < ∞) = 1.
Il reste à prouver que le processus {Xn }n≥0 défini par (8.32) est une cmh de matrice
de transition P. Ceci est fait dans l’Exercice 8.5.18. 
8.3. COMPORTEMENT ASYMPTOTIQUE 237

µ Xn
(1)

(2)
Xn
Xn

ν
0

Exemple 8.3.1: L’urne d’Ehrenfest, take 4. (suite des Exemples 8.1.3, 8.1.8 et
8.1.10) La célébrité du modèle d’Ehrenfest est due à l’éclaircissement qu’il apporte au
phénomène d’irréversibilité thermodynamique, un sujet de controverses du temps de
Boltzmann. Selon la théorie macroscopique de la thermodynamique de ce physicien, les
systèmes progressent d’une manière ordonnée vers l’équilibre thermodynamique.
Considérons, par exemple, un système de N particules gazeuses dans une boite divisée
en deux compartiments, A et B, séparés par une membrane fictive. Si à l’origine des
temps on place toutes les particules dans le compartiment A, ces particules vont se
redistribuer, et le système atteint l’équilibre, un état pour lequel les contenus deux
compartiments sont thermodynamiquement équivalents. Boltzmann disait qu’il existait
une flèche du temps en direction de l’entropie croissante, et en effet dans l’expérience de
diffusion modélisée par le modèle des Ehrenfest, l’équilibre thermodynamique correspond
à l’entropie maximale du système.
Boltzmann eut un redoutable contradicteur, un certain Zermelo, qui, au vu de la
réversibilité dans le temps des lois de la physique, doutait de la flèche du temps évoquée
par Boltzmann, ou du moins, demandait une explication. Sa position était renforcée par
d’irréfutables mathématiques, en particulier le théorème de récurrence de Poincaré qui
prédisait que si l’expérience débutait avec toutes les particules dans le compartiment A,
on les retrouverait toutes, tôt ou tard dans le compartiment d’origine. Comme chacun
sait, ce comportement n’est jamais observé dans la vie quotidienne, et on n’a jamais vu
le sucre dissous dans la tasse de café reprendre sa forme initiale.
La théorie de Boltzmann était mise à mal par ce type d’arguments. Les choses de-
vaient être clarifiées, et elles le furent par Tatiana et Paul Ehrenfest, dont le modèle
markovien permit de sauver tout l’édifice.
Ce modèle ne rentre pas dans les détails de la physique du phénomène de diffusion,
mais il en conserve les traits essentiels du point de vue de la physique statistique. C’est un
système réversible (la chaı̂ne de Markov est réversible) et il est récurrent, repassant une
infinité de fois dans n’importe quel état, comme par exemple celui où le compartiment A
est vide. L’irréversibilité du système consiste en ceci : en partant d’un état quelconque,
238 CHAPITRE 8. CHAÎNES DE MARKOV

la distribution au temps n converge vers la distribution stationnaire1 qui met pratique-

ment toute la masse sur les états proches du partage équilibré des particules entre les
deux compartiments. Il n’en reste pas moins que ceci n’empêche pas la récurrence et en
particulier le retour en l’état 0 (correspondant au compartiment A vide).
Mais en réalité ce retour n’est pas observable dans le sens suivant. On peut montrer
que le temps moyen pour aller à l’état 0 en partant de L = N2 (on suppose N pair) est

1 2L
2 (1 + O(L))
2L
tandis que le temps moyen pour aller de L à 0 est inférieur à

L + L log L + O(1).

Avec L = 106 et une unité de temps mathématique égale à 10−5 seconde, le retour à
l’état L en partant de 0 est de l’ordre d’une seconde, tandis qu’il faudrait de l’ordre de

1 106
11
× 22 secondes
2 · 10
pour passer de L à 0. Il s’agit d’un temps astronomique, et c’est en ce sens que le retour
en 0 n’est pas observable.
Ces nombres nous apprennent qu’il est inutile de passer trop de temps à touiller
son café, ou de l’avaler rapidement de peur que le morceau de sucre se reforme. Plus
sérieusement : rien n’empêche la chaı̂ne de se trouver dans un état rare (au sens proba-
biliste, c’est-à-dire, de faible probabilité stationnaire), seulement elle ne s’y trouve que
rarement (au sens temporel), extrêmement rarement, pour nous autre mortels, jamais !
Boltzmann était conscient du fait que les temps de récurrence dans le théorème de
Poincaré devaient être très longs, mais ses arguments n’avaient pas réussi à convaincre,
ce que put faire le modèle Ehrenfest.

Théorème ergodique
Nous allons donner des conditions générales garantissant que les moyennes empiriques
du type
N
1 
g(Xk , . . . , Xk+L )
N
k=1

convergent vers les moyennes probabilistes.

On obtiendra le résultat recherché comme conséquence de la proposition suivante.

1
Dans ce modèle, ce n’est pas vrai à cause de la périodicité de la chaı̂ne, mais cette objection
disparait au prix d’une légère modification.
8.3. COMPORTEMENT ASYMPTOTIQUE 239

Proposition 8.3.1 Soit {Xn }n≥0 une cmh irréductible récurrente, et soit x la mesure
invariante canonique associée à l’état 0 ∈ E,
 

x i = E0  1{Xn =i} 1{n≤T0 }  , (8.33)
n≥1

où T0 est le temps de retour en 0. Définissons pour tout n ≥ 1

n

ν(n) = 1{Xk =0} . (8.34)
k=1

Soit maintenant f : E → R une fonction telle que


|f (i)|xi < ∞. (8.35)
i∈E

Alors, pour toute distribution initiale µ, presque sûrement,

N
1  
lim f (Xk ) = f (i)xi . (8.36)
N ↑∞ ν(N )
k=1 i∈E

Démonstration. Soit T0 = τ1 , τ2 , τ3 , . . . les temps de retour successifs en 0. Posons

τp+1

Up = f (Xn ).
n=τp +1

La suite {Up }p≥1 est, d’après le Théorème 8.2.1, iid. De plus, si on suppose f ≥ 0,
&T '
 0

E[U1 ] = E0 f (Xn )
n=1
& T0 
' & T0
'
  
= E0 f (i)1{Xn =i} = f (i)E0 1{Xn =i}
n=1 i∈E i∈E n=1

= f (i)xi .
i∈E

Cette quantité est finie par hypothèse et, d’après la loi forte des grands nombres,
n
1 
lim Up = f (i)xi ,
n↑∞ n
p=1 i∈E

c’est-à-dire :
τn+1
1  
lim f (Xk ) = f (i)xi . (8.37)
n↑∞ n
k=T0 +1 i∈E
240 CHAPITRE 8. CHAÎNES DE MARKOV

En observant que
τν(n) ≤ n < τν(n)+1 ,
on a :
τν(n) n τν(n)+1
k=1 f (Xk ) k=1 f (Xk ) k=1 f (Xi )
≤ ≤ .
ν(n) ν(n) ν(n)
Comme la chaı̂ne est récurente, limn↑∞ ν(n) = ∞, et donc,  d’après (8.37), les termes
extrêmes de la chaı̂ne d’inégalités ci-dessus tendent vers i∈E f (i)xi quand n tend vers
l’∞, et ceci donne (8.36). Le cas où f est de signe arbitraire s’obtient en écrivant (8.36)
pour f + = max(0, f ) et f − = max(0, −f ), et en prenant les différences des égalités
obtenues de cette manière (la différence n’est pas une forme indéterminée ∞ − ∞, grâce
à l’hypothèse (8.35)). 

Nous sommes maintenant en mesure de donner le théorème ergodique pour les chaı̂nes
de Markov.
Théorème 8.3.3 Soit {Xn }n≥0 une cmh irréductible récurrente positive de distribu-
tion stationnaire π, et soit f : E → R une fonction telle que

Eπ [|f (X0 )|] := |f (i)|π(i) < ∞. (8.38)
i∈E

Alors, pour toute distribution initiale µ, presque sûrement,

N
1  
lim f (Xk ) = f (i)π(i). (8.39)
n↑∞ N
k=1 i∈E

Démonstration. On applique la Proposition 8.3.1  à f ≡ 1. La condition (8.35) est

satisfaite, puisque dans le cas positif récurrent, i∈E xi = E0 [T0 ] < ∞. Donc, presque
sûrement,
N 
lim = xj .
N ↑∞ ν(N )
j∈E
Si la fonction f satisfait (8.38), elle satisfait aussi (8.35), puisque x et π sont propor-
tionnelles, et donc, presque sûrement,
N
1  
lim f (Xk ) = f (i)xi .
N ↑∞ ν(N )
k=1 i∈E
En combinant les égalités ci-dessus, on obtient
N N 
1  ν(N ) 1  i∈E f (i)xi
lim f (Xk ) = lim f (Xk ) =  ,
N →∞ N N →∞ N ν(N ) j∈E xj
k=1 k=1
d’où (8.39), puisque π est obtenue par normalisation de x. 

Le corollaire suivant étend le domaine d’application du Théorème 8.3.3.

8.3. COMPORTEMENT ASYMPTOTIQUE 241

Corollaire 8.3.1 Soit {Xn }n≥0 une cmh irréductible récurrente positive de distribution
stationnaire π, et soit g : E L+1 → R une fonction telle que
Eπ [|g(X0 , . . . , XL )|] < ∞ .
Alors, pour toute distribution initiale µ, presque sûrement,
N
1 
lim g(Xk , Xk+1 , . . . , Xk+L ) = Eπ [|g(X0 , . . . , XL )|] .
N
k=1

Démonstration. On applique le Théorème 8.3.3 à la chaı̂ne {(Xn , Xn+1 , . . . , Xn+L )}n≥0

d’espace d’état
F = {(i0 , i1 , . . . , iL ) ∈ E L+1 ; pi0 i1 · · · piL−1 iL > 0}
qui est (voir Exercice 8.5.19) irréductible récurrente positive de distribution stationnaire
π(i0 )pi0 i1 · · · piL−1 iL .


Exemple 8.3.2: Estimateur empirique des probabilités de transition. Soit

{Xn }n≥1 une cmh irréductible récurrente positive de matrice de transition P et de
distribution stationnaire π. Alors, pour tous i0 , i1 ∈ E,
N
1 
lim 1{Xn =i0 } = π(i0 )
N ↑∞ N
k=1
et
N
1 
lim 1{Xn =i0 ,Xn+1 =i1 } = π(i0 )pi0 ,i1 .
N ↑∞ N
k=1
En particulier, N
k=1 1{Xn =i0 ,Xn+1 =i1 }
lim N = pi0 ,i1 .
k=1 1{Xn =i0 }
N ↑∞

Démonstration. Soit f : E → R la fonction définie par f (i) = 1{i0 } (i). On a :

f (Xn ) = 1{i0 } (Xn )
= 1{Xn =i0 } ,
et donc, d’après le théorème ergodique(Théorème 8.3.3),
N
1   
lim 1{Xn =i0 } = Eπ 1{X0 =i0 }
N ↑∞ N
k=1
= Pπ (X0 = i0 ) = π(i0 ).
242 CHAPITRE 8. CHAÎNES DE MARKOV

Avec f : E × E → R définie par f (i, j) = 1{i0 ,i1 } (i, j), on a :

f (Xn , Xn+1 ) = 1{i0 ,i1 } (Xn , Xn+1 )

= 1{Xn =i0 ,Xn+1 =i1 } .

et donc, toujours d’après le théorème ergodique (Corollaire 8.3.1) :

N
1   
lim 1{Xn =i0 ,Xn+1 =i1 } = Eπ 1{X0 =i0 ,X1 =i1 }
N ↑∞ N
k=1
= Pπ (X0 = i0 , X1 = i1 ) = π(i0 )pi0 ,i1 .

On voit donc que si l’on ne connaı̂t pas la matrice de transition d’une cmh irréductible
récurrente positive, on peut, en principe, obtenir cette matrice de transition si on dispose
d’une trajectoire complète de la cmh en question.

Exemple 8.3.3: Une politique de maintenance. Soit {Un }n≥1 une suite de variables
iid à valeurs dans N+ . La variable Un est interprétée comme la durée de vie d’une
machine, la n-ème, qui est remplacée par une (n + 1)-ème dès qu’elle tombe en panne.
Donc, au temps 0, la machine 1 est mise en service service jusqu’à ce qu’elle “casse” au
temps U1 , où elle est immédiatement remplacée par la machine 2, qui casse au temps
U1 + U2 , et ainsi de suite. Au temps n, le temps restant avant la prochaine panne est
Xn . Plus précisément, le processus {Xn }n≥0 prend ses valeurs dans E = N (On suppose
que ces variables prennent des valeurs arbitrairement grandes : P (U1 > k) > 0 pour
 tout
k ≥ 1 ; l’autre cas se traı̂te de manière analogue), est égal à 0 au temps Rk = ki=1 Ui ,
à Uk+1 − 1 au temps Rk + 1, et alors décroı̂t d’une unité par unité de temps jusqu’à
ce qu’il atteigne la valeur 0 au temps Rk+1 . On supposera que pour tout k ∈ N+ ,
P (U1 > k) > 0, de sorte que l’espace d’état E est N. Alors {Xn }n≥0 est une cmh de
probabilités de transition :

P (U > i + 1)
pi,i+1 = P (U > i + 1 | U > i) = ,
P (U > i)
P (U = i + 1)
pi,0 = P (U = i + 1 | U > i) = ,
P (U > i)

où U est une variable aléatoire de même distribution que U1 . Cette cmh est irréductible,
comme on le vérifie facilement. Elle est récurrente positive si et seulement si E[U ] < ∞
(U1 = T0 ). Dans ce cas, sa distribution stationnaire est

P (U > i)
π(i) = . (8.40)
E[U ]
8.3. COMPORTEMENT ASYMPTOTIQUE 243

En effet, on vérifie facilement les équations de balance globale

π(i) = pi−1,i π(i − 1)

et
∞

π(0) = π(i)pi,0 .
i=0

Une visite de la cmh à l’état 0 correspond à une panne de la machine machine, et donc
d’après le théorème ergodique,,
N
1 
π(0) = lim 1{Xk =0}
N ↑∞ N
k=1

est la fréquence empirique des pannes. On a

π(0) = E0 [T0 ]−1 ,

où T0 est le temps de retour en 0. Ici,

E0 [T0 ] = E[U ],

et donc
N
1  1
lim 1{Xk =0} = . (8.41)
N ↑∞ N E[U ]
k=1
Le coût d’une panne peut être si important que l’on préfère remplacer une machine avant
qu’elle tombe en panne (une panne entraı̂ne des réparations coûteuses, peut-être même
une catastrophe humaine, tandis qu’un remplacement se traduit par de simples coûts de
maintenance). Dans la politique de de retraite à âge fixe, on choisit un entier T ≥ 1
et on impose que toute machine atteignant l’âge T soit immédiatement remplacée. On
veut calculer la fréquence empirique des pannes (pas des remplacements).
La cmh correspondant à cette politique est du même type que celle décrite plus haut,
on remplace simplement Un par Vn = Un ∧ T . Un remplacement (pas une panne) a lieu
au temps n si et seulement si Xn = 0 et Xn−1 = T − 1. Mais Xn−1 = T − 1 implique
Xn = 0, et donc un remplacement a lieu au temps n si et seulement si

Xn−1 = T − 1.

La fréquence empirique de remplacements non dus à des pannes est donc, d’après le
théorème ergodique,
N
1 
lim 1{Xk =T −1} = π(T − 1).
N ↑∞ N
k=1
La formule (1) appliquée à cette nouvelle situation donne
P (V ≥ T )
π(T − 1) = ,
E[V ]
244 CHAPITRE 8. CHAÎNES DE MARKOV

et donc, comme V = U ∧ T ,
P (U ≥ T )
π(T − 1) = .
E[U ∧ T ]
La fréquence empirique des visites à 0 est, d’après (8.41),
1
.
E[U ∧ T ]
La fréquence empirique des pannes est donc
1 P (U ≥ T ) P (U < T )
− = .
E[U ∧ T ] E[U ∧ T ] E[U ∧ T ]

8.4 Méthode de Monte Carlo

Principe de la méthode de Monte Carlo
On a vu (Section 3.2) que pour échantillonner une distribution de probabilié π sur
un espace fini E = {1, 2, ..., r}, on dispose d’une méthode conceptuellement très simple :
On tire un nombre aléatoire U uniformément
 distribué
i sur [0, 1] et on définit la variable
aléatoire Z en posant Z = i si i−1 =1 π( ) ≤ U < =1 π( ). La variable aléatoire Z est
alors bien un échantillon de π (c’est-à-dire : elle admet π comme distribution).
Cette méthode, dite de l’inverse, a un certain nombre d’inconvénients quand r est
très grand :
(a) Des problèmes peuvent se poser à cause de la petitesse des intervalles qui forment la
partition de [0, 1] adaptée à la distribution π, et du coût de la précision alors nécessaire
dans les calculs.
(b) L’espace des états ne se présente pas d’une manière naturelle sous la forme
{1, 2, ..., r}. En traitement des images et en physique statistique, un état est, par exemple,
un tableau de symboles binaires {aij , 1 ≤ i, j ≤ M ; aij ∈ {0, 1}, avec M très grand.
Pour implémenter la méthode de l’inverse, il faut d’abord “coder” E, c’est-à-dire associer
à chacun de ses éléments un nombre de 1 à r, obtenir Z qui est un nombre de 1 à r, puis
“décoder” le résultat (dire quelle image correspond à ce nombre). Ces opérations, qui
nécessitent des recherches dans de très grandes listes, sont coûteuses en temps de calcul.
(c) Enfin, il existe de nombreuses situations, surtout en physique, où π n’est connu qu’à
un facteur de normalisation près. La méthode de l’inverse est alors tout simplement
inapplicable.
La recherche d’échantillonneurs qui surmontent ces difficultés (surtout la dernière) est
un sujet important. La méthode dite mcmc (“Monte Carlo Markov chain”) est basé
8.4. MÉTHODE DE MONTE CARLO 245

sur le principe suivant : on construit une cmh {Xn }n≥0 irréductible récurrente positive
apériodique dont l’espace des états est E = {1, 2, ..., r} et qui admet π comme distri-
bution stationnaire. On laisse ce processus évoluer jusquà un temps n assez grand pour
que la distribution de Xn soit assez proche de la distribution stationnaire π, et on prend
comme échantillon de π la variable Xn . La distribution de Xn n’est qu’approximative-
ment égale à π. Ceci n’est pas trop grave si on peut donner une vitesse de convergence
de la distribution au temps n vers la distribution stationnaire ce qui permet de contrôler
la qualité de l’approximation en choisissant n en fonction des exigences de précision.
Le problème des vitesses de convergence est un domaine de recherche très actif que
nous n’aborderons pas ici. Pour l’instant nous allons simplement choisir une matrice de
transition irréductible récurrente positive apériodique qui admet π comme distribution
stationnaire.
Il y a un nombre infini de telles matrices et, parmi elles, il y en a une infinité qui
correspondent à une paire (P, π) réversible, c’est-à-dire telle que
π(i)pij = π(j)pji . (8.42)
Nous allons chercher des solutions de la forme
pij = qij αij (8.43)
pour j = i, où Q = {qij }i,j∈E est une matrice de transition sur E irréductible. La chaı̂ne
évolue de la façon suivante : Lorsque l’état présent est i, on choisit un état j avec la
probabilité qij . Cet état j est accepté comme nouvel état avec la probabilité αij . S’il
n’est pas accepté, on ne change pas d’état, on reste en i. La probabilité de transition de
i à j quand i = j est bien donné par (8.42). Il reste maintenant à choisir qij et αij . Nous
allons décrire les deux algorithmes les plus célèbres.

Exemple 8.4.1: L’algorithme de Metropolis. On suppose que la distribution π

est de la forme
e−U (i)
π(i) = , (8.44)
K
où U : E → R est une fonction, dite “fonction énergie” dans un contexte de physique, et
K est la “constante de partition”, la constante de normalisation assurant que π est bien
un vecteur de probabilité. On notera que la forme (8.44) n’a pas vraiment à être postulée
puisque on peut toujours choisir U (i) = − log π(i) et K = 1. En pratique, la fonction
d’énergie U est donnée et la constante de normalisation K est impossible à calculer
numériquement. Mais nous allons voir que l’algorithme de Metropolis n’en a pas besoin.
Cet algorithme préconise une matrice Q symétrique, et la probabilité d’acceptation
+ ,
αij = min 1, e−(U (j)−U (i)) .
Il est facile de vérifier que les équations de balance détaillée (8.42) sont satisfaites, et
que la cmh en question est bien irréductible et, lorsque la fonction énergie n’est pas une
constante, apériodique.
246 CHAPITRE 8. CHAÎNES DE MARKOV

Exemple 8.4.2: L’algorithme de Barker. Cet algorithme utilise lui aussi une ma-
trice Q symétrique. Sa probabilité d’acceptation est

e−U (i)
αij = .
e−U (i)+ e−U (j)
Ce choix correspond au principe de base de la physique statistique : quand la Nature a le
choix entre deux états 1 et 2 d’énergies respectives E1 et E2 , elle choisit i = 1, 2 avec la
−E
probabilité e−Ee1 +ei−E2 . Là encore, on vérifie que les équations de balance détaillée (8.42)
sont satisfaites, et que la cmh en question est bien irréductible et, lorsque la fonction
énergie n’est pas une constante, apériodique.

Exemple 8.4.3: L’algorithme de Gibbs. L’espace des états est E = ΛN , où N est
un entier positif et Λ est un ensemble fini. La distribution à échantillonner est donc de
la forme
π(z) = π(z(1), . . . , z(N ))
Le mécanisme de transition est le suivant. Si on se trouve dans l’état (z(1), . . . , z(N )), on
choisit un “site” , 1 ≤ ≤ N , au hasard, et on change la coordonnée z( ) (et elle seule)
en y( ), cette nouvelle coordonnée étant choisie en fonction de z(1), . . . , z( − 1), z( +
1), . . . , z(N ) avec la probabilité

π(y( ) | z(1), . . . , z( − 1), z( + 1), . . . , z(N )). (8.45)

Là encore, on vérifie que les équations de balance détaillée (8.42) sont satisfaites, que la
cmh en question est bien irréductible et, lorsque π n’est pas une constante, apériodique.

Cette méthode est spécialement intéressante lorsque Λ (l’“espace des phases”) est petit,
et lorsque la probabilité conditionnelle π(· | z(1), . . . , z( − 1), z( + 1), . . . , z(N )) ne
dépend que d’un petit nombre des arguments z(1), . . . , z( − 1), z( + 1), . . . , z(N ). Voici
un exemple qui présente un grand intérêt pour les physiciens :

Exemple 8.4.4: L’échantillonneur de Gibbs pour le modèle d’Ising. Le modèle

d’Ising est une idéalisation d’un matériau ferromagnétique. On a N = M 2 dipôles
magnétiques placés sur une grille finie. Plus précisément les sites sur lesquels se trouvent
les dipôles forment un ensemble S = {(i, j); 1 ≤ i, j ≤ M }. Un site s ∈ S a donc
la forme s = (i, j). La distance entre deux sites s1 = (i1 , j1 ) et s2 = (i2 , j2 ) est
d(s1 , s2 ) = |i1 − i2 | + |j1 − j2 |. On dit que s1 et s2 sont voisins si d(s1 , s2 ) = 1. Deux sites
voisins s1 et s2 forment une paire notée s1 , s2 !. L’espace des phases est Λ = {−1, +1},
la valeur −1 correspond à une orientation de dipôle, disons vers le bas, tandis que +1
correspond à la direction opposée. L’espace d’états E = ΛS est l’ensemble des “confi-
gurations” (z(s), s ∈ S) où z(s) ∈ Λ = {−1, +1}. Une telle configuration représente
des dipôles placés sur les sites de S, l’orientation du dipôle placé en s étant z(s). Si on
8.5. EXERCICES 247

énumère les sites de S de 1 à N = M 2 , on retrouve bien la situation décrite plus haut.

Précisons maintenant la distribution π. On prendra
exp{−E(z)}
π(z(s), s ∈ S) =
K

oùE(z) est l’énergie de la configuration z = (z(s), s ∈ S) : E(z) = H s∈S z(s) +
J s,t z(s)z(t) (la deuxième somme porte sur toutes les paires de sites voisins) et K
est une constante de normalisation, en général incalculable numériquement. (Pour les
physiciens H est le champ magnétique externe, et J est l’énergie interne d’une paire de
dipôles voisins orientés dans le même sens.) La probabilité conditionnelle jouant le rôle
de (8.45),
π(y(s), z(t), t ∈ S − {s})
π(y(s) | z(t), t ∈ S − {s}) =  ,
z(s)∈Λ π(z(s), z(t), t ∈ S − {s})

prend la forme (faire le calcul)

exp{E(s, z)}
π(y(s) | z(t), t ∈ S − {s}) = , (8.46)
exp{E+1 (s, z)} + exp{E+1 (s, z)}

où E(s, z) = y(s) (H + J z(v(s))) et où la somme porte sur tous les sites v(s) voi-
sins de s. En physique, on appelle E(s, z) l’énergie locale au site s de la configuration
(y(s), z(t), t ∈ S − {s}), et E+1 (s, z) et E+1 (s, z) sont les valeurs de cette énergie locale
correspondant aux directions +1 et −1 respectivement de l’orientation du dipôle placé en
s. L’échantillonneur de Gibbs fonctionne donc dans le cas présent de la façon suivante :
si au temps n on a la configuration z = (z(s), s ∈ S), on choisit un site complètement
au hasard (distribution uniforme). Si c’est le site s qui a été tiré au sort, on tire au sort
la nouvelle phase y(s) de ce site s selon la probabilité (8.46). On notera que ce choix est
fait selon les principes de la physique statistique décrit quelques lignes plus haut.

8.5 Exercices
Exercice 8.5.1. Un contre-exemple.
La propriété de Markov ne dit pas que le présent et le futur sont indépendants étant
donné une information quelconque sur le présent. Trouvez un exemple simple de cmh
{Xn }n≥0 avec l’espace d’état E = {1, 2, 3, 4, 5, 6} tel que
P (X2 = 6 | X1 ∈ {3, 4}, X0 = 2) = P (X2 = 6 | X1 ∈ {3, 4}).

Exercice 8.5.2.
Démontrez l’égalité (8.2).

Exercice 8.5.3.
Démontrez le Théorème 8.1.5.
248 CHAPITRE 8. CHAÎNES DE MARKOV

Exercice 8.5.4. Gestion des stocks.

Une marchandise donnée A est stockée en vue de satisfaire à la demande. La demande
totale entre le temps n et le temps n + 1 est de Zn+1 unités, et on suppose que la suite
{Zn }n≥1 est iid, et indépendante de la valeur initiale X0 du stock. Le remplissage du
stock a lieu aux temps n + 0 (c’est-à-dire, immédiatement après le temps n) pour tout
n ≥ 1.

Z1 = 1 Z2 = 4 Z3 = 2 Z4 = 1 Z5 = 1 Z6 = 3 Z7 = 2
s=5
X0 X5
X1
X3 X7
s=2
X4
X6
0
X2

Une stratégie de gestion populaire est la stratégie (s, S), où s et S sont des entiers tels
que 0 < s < S. Avec cette politique de gestion, si le niveau du stock au temps n est plus
gret que s, alors le stock est ramené au niveau S autemps n + 0. Autrement, rien n’est
fait. Le stock initial X0 est supposé inférieur ou égal à S, et donc {Xn }n≥1 prend ses
valeurs dans E = {S, S − 1, S − 2, . . .}. (Voir la figure.) Les valeurs négatives du stock
sont admises, avec interprétation qu’une commande non satisfaite est immédiatement
honorée après restockage. Montrez que {Xn }n≥1 est une cmh et donnez sa matrice de
transition.

Exercice 8.5.5. ∗ Records.

Soit {Zn }n≥1 une suite iid de variables géometriques (pour k ≥ 0, P (Zn = k) = (1−p)k p,
où p ∈ (0, 1)). Soit Xn = max(Z1 , . . . , Zn ) la valeur record au temps n, où on suppose
que X0 est une variable à valeurs entières et indépendante de la suite {Zn }n≥1 . Montrez
que {Xn }n≥0 est une cmh et donnez sa matrice de transition.

Exercice 8.5.6. ∗ La vie des gangsters.

Trois personnages armés, A, B, et C, se trouvent soudainement en présence au carrefour
d’une rue de Washington, D.C., et sur ce, se mettent tout naturellement à se tirer dessus.
Chaque survivant tire sur un autre survivant de son choix toutes les 10 secondes. Les
probabilités d’atteindre la cible pour A, B, et C sont respectivement α, β, et γ. A est le
plus haı̈ des trois, et donc, tant qu’il vit, B et C s’ignorent et lui tirent dessus. Pour des
raisons historiques que nous ne développerons pas, A ne peut pas sentir B, et donc il ne
8.5. EXERCICES 249

tire que sur B tant que ce dernier est vivant. Le bienheureux C n’est visé que lorsqu’il
se trouve en présence de A seul ou B seul. Quelles sont les chances de survie de A, B, et
C, respectivement ?
Exercice 8.5.7. ∗ Le chat, la souris et le gruyère.
Une souris affairée se promène dans un labyrinthe. Si au temps n elle se trouve dans une
pièce avec k portes, elle en choisit une avec la probabilité k1 et se retrouve à l’instant
n + 1 dans la pièce à laquelle cette porte conduit. Un chat paresseux attend dans la pièce
numéro 3, et il y a un morceau de fromage dans la pièce numéro 5. La souris commence
son périple dans la pièce 1. Avec quelle probabilité goûtera-t-elle du fromage avant que
le chat ne la dévore ?

2 3

CHAT

1 4 5

SOURIS FROMAGE

La chambre au gruyère

Exercice 8.5.8.
Montrez que le graphe de transition de la figure ci-dessous est irréductible. Donnez sa
période et ses classes cycliques.

3 7

4 2

5
1 6

Exercice 8.5.9.
Montrez qu’une matrice de transition P avec au moins un état i ∈ E tel que pii > 0 est
apériodique.
250 CHAPITRE 8. CHAÎNES DE MARKOV

Exercice 8.5.10. ∗
Montrez que la marche aléatoire symétrique sur Z n’a pas de distribution stationnaire.

Exercice 8.5.11.
Est-ce que la cmh de l’Exemple 8.1.9 est réversible ?

Exercice 8.5.12.
Soit {Xn }n≥0 la cmh de l’Exemple 8.1.7.
(1) Montrez qu’elle est réversible ;
(2) Sachant X0 = 1, calculez la distribution de probabilité de T1 = inf {n ≥ 1; Xn = 1},
où on utilise la convention inf {∅} = ∞.

Exercice 8.5.13. ∗
Calculez la distribution stationnaire de la cmh d’espace d’état E = {1, 2, 3} et de matrice
de transition  
1 1−α α 0
P = 0 1 − β β ,
γ 0 1−γ
où α, β, γ ∈ (0, 1). Est-elle réversible ?

Exercice 8.5.14. ∗
Démontrez le Théorème 8.2.1

Exercice 8.5.15. Les cailloux.

Des cailloux S1 , . . . , SM sont alignés. Au temps n un caillou est choisi au hasard, et ce
caillou échange sa place avec le caillou placé juste devant lui. Si le caillou sélectionné
est en tête, on ne change rien. Par exemple, avec M = 5 : Si la situation juste avant le
temps n est S2 S3 S1 S5 S4 (S2 est en tête), et si S5 est tiré au sort, la nouvelle situation est
S2 S3 S5 S1 S4 , tandis que si S2 est sélectionné, la configuration reste la même. À chaque
top de l’horloge, Si est sélectionné avec la probabilité αi > 0. Notons Xn la situation au
temps n, par exemple Xn = Si1 · · · SiM , avec l’interprétation que Sij est dans la j-ème
position. Montrez que {Xn }n≥0 est une cmh irréductible récurrente positive et que sa
distribution stationnaire est

π(Si1 · · · SiM ) = CαiM1 αiM2 −1 · · · αiM ,

où C est une constante de normalisation.

Exercice 8.5.16. Chaı̂ne produit.

(1) (2)
Soit {Xn }n≥0 et {Xn }n≥0 deux cmh avec la même matrice de transition P. Montrez
(1) (2)
que le processus {Zn }n≥0 à valeurs dans E × E défini par Zn = (Xn , Xn ) est une cmh.
Quelle est sa matrice de transition en n étapes ? Montrez qu’elle est irréductible si P est
8.5. EXERCICES 251

irréductible et apériodique. Donnez un contre-exemple lorsqu’on abandonne l’hypothèse

d’apériodicité.

Exercice 8.5.17.
Soit X01 , X02 , Zn1 , Zn2 (n ≥ 1) des variables aléatoires indépendantes, et telles que, de plus,
Zn1 , Zn2 (n ≥ 1) sont identiquement distribuées. Soit τ une variable aléatoire à valeurs
entières non négatives telle que pour tout m ∈ N, l’événement {τ = m} est exprimable
en fonction de X01 , X02 , Zn1 , Zn2 (n ≤ m). On définit {Zn }n≥1 par

= Zn1 si n ≤ τ
Zn =
= Zn2 si n > τ

Montrez que {Zn }n≥1 a la même distribution que {Zn1 }n≥1 et est indépendante de
X01 , X02 .

Exercice 8.5.18. Fusion.

Soit {Xn1 }n≥0 et {Xn2 }n≥0 deux cmh avec la même matrice de transition P. Soit τ le
temps défini par
τ = inf{n ≥ 0 ; Xn1 = Xn2 }
(avec la convention usuelle: inf ∅ = ∞). Supposons que P (τ < ∞) = 1. On définit
{Xn }n≥1 par 
Xn1 if n ≤ τ
Xn =
Xn2 if n > τ

Montrez que {Xn }n≥1 a la même distribution que {Xn1 }n≥1 .

Exercice 8.5.19. La chaı̂ne serpent.

Soit {Xn }n≥0 une cmh d’espace d’état E et de matrice de transition P. Pour L ≥ 1, on
définit Yn = (Xn , Xn+1 , . . . , Xn+L ).
(a) Le processus {Yn }n≥0 prend ses valeurs dans F = E L+1 . Montrez que c’est une cmh
et donnez sa matrice de transition.
(b) Montrez que si {Xn }n≥0 est irréductible, il en est de même pour {Yn }n≥0 si on
restreint l’espace d’état de cette dernière à F = {(i0 , . . . , iL ) ∈ E L+1 ; pi0 i1 pi1 i2 · · ·
piL−1 iL > 0}.
(c) Montrez que si {Xn }n≥0 a une distribution stationnaire π, alors {Yn }n≥0 a aussi une
distribution stationnaire. Laquelle ?

Exercice 8.5.20. ∗ Retour à l’état initial.

Soit τ le temps de retour à l’état initial d’une cmh irréductible récurrente positive
{Xn }n≥0 , c’est-à-dire,
τ = inf{n ≥ 1; Xn = X0 },
252 CHAPITRE 8. CHAÎNES DE MARKOV

Calculez l’espérance de τ lorsque la distribution initiale est la distribution stationnaire π.

Conclure que cette espérance est finie si et seulement si E est fini. Quand E est infini,
est-ce que ceci est en contradiction avec l’hypothèse de récurrence positive ?

Exercice 8.5.21. ∗ Le cavalier rentre à la maison.

Un cavalier circule de manière aléatoire sur un échiquier, choisissant chaque mouvement
parmi ceux qui lui sont permis avec la même probabilité, et débutant son périple d’un
coin de l’échiquier. Combien de temps en moyenne lui faudra-t-il pour se retrouver sur
sa case de départ ?

Exercice 8.5.22. Codage alternatif.

Dans certains systèmes de communication numérique, une suite de 0 et de 1 (symboles
d’entrée) est codée en une suite de 0, +1 et −1 (symboles de sortie) de la manière
suivante. Un symbole d’entrée 0 est codé en 0, tandis qu’un symbole d’entrée 1 est codé
en −1 ou +1. Le choix entre −1 et +1 est fait de telle sorte que les −1 et les +1 alternent.
Le premier 1 est codé en +1. Par exemple la suite de symboles d’entrée 011101 devient
0, +1, −1, +1, 0, −1.
a. Trouvez un automate avec 4 états +1, −1, 0+ et 0− , pour lequel la suite des états vi-
sités, à part l’état initial fixé à 0+ , est, lorsque 0+ et 0− sont remplacés par 0, exactement
la suite de sortie.
b. On suppose que la suite d’entrée {Zn }n≥1 est iid, avec 0 et 1 équiprobables. La suite
des états de l’automate est alors une cmh dont on demande de calculer la matrice de
transition P et ses itérées Pn , et la distribution stationnaire π.
c. Notons {Yn }n≥0 la suite de symboles de sortie (prenant les valeurs {0, −1, +1}). Mon-
trez que Yn = f (Xn ) pour une function f à identifier, et calculez limn→∞ {E[Yn Yn+k ] −
E[Yn ]E[Yn+k ]} pour tout k ≥ 0.

Exercice 8.5.23. ∗ ABBABAA.

Une suite de A et de B est formée comme suit. La première lettre est choisie au hasard,
P (A) = P (B) = 12 , ainsi que la deuxième, indépendamment de la première. Quand les
n ≥ 2 premières lettres ont été sélectionnées, la (n + 1)-ème est choisie, indépendamment
des lettres dans les positions k ≤ n − 2, et conditionnellement à la paire formée par les
lettres en position n − 1 et n, comme suit :

1 1 1 1
P (A | AA) = , P (A | AB) = , P (A | BA) = , P (A | BB) = .
2 2 4 4
Quelles sont les proportions de A et de B au long terme ?

Exercice 8.5.24. Recherche d’un motif.

Considérons le tableau de a et de b de la figure A ci-dessous où une lettre dans
une position donnée est choisie au hasard et équiprobablement dans l’ensemble {a, b},
8.5. EXERCICES 253

indépendamment des autres lettres. On veut calculer la fréquence empirique asympto-

tique du motif de la figure B, sans compter les chevauchements. Par exemple, avec la
suite de la figure A , on compte 2 occurences du motif ; La troisième est ignorée car elle
chevauche la deuxième (Figure C).

b a b b a b a b b b
b a a a b b a a a a
A
b · b
· a a
B
b a b b a b a b b b
b a a a b b a a a a
C
OUI OUI NON
Trouvez un automate qui lit successivement les colonnes à deux lettres de gauche à
droite, et qui possède un état privilégié ∗ avec la propriété suivante : l’automate entre
ou reste dans l’état ∗ si et seulement si il vient de découuvrir un motif qui ne chevauche
pas un autre précédemment découvert. Quelle est la fréquence empirique asymptotique
du motif ?