Université de Rennes 1 – Préparation à l’épreuve de modélisation - Agrégation Externe de Mathématiques – 2012-2013. Page n◦ 1.

Chaı̂nes de Markov 1

L’essentiel de ces notes provient de [BEK04]. On pourra aussi consulter [BL98] ou [Nor97]
qui est très facile à lire (bien qu’en anglais) et contient de nombreux exemples.
Dans tout ce qui suit E est un espace de cardinal fini, très souvent identifié à {1, . . . , d}.

1 Matrices de transition et chaı̂nes de Markov

Définition 1. Une matrice de transition (ou noyau de transition ou matrice markovienne) sur
l’ensemble E est une application P : E × E → [0, 1] telle que
X
∀x ∈ E, P (x, y) = 1.
y∈E

Une chaı̂ne de Markov de matrices de transition (Pn )n≥0 et de loi initiale µ est une suite de
variables aléatoires (Xn )n∈N définie sur un espace probabilisé (Ω, A, P) et à valeurs dans E telle
que L(X0 ) = µ et
n−1
Y
P(X0 = x0 , . . . , Xn = xn ) = µ({x0 }) Pi (xi , xi+1 ). (1)
i=0

pour tout n ∈ N et tout (n + 1)-uplet (x0 , . . . , xn ) de E n+1 .

Remarque 2. On peut définir alternativement une chaı̂ne de Markov sur E de la façon suivante.
Une suite (Xn )n≥0 est une chaı̂ne de Markov sur E s’il existe une suite (fn )n≥0 de fonctions de
E × [0, 1] dans E et une suite de variables aléatoires indépendantes de loi uniforme sur [0, 1]
telles que
∀n ≥ 0, Xn+1 = fn (Xn , Un ).
Définition 3. La chaı̂ne est dite homogène si la suite de matrices markoviennes (Pn )n≥0 ou la
suite de fonctions (fn )n≥0 est constante.

Exemple 4 (Marche aléatoire sur les sommets du cube). L’espace d’états est E = {0, 1}d les
sommets du cube unité dans Rd et la matrice de transition est définie ainsi : pour x, y ∈ E,
(
1/(2d) si |x − y| = 1,
P (x, y) =
0 sinon.

Exemple 5 (Urne d’Ehrenfest). L’espace d’états est {0, 1, . . . , d} et la matrice de transition est
définie par 
x/d
 si y = x − 1,
P (x, y) = (d − x)/d si y = x + 1,

0 sinon.


18 août 2020. F. Malrieu [Link]@[Link]. GNU FDL Copyleft. Page n◦ 1.

Université de Rennes 1 – Préparation à l’épreuve de modélisation - Agrégation Externe de Mathématiques – 2012-2013. Page n◦ 2.

Exemple 6 (Modèle de Wright-Fisher). L’espace d’états est {0, 1, . . . , N } et

   
N x y x N −y
P (x, y) = 1− .
y N N

En d’autres termes, L(Xn+1 |Xn = x) est la loi binomiale B(N, x/N ).

Dans la suite, nous considérerons, sauf mention contraire, des chaı̂nes de Markov homogènes.

2 Équation de Chapman-Kolmogorov
Il faut voir une matrice markovienne P comme un opérateur agissant sur les fonctions (iden-
tifiées à des vecteurs colonnes) et les mesures identifiées à des vecteurs lignes. L’opérateur P
associe à une fonction h (mesurable bornée) de E dans R la fonction P h (mesurable bornée) de
E dans R définie par X
∀x ∈ E, P h(x) = P (x, y)h(y)
y∈E

et à une mesure positive (respectivement une probabilité) µ sur E la mesure positive (respecti-
vement la probabilité) µP sur E définie par
X
∀y ∈ E, µP (y) = µ(x)P (x, y).
x∈E

Théorème 7. Soit X = (Xn )n≥0 une chaı̂ne de Markov homogène sur E de matrice de transition
P et de loi initiale µ0 . Notons µn la loi de Xn . Alors
— la suite (µn )n≥0 vérifie la relation de récurrence, appelée équation de Chapman-Kolmogorov,
suivante :
µn+1 = µn P = µ0 P n+1 ,
— pour tous x, y ∈ E, P(Xn = y|X0 = x) = P n (x, y),
— pour toute fonction h de E dans R,

E(h(Xn )|X0 = x) = P n h(x).

— pour toute fonction h de E dans R et toute probabilité µ0 sur E, si L(X0 ) = µ0 alors

E(h(Xn )) = µ0 (P n h) = (µ0 P n )h = µ0 P n h.

3 Propriété de Markov
La propriété de Markov exprime le fait que « conditionnellement au présent, passé et futur
sont indépendants ». Introduisons un peu de formalisme. Soit X une chaı̂ne de Markov sur E.
On peut voir X comme une variable aléatoire à valeurs dans l’espace des trajectoires T = E N .
Pour cela, on munit T de la tribu engendrée les tribus cylindriques (Bn (T))n≥0 définies par
Bn (T) = σ(X0 , . . . , Xn ).
Si X0 est de loi µ, on note Pµ la loi de X et si µ = δx , on note Pδx = Px .

18 août 2020. F. Malrieu [Link]@[Link]. GNU FDL Copyleft. Page n◦ 2.

Université de Rennes 1 – Préparation à l’épreuve de modélisation - Agrégation Externe de Mathématiques – 2012-2013. Page n◦ 3.

Proposition 8. La loi d’une chaı̂ne de Markov homogène sur E de matrice de transition P et

de loi initiale µ est l’unique mesure de probabilité Pµ sur (T, B(T)) caractérisée par (1).
On introduit à présent le processus décalé de n : Xn+ = (Xn+,k )k∈N défini par
Xn+,k = Xn+k , pour k ≥ 0.
Théorème 9 (Propriété de Markov). Soit X une chaı̂ne de Markov sur E de loi initiale µ.
Pour tout A ∈ B(T) et k ∈ N,
P(Xk+ ∈ A|Xk = xk , . . . , X0 = x0 ) = Pxk (A).
Remarque 10. On peut montrer que, pour une chaı̂ne de Markov à espace d’états fini, cette
propriété est encore vraie si l’on remplace k par un temps d’arrêt. On parle alors de propriété
de Markov forte. Mais ceci nous entraine trop loin pour aujourd’hui...

4 Récurrence et transience
Définition 11. Soit X une chaı̂ne de Markov sur E de noyau P et x ∈ E. On définit la variable
aléatoire Tx = inf {n > 1, Xn = x} à valeurs dans N∗ ∪ {+∞}. L’état x est dit
— transient pour P si Px (Tx < +∞) < 1,
— récurrent pour P si Px (Tx < +∞) = 1.
Remarque 12. On dit que x ∈ E est absorbant si P (x, x) = 1. Un état absorbant est récurrent.
Proposition 13. Si x est récurrent alors la suite (Xn )n≥0 revient une infinité de fois en x avec
probabilité 1.
Si x est transient, le nombre (aléatoire) de retours en x de la chaı̂ne issue de x est presque
sûrement fini de loi géométrique de paramètre Px (Tx = +∞).
On peut décomposer une chaı̂ne de Markov en regroupant les états transients et les classes
de récurrence que forment les classes d’équivalence de la relation x ∼ y si x mène à y et y mène
à x (on dit que x mène à y s’il existe k ∈ N tel que P k (x, y) > 0).

5 Probabilités invariantes
Définition 14. Une probabilité π sur E est dite invariante (ou stationnaire) pour P si c’est un
point fixe de l’équation de Chapman-Kolmogorov :
π = πP.
Définition 15. Soit π une probabilité sur E. La matrice de transition P est dite réversible par
rapport à π si
∀x, y ∈ E, π(x)P (x, y) = π(y)P (y, x).
Proposition 16. Si P est réversible par rapport à π alors π est une probabilité invariante pour
le noyau P .
Exemple 17. La marche aléatoire sur le cube admet une unique mesure invariante (la loi
uniforme sur E) et la chaı̂ne est réversible par rapport à cette probabilité. Toutes les mesures
pδ0 + (1 − p)δN , pour p ∈ [0, 1] sont des mesures invariantes de la chaı̂ne de Wright-Fisher.

18 août 2020. F. Malrieu [Link]@[Link]. GNU FDL Copyleft. Page n◦ 3.

Université de Rennes 1 – Préparation à l’épreuve de modélisation - Agrégation Externe de Mathématiques – 2012-2013. Page n◦ 4.

5.1 Existence
Soit P(E) l’ensemble des mesures de probabilité sur E fini de cardinal d. Cet ensemble est
le simplexe unité de Rd :
( )
X
d
P(E) = µ ∈ R : ∀x ∈ E, µ(x) ≥ 0, µ(x) = 1 .
x∈E

Théorème 18. L’ensemble des probabilités invariantes pour P est un sous-ensemble non vide
compact et convexe de P(E).

Corollaire 19. Il existe une mesure de probabilité invariante pour P .

5.2 Irréductibilité et unicité

Un graphe (orienté) sur un ensemble fini E est un couple G = (E, A) caractérisé par un
ensemble d’arêtes A ⊂ E × E. Les points de E sont appelés sommets et les points y de E tels
que (x, y) ∈ A sont les voisins de x. On associe à P la structure de graphe orienté G = (E, A)
définie par
A = {(x, y), P (x, y) > 0}.

Définition 20. Le noyau P est irréductible si, pour tout couple (x, y) ∈ E × E, il existe k ∈ N
et x0 = x, x1 , . . . , xn−1 , xn = y ∈ E tels que P (xi , xi+1 ) > 0 pour i = 0, . . . , k − 1 ou encore s’il
existe k ∈ N tel que P k (x, y) > 0 (on dit que x mène à y).

Remarque 21. L’irréductibilité de P est équivalente à la connexité du graphe orienté associé.

Proposition 22. Si P est irréductible, alors

— les seules fonctions P -invariantes (P f = f ) sont les fonctions constantes,
— P admet une unique probabilité invariante π. De plus, π(x) > 0 pour tout x ∈ E.

Si la chaı̂ne n’est pas irréductible, on peut décomposer son graphe associé en la réunion
d’une partie transiente et de composantes connexes de sorte que sur chacune de ces composantes
connexes, la chaı̂ne soit irréductible. Toute mesure invariante pour P s’écrit alors comme combi-
naison convexe des mesures invariantes des chaı̂nes restreintes à chaque composante récurrente.

6 Théorème ergodique
Théorème 23 (Théorème ergodique). Supposons P irréductible de mesure invariante π. Alors,
pour toute mesure initiale µ, et tout x ∈ E,
n−1
1X Pµ −p.s.
1{Xk =x} −−−−−→ π(x),
n n→∞
k=0

et, si pour tout x ∈ E, Tx = inf {k ≥ 1, Xk = x} désigne le temps de retour en x, alors

1
π(x) = .
Ex (Tx )

18 août 2020. F. Malrieu [Link]@[Link]. GNU FDL Copyleft. Page n◦ 4.

Université de Rennes 1 – Préparation à l’épreuve de modélisation - Agrégation Externe de Mathématiques – 2012-2013. Page n◦ 5.

Remarque 24. Sous les mêmes hypothèses, pour toute fonction h de E dans R,
n−1 Z
1X Pµ −p.s.
h(Xk ) −−−−−→ h dπ.
n n→∞
k=0

7 Convergence en loi
7.1 Irréductibilité forte
Définition 25. Le noyau P est dit fortement irréductible s’il existe un entier k tel que
∀x, y ∈ E, P k (x, y) > 0.
Remarque 26. Si P est fortement irréductible, non seulement tout état mène à tout autre mais
il existe une longueur de chemin commune à tous les couples départ-arrivée.
Théorème 27. Soit P un noyau fortement irréductible de probabilité invariante π. Alors, pour
toute probabilité µ sur E,
µP n −−−→ π,
n→∞
ou encore, pour toute loi initiale, (Xn )n≥0 converge en loi vers µ.

7.2 Apériodicité
Définition 28. Soit x ∈ E et R(x) = {n ∈ N∗ , P n (x, x) > 0}. On appelle période de x, et on
note p(x), le plus grand commun diviseur de R(x).
Proposition 29. Si P est irréductible, alors tous les points ont même période.
Définition 30. Si la période de P est égale à 1, on dit que P est apériodique.
Proposition 31. Le noyau P est fortement irréductible si et seulement si P est irréductible et
apériodique.

8 Exercices
Exercice 32. Soit (Xn )n≥0 une chaı̂ne de Markov de loi initiale λ et de matrice de transition P .
Soit k ∈ N∗ . Montrer que (Xkn )n≥0 est une chaı̂ne de Markov dont on précisera les paramètres.
Exercice 33. Soit (Xn )n∈N une chaı̂ne de Markov sur {1, 2, 3} de matrice de transition
 
0 1 0
P =  0 2/3 1/3 
p 1−p 0
Calculer P(Xn = 1|X0 = 1) dans les cas suivants : p = 1/16, p = 1/6 et p = 1/12.
Exercice 34. Soit Rec (resp. Tra) l’ensemble des états récurrents (resp. transients) d’une chaı̂ne
de Markov finie et homogène. Soit T le temps d’atteinte dans l’ensemble Rec. Montrer que pour
tout état i ∈ Tra, on a X
Ei (T ) = 1 + pij Ej (T ).
j∈Tra

18 août 2020. F. Malrieu [Link]@[Link]. GNU FDL Copyleft. Page n◦ 5.

Université de Rennes 1 – Préparation à l’épreuve de modélisation - Agrégation Externe de Mathématiques – 2012-2013. Page n◦ 6.

Exercice 35. Soit (Xn )n∈N une chaı̂ne de Markov sur {1, 2, 3, 4} de matrice de transition
 
1 0 0 0
 1/2 0 1/2 0 
P = 
 0 1/2 0 1/2 
0 0 0 1

— Classer les états de la chaı̂ne.

— Quelle est la probabilité que la chaı̂ne issue de 2 soit absorbée en 4 ?
— Quel est le temps moyen d’absorption de la chaı̂ne issue de 2 ?
— Quelles sont les mesures invariantes de la chaı̂ne ?

Exercice 36. On considère la matrice de transition suivante :

 
1/2 1/2 0 0 0 0
 0 0 1 0 0 0 
 
 1/3 0 0 1/3 1/3 0 
P =  0

 0 0 1/2 1/2 0 

 0 0 0 0 1/2 1/2 
0 0 0 0 1/2 1/2

Représenter le graphe de la chaı̂ne. Quelles sont les classes de la chaı̂ne, les mesures invariantes ?
Peut-on parler de chaı̂ne périodique, apériodique ?

Exercice 37. Quelle est la mesure invariante de la chaı̂ne de transition

 
0 1 0
P =  0 1/2 1/2 ?
1/2 0 1/2

Exercice 38. Soit p ∈]0, 1[, q = 1 − p et (Xn )n≥0 la chaı̂ne de Markov sur 0, 1, 2, . . . , M de
matrice de transition définie par

p00 = q, p01 = p, ∀i = 1, . . . , M − 1, pi,i−1 = q, pi,i+1 = p, pM,M −1 = q, pM,M = p.

Montrer que la chaı̂ne admet une mesure réversible que l’on explicitera.

Exercice 39. Sur l’ensemble fini E = Z/mZ, on considère la chaı̂ne de Markov (Xn )n≥0 de
transition P définie par

Pi,i+k = Pi,i−k = 1/2, Pi,j = 0 sinon pour k ∈ {1, . . . , m − 1}.

Donner, dans tous les cas, ses classes de récurrence et la mesure invariante de ces classes. Lorsque
la chaı̂ne est récurrente irréductible, déterminer quand elle est apériodique.

Exercice 40. On considère la chaı̂ne d’Ehrenfest décrite dans l’exemple 5.

1. Grâce à la section 2, calculer l’espérance de Xn sachant que X0 = i.

18 août 2020. F. Malrieu [Link]@[Link]. GNU FDL Copyleft. Page n◦ 6.

Université de Rennes 1 – Préparation à l’épreuve de modélisation - Agrégation Externe de Mathématiques – 2012-2013. Page n◦ 7.

2. Montrer que la loi binomiale B(d, 1/2) (que l’on notera π) est invariante (penser à la réversi-
bilité...). Est-elle unique ?
3. On suppose que la chaı̂ne est à l’état stationnaire. Comparer π(d/2) et π(0). Commenter...
4. Lorsque d est grand, estimer
√ que la √probabilité d’observer la chaı̂ne dans un état n’appartenant
pas à l’intervalle [(d − 5 d)/2, (d + 5 d)/2].
5. Déterminer la période de la chaı̂ne X. Soit F = {0, 1, . . . , d} ∩ (2N) et z ∈ F . Montrer que
la suite Y z définie par Ynz = X2n
z est une chaı̂ne de Markov sur F dont on exprimera la mesure

invariante en fonction de celle de X. Si X0 est à valeurs dans E quel est le comportement en

temps en long de la loi de Xn ? Les résultats de cette question admettent-ils une généralisation ?
6. Montrer que la chaı̂ne d’Ehrenfest est l’image de la marche aléatoire sur le cube par une
fonction que l’on précisera. Soit E et F deux ensembles finis, f : E → F et X une chaı̂ne de
Markov sur E. La suite Y définie par Yn = f (Xn ) est-elle, en général, une chaı̂ne de Markov ?
Exercice 41. On considère un cavalier fou sur un échiquier : à chaque coup, il se déplace de
manière équiprobable sur toutes les cases de l’échiquier qu’il a le droit d’atteindre. On note Xn
sa position après n déplacement. Montrer que (Xn )n≥0 est une chaı̂ne de Markov irréductible
récurrente. Quelle est sa mesure invariante ?
Exercice 42. Soit (V, E) un graphe connexe non orienté d’ensemble de sommets fini V et
d’ensembleP d’arêtes E ∈ V × V . On associe à chaque arête (i, j) un poids wij = wji > 0 et l’on
pose wi = j wij . Déterminer la mesure invariante de la chaı̂ne de Markov sur V de matrice de
transition P définie par Pij = wij /wi .
Exercice 43. Soit (Xn )n≥0 une chaı̂ne de Markov sur un espace d’états fini de matrice de
transition P avec Pij > 0 pour tous i, j. On pose τj = inf {n ≥ 1 ; Xn = j}. Montrer qu’il existe
ρ ∈]0, 1[ tel que pour tout n ≥ 1, tous i, j,
Pi (τj > n) ≤ ρn .
Exercice 44. Soit (Xn )n≥0 une chaı̂ne de Markov sur un espace d’états fini de matrice de
transition P avec Pij > 0 pour tous i, j et de loi initiale µ. On suppose cette chaı̂ne irréductible
et apériodique et on note π sa mesure invariante. On considère Y une chaı̂ne de Markov de
même matrice de transition et de loi initiale π et on la suppose indépendante de X. On note
T = inf {n ≥ 0, Xn = Yn } et on définit enfin Z de la façon suivante :
(
Xn si n ≤ T,
Zn =
Yn si n > T.
1. Remarquer que (X, Y ) est une chaı̂ne de Markov sur E × E. Que dire des coefficients de la
matrice de transition de la chaı̂ne produit ?
2. Établir que T est un temps d’arrêt pour la filtration du processus (X, Y ).
3. Déduire de la propriété de Markov forte, après l’avoir révisée ([BL98, p. 212]) que Z a même
loi que X.
4. Montrer qu’il existe ρ ∈]0, 1[ tel que pour tout n ≥ 1, tous i, j,
Pi (T > n) ≤ ρn .
5. Déduire de ce qui précède que la convergence de la loi de Xn vers π est sous-géométrique.

18 août 2020. F. Malrieu [Link]@[Link]. GNU FDL Copyleft. Page n◦ 7.

Université de Rennes 1 – Préparation à l’épreuve de modélisation - Agrégation Externe de Mathématiques – 2012-2013. Page n◦ 8.

Références
[BEK04] M. Benaı̈m et N. El Karoui – Promenade aléatoire, Les éditions de l’école poly-
technique, 2004.
[BL98] P. Barbe et M. Ledoux – Probabilités, De la licence à l’agrégation, Belin, 1998.
[Nor97] J. Norris – Markov chains, Cambridge Series in Statistical and Probabilistic Mathe-
matics, 1997.

18 août 2020. F. Malrieu [Link]@[Link]. GNU FDL Copyleft. Page n◦ 8.