Chapitre 4.

Chaînes de Markov

LAKHEL El Hassan

Département: Informatiques et Réseaux-Télécom.

ENSA

Page Web: [Link]

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 1 / 49

 Chaînes de Markov discrètes

Chaîne de Markov

Les chaînes de Markov constituent l’exemple le plus simple des processus stochastiques, lorsque
dans une suite de v. a., on abandonne l’hypothèse d’indépendance. Il s’agit d’un processus à
temps discret ; d’où le nom de chaîne . Soit E un espace fini ou dénombrable dans lequel les v.
a. vont prendre leurs valeurs ; l’espace E s’appelle l’espace d’états.
La définition suivante exprime qu’une chaîne de Markov est un processus stochastique sans
mémoire.

Définition
Une suite (Xn )n∈N de variables aléatoires à valeurs dans E est une chaîne de Markov sur E si,
pour tout entier strictement positif n et pour toute suite x0 , x1 , ..., xn d’éléments de E pour
laquelle P(Xn = xn , Xn−1 = xn−1 , ..., X1 = x1 , X0 = x0 ) ̸= 0, nous avons :

P(Xn+1 = xn+1 |Xn = xn , ..., X0 = x0 ) = P(Xn+1 = xn+1 |Xn = xn ).

Remarque
Cette propriété s’appelle propriété de Markov. Elle traduit le fait que le futur ne dépend du passé
que de l’information la plus récente que l’on possède au sujet du processus.

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 2 / 49

 Chaînes de Markov discrètes

Chaîne de Markov homogène

Définition
Une chaîne de Markov X = (Xk )k∈N est dite homogène (dans le temps) si la probabilité
suivante ne dépend pas de n

P(Xn+1 = j|Xn = i) := Gij (∀n ≥ 0)

cette probabilité ; on l’appelle la probabilité de passage de l’état i en l’état j, en une étape, ou

en une transition.

Remarque
- Une chaîne est homogène si les changements d’états ne dépend que de l’état, et pas de la
date.
Ainsi, la probabilité de passer de l’état i à l’état j entre les instants t = 0 et t = 1, ou
encore entre t = 100 et t = 101 est la même : elle vaut

P(X1 = j|X0 = i) = P(X101 = j|X100 = i).

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 3 / 49

 Chaînes de Markov discrètes

Matrice de transition d’une chaîne de Markov

Définition
On appelle matrice de transition d’une chaîne de Markov homogène la matrice
G = (Gij )i,j∈E d’éléments

Gij = P(Xn+1 = j|Xn = i), i, j ∈ E .

Proposition
La matrice G est une matrice stochastique, c’est-à-dire une matrice dont les éléments vérifient
les deux propriétés :
1. Gij ≥ 0 ∀(i, j) ∈ E 2 ;
P
2. ∀i ∈ E j∈E
Gij = 1.

Exercice
Démontrer cette proposition.

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 4 / 49

 Chaînes de Markov discrètes

Preuve.
Le premier point découle trivialement du fait que les Gij sont des probabilités et le second de
l’égalité : X
Gij = P(Xn+1 ∈ E /Xn = i) = 1
j∈E

pour tout i dans E .

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 5 / 49

 Exemples classiques de Chaîne de Markov

Exemple 1 : Chaîne à deux états : (Ligne téléphonique)

Considérons l’état d’une ligne de téléphone Xn = 0 si la ligne est libre à l’instant n, et Xn = 1 si

la ligne est occupée. Supposons que sur chaque intervalle de temps, il y a une probabilité p
qu’un appel arrive (un appel au plus). Si la ligne est déjà occupée, l’appel est perdu. Supposons
également que si la ligne est occupée au temps n, il y a une probabilité q qu’elle se libère au
temps n + 1.

Exercice
Modéliser cette situation à l’aide d’une chaîne de Markov.

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 6 / 49

 Exemples classiques de Chaîne de Markov

Exemple 1 (solution)

On peut modèliser la situation précédente avec une chaîne de Markov à valeurs dans

E = {0, 1},
avec matrice de transition  
1−p p
G= .
q 1−q

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 7 / 49

 Exemples classiques de Chaîne de Markov

Exemple 2 : File d’attente simple

On modifie l’exemple précédent en supposant qu’on peut mettre un appel en attente. Les appels
arrivent et la ligne se libère comme avant. Si un appel arrive pendant que la ligne est occupée et
si le système n’est pas saturé, l’appel est mis en attente. Si un appel arrive alors qu’il y a déjà
un en attente, il est perdu.

Exercice
Modéliser la nouvelle situation à l’aide d’une chaîne de Markov.

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 8 / 49

 Exemples classiques de Chaîne de Markov

Exemple 2 (solution)
Cette fois l’espace E = {0, 1, 2}. On a

G00 = 1 − p, G01 = p, G02 = 0.

De même
G20 = 0, G21 = q, G22 = 1 − q.

Le cas où il y a exactement un appel retenu : On a

G10 = q(1 − p) (l’appel se termine et pas d’appel nouveau arrive).
G12 = p(1 − q) (un appel nouveau arrive et celui en cours continu).
Comme la somme doit avoir 1, on a

G10 + G11 + G12 = 1 ⇒ G11 = 1 − q(1 − p) − p(1 − q).

Finalement, la matrice de transition de la chîne est

!
1−p p 0
G= q(1 − p) 1 − q(1 − p) − p(1 − q) p(1 − q)
0 q 1−q

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 9 / 49

 Equation de Chapman-Kolmogorov

Probabilité de transition en n étapes

Définition
La probabilité de passer de l’état i à l’état j en n étapes est donnée par : pour tout (i, j) ∈ E 2 :

P(Xm+n = j|Xm = i) = P(Xn = j|X0 = i) ∀m ∈ N.

où la dernière égalité est justifiée par l’homogénéité de la chaîne.

Proposition
Soit X = (Xk )k∈N une chaîne de Markov de matrice de transition G. Pour n ∈ N, on note
G n = G × G × ... × G .
| {z }
n fois
La probabilité de transition en n étapes de l’état i à l’état j est donnée par :

(n)
P(Xn = j|X0 = i) = Gij .

(n)
où Gij désigne l’élément d’indices (i, j) de la matrice G n .
Autrement dit, la matrice de transition en n étapes est égale à la puissance nieme de la matrice
de transition en une étape.

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 10 / 49

 Equation de Chapman-Kolmogorov

Remarque
Par commodité, on a noté
(n)
Gij = (G n )ij .

Ne pas confondre cette quantité avec (Gij )n .

Interprétation : La distribution de Xn en partant de X0 = i est donnée par la i-ième ligne de la

matrice G n .

Exercice
Démontrer la proposition. (Ind. Raisonner par récurrence).

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 11 / 49

 Equation de Chapman-Kolmogorov

Preuve.
La formule est triviale pour n = 0 puisque G 0 = I. Elle est également vraie pour n = 1.
Supposons maintenant qu’elle soit vraie jusqu’au rang n. L’homogénéité de la chaîne nous
permet alors d’écrire, pour tout (i, j) ∈ E 2 :
(n+1) P
Gij = P(Xn+1 = j/X0 = i) = k∈E
P(Xn+1 = j, Xn = k/X0 = i)
P P (n)
= k∈E
P(Xn+1 = j/Xn = k)P(Xn = k/X0 = i) = k∈E
Gkj Gik .

On a donc, en prenant l’écriture matricielle et en utilisant l’hypothèse de récurrence,

G (n+1) = G (n) G = G n G = G n+1 .

ce qui prouve bien le résultat.

Nous allons montrer que la connaissance des probabilités de transition du système , pour des
durées n et m, permet de calculer les probabilités de transition sur une durée m + n :

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 12 / 49

 Equation de Chapman-Kolmogorov

Equation de Chapman-Kolmogorov
Proposition
Soit (Xk )k∈N une chaîne de Markov d’espace détats E . ∀i, j ∈ E , ∀n, m ∈ N, on a
X
P(Xn+m = j|X0 = i) = P(Xm = j|X0 = k) × P(Xn = k|X0 = i).
k∈E

Soit sous forme matricielle X

(m+n) (n) (m)
Gij = Gik × Gkj
k∈E

Exercice
Démontrer cette proposition.

Preuve.
Cela découle directement des propriétés du produit matriciel.

G (m+n) = G n+m = G n G m = G (n) G (m) ,

et cette formule est bien évidemment symétrique en m et n.

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 13 / 49
 Equation de Chapman-Kolmogorov

Proposition
Pour tout entier n positif, la matrice de transition en n étapes G (n) est également une matrice
stochastique.

Exercice
Démontrer la proposition.

Preuve. Soit n ∈ N. Les éléments de la matrice G (n) sont positifs puisqu’il s’agit de probabilités
et on a de plus :
X (n)
X
Gij = P(Xn = j/X0 = i) = P(Xn ∈ E /X0 = i) = 1.
j∈E j∈E

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 14 / 49

 Equation de Chapman-Kolmogorov

Exercice
Soit X = (Xk )k∈N une chaîne de Markov de matrice de transition G. Soit n ≥ 0 , r ≥ 1 deux
entiers. Montrer que

P(Xn+1 = jn+1 , ..., Xn+r = jn+r /X0 = i0 , ..., Xn = in )

= Gin ,jn+1 Gjn+1 ,jn+2 ...Gjn+r −1 ,jn+r .

Indication : faire une démonstration par récurrence sur r .

Posons
A1 = {X0 = i0 , ..., Xn = in };
A2 = {Xn+1 = jn+1 , ..., Xn+r −1 = jn+r −1 };
A3 = {Xn+r = jn+r }.
Conclure en utilisant l’identité :

P(A2 , A3 /A1 ) = P(A3 /A1 , A2 )P(A2 /A1 ).

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 15 / 49

 Graphe associé à une chaîne de Markov homogène

Le graphe de transition

A partir de la matrice de transition d’une chaîne de Markov, nous construisons un graphe. Il

donne les mêmes informations que la matrice mais, comme toute représentation graphique, a
l’avantage d’être plus parlant.

Définition
Lorsque le nombre d’états n’est pas trop grand, il est possible de représenter l’évolution de la
chaîne de markov à l’aide du graphe de transition : Les états forment les sommets tandis
qu’une flèche qui joint l’état i à l’état j si pij > 0.

Remarque
Utilité d’un graphe :
(i) On voit directement si le système peut passer d’un état à un autre (dans un temps fini).
(ii) On étudie plus facilement les propriétés des états du système.
(iii) On classifie plus facilement les états du système.

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 16 / 49

 Graphe associé à une chaîne de Markov homogène

Exercice
1. Faire le graphe associé à la chaîne de Markov d’espace d’états E = {0, 1, 2} et dont la
matrice de transition en une étape est :

1 1 1
!
2 4 4
1 1
P= 2
0 2
1 1
0 2 2

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 17 / 49

 Graphe associé à une chaîne de Markov homogène

Exercices

Exercice (La marche aléatoire sur Z)

On considère une suite de variables aléatoires (Yn )n≥1 à valeurs dans Z indépendantes et de
même loi, et Y0 une variable aléatoire à valeurs dans Z, indépendante des (Yn )n≥1 . Posons

X0 = Y0
Pn+1
Xn+1 = Xn + Yn+1 = Y ,
k=0 k
n ≥ 0.

1 Montrer que (Xn )n≥0 est une chaîne de Markov

On suppose maintenant que Y1 est à valeurs dans {−1, 1} de loi,

P[Y1 = 1] = p, P[Y1 = −1] = 1 − p,

où 0 < p < 1.
2 Donner la matrice de transition et dessiner le graphe de cette chaîne de Markov.
Définition. Si p = 1 − p = 12 , (Xn )n≥0 s’appelle la marche aléatoire simple sur Z.

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 18 / 49

 Graphe associé à une chaîne de Markov homogène

Solution de l’exercice
1 La chaîne (Xn )n≥0 est à valeurs dans E = Z . Pour tout x0 , ..., xn+1 ∈ Z , on a :

P[Xn+1 =xn+1 ,Xn =xn ,...,X0 =x0 ]

P[Xn+1 = xn+1 |Xn = xn , ..., X0 = x0 ] = P[Xn =xn ,...,X0 =x0 ]

P[Yn+1 =xn+1 −xn ,Xn =xn ,...,X0 =x0 ]

= P[Xn =xn ,...,X0 =x0 ]

= P[Yn+1 = xn+1 − xn ], (indépendance)

P[Yn+1 =xn+1 −xn ]×P[Xn =xn ]

= P[Xn =xn ]

P[Yn+1 =xn+1 −xn ,Xn =xn ]

= P[Xn =xn ]
, (indépendance)

= P[Xn+1 = xn+1 |Xn = xn ].

Ainsi (Xn )n≥0 est une chaîne de Markov. De plus, on a montré que pour tout (x , y ) ∈ Z 2

P[Xn+1 = y |Xn = x ] = P[Yn+1 = y − x ] = P[Y1 = y − x ],

la suite (Yn )n≥0 étant identiquement distribuée. Cette quantité ne dépend pas de n et la chaîne
est donc homogène.
LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 19 / 49
 Graphe associé à une chaîne de Markov homogène

Solution de l’exercice (suite)

2. La matrice de transition G = Gij est de taille infinie. Les lignes et les colonnes sont
indexées par Z et on a

P[Xn+1 = j|Xn = i] = P[Yn+1 = j − i] = P[Y1 = j − i],

Ainsi, pour tout i ∈ Z , la i-ième ligne a pour seuls coefficients non nuls :

G(i, i − 1) = 1 − p et G(i, i + 1) = p.

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 20 / 49

 Dynamique d’une chaînes de Markov

Dans ce paragraphe, nous donnons une caractérisation d’une chaîne de Markov et étudions sont
évolution dans le temps.
On introduit la fonction de masse de la v. a. discrète X0 ,

PX0 : E −→ [0, 1]
(0)
k −→ πk = P(X0 = k).

(0)
On définit le vecteur ligne π (0) = (πk )k∈E .

Proposition
Soit X = (Xn )n∈N une chaîne de Markov homogène de matrice de transition G. Posons, pour
tout entier n ∈ N, et k ∈ E ,
(n)
πk = P(Xn = k).
(n)
Alors, le vecteur π (n) = (πk )k∈E est obtenu en effectuant le produit du vecteur ligne π (0) par la
matrice G n .
Autrement dit :

π (n) = π (0) G n . (∗)

Exercice
Démontrer cette proposition.

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 21 / 49

 Dynamique d’une chaînes de Markov

Remarque
(n)
- π (n) = (πk )k∈E = (P(Xn = k))k∈E : le vecteur des probabilités des états du système à
l’instant n est appelé régime du système à l’instant n. C’est un vecteur stochastique.

- L’équation (∗) signifie que la situation du système càd les probabilités des états est
entierement déterminée par π (0) et G.

Preuve. Pour i ∈ E , d’après le Théorème des probabilités totales, on a :

X X (n) (0)
P(Xn = i) = P(Xn = i/X0 = k)P(X0 = k) = Gki πk .
k∈E k∈E

Cette dernière égalité représente le produit du vecteur π (0) par la iieme colonne de G n .

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 22 / 49

 Dynamique d’une chaînes de Markov

Exercice
Montrer que
π (n) = π (n−1) G.

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 23 / 49

 Dynamique d’une chaînes de Markov

Exercice
Montrer que
π (n) = π (n−1) G.

On a
(n)
πk P n = k, ∪j∈E Xn−1 = j)
= P(X
= j∈E
P(Xn = k, Xn−1 = j)
Gjk πjn−1 .
P P
= j∈E
P(Xn = k/Xn−1 = j)P(Xn−1 = j) = j∈E

Donc
π (n) = π (n−1) G.

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 23 / 49

 Dynamique d’une chaînes de Markov Caractérisation de la loi d’une chaîne de Markov

Loi d’une chaîne de Markov homogène

Montrons maintenant que la donnée d’une matrice de transition G et la loi initiale π (0) = PX0
permet de caractériser une chaîne de Markov (Xn )n∈N , c’est-à-dire de déterminer la loi de
(X0 , ...., Xn ) pour tout entier n.

Proposition
Soit X = (Xn )n∈N une chaîne de Markov homogène sur un espace d’états E , de matrice de
transition G et de loi initiale π (0) . Pour tout entier n et tout (n + 1)−uplet (x0 , ..., xn ) ∈ E n+1 ,
on a
(0)
P(X0 = x0 , ..., Xn = xn ) = πx0 Gx0 ,x1 Gx1 ,x2 ...Gxn−1 ,xn

Remarque
La matrice de transition en une étape et le vecteur π (0) déterminent la loi de la chaîne de
Markov homogène.

Exercice
Démontrer cette proposition.

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 24 / 49

 Dynamique d’une chaînes de Markov Caractérisation de la loi d’une chaîne de Markov

Preuve. Ce résultat se démontre par récurrence. Pour n = 0, on a

(0)
P(X0 = x0 ) = πx0 .

Supposons le résultat soit vrai jusqu’au rang n et montrons le pour n + 1.

P(X0 = x0 , ..., Xn+1 = xn+1 )

= P(Xn+1 = xn+1 /Xn = xn , Xn−1 = xn−1 , ..., X0 = x0 ).P(Xn = xn , Xn−1 = xn−1 , ..., X0 = x0 )

= P(Xn+1 = xn+1 /Xn = xn ).P(Xn = xn , Xn−1 = xn−1 , ..., X0 = x0 )

(0)
= Gxn ,xn+1 πx0 Gx0 ,x1 Gx1 ,x2 ...Gxn−1 ,xn (d’après l’ H. R.)

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 25 / 49

 Dynamique d’une chaînes de Markov Caractérisation de la loi d’une chaîne de Markov

Exercice
Soit (Xn )n∈N une chaîne de markov homogène sur l’ensemble {1, 2}, de distribution initiale
µ0 = ( 51 , 45 ) et de matrice de transition
 
2 1
P= 3 3
1 5
6 6

- Calculer P(X0 = 2, X1 = 2), P(X1 = 2) et P(X0 = 2|X1 = 2).

Solution :
5 4
On a P(X0 = 2, X1 = 2) = P(X1 = 2/X0 = 2).P(X0 = 2) = 6
× 5
= 23 .
On a le régime du système à l’instant 1 est donné par

(P(X1 = 1), P(X1 = 2)) = µ0 .P.

Donc
1 20 22
P(X1 = 2) = + = .
15 30 30
2
3 10
P(X0 = 2|X1 = 2) = 22 = 11
.
30

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 26 / 49

 Dynamique d’une chaînes de Markov Caractérisation de la loi d’une chaîne de Markov

Classification des états d’une chaîne de Markov

Les états d’une chaîne de Markov se répartissent en classe que l’on définit à l’aide de sa matrice
de transition.

Définition
On dit que l’état j est accessible à partir de l’état i et on note i −→ j, si la probabilité de passer
de i à j est non nulle :
(n)
∃n ∈ N, Gij > 0.

Ceci signifie qu’il existe un chemin entre i et j.

Remarque
(0)
étant donné que l’on inclut n = 0 dans la définition et que Gii = 1 > 0. Tout état est
accessible à partir de lui-même.

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 27 / 49

 Dynamique d’une chaînes de Markov Caractérisation de la loi d’une chaîne de Markov

Définition
On dit que les états i et j communiquent et on note i ←→ j, si chacun d’eux est accessible à
partir de l’autre.

Proposition
La relation de communication entre deux états est une relation d’équivalence.

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 28 / 49

 Dynamique d’une chaînes de Markov Caractérisation de la loi d’une chaîne de Markov

Définition
On dit que les états i et j communiquent et on note i ←→ j, si chacun d’eux est accessible à
partir de l’autre.

Proposition
La relation de communication entre deux états est une relation d’équivalence.

Preuve. (réflexive) tout état communique avec lui même, (symétrique) par définition et
(transitive) d’après les équations de Chapman-Kolmogorov :
(m+n) (m) (n)
Gik ≥ Gij Gjk > 0, pour tous les m, n ≥ 0.

Remarque
1 On a vu que tout état d’une chaîne de Markov communique avec lui même, puisque l’on a
(0) (n)
Gii = 1. En revanche, s’il existe n > 0, tel Gii > 0, alors l’état i est dit état de retour et
état de non retour dans le cas contraire.
2 Si i ←→ j, on dit que les états i et j sont dans la même classe.

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 28 / 49

 Dynamique d’une chaînes de Markov Etats récurrents et transients

Définition
1 Un état j ∈ E tel que, lorsque la chaîne est issue de ce point, elle y retourne en un temps
fini avec une probabilité strictement positive, s’appelle un état récurrent (sinon l’état est
dit transitoire).
2 Une classe d’équivalence est dite récurrente, resp. transiente, si un de ses sommets est
récurrent, resp. transient.
3 Une classe est dite récurrente si elle est impossible de la quetter. Si une classe récurrente
est constituée d’un seul état, cet état est dit absorbant.
4 Une classe est dite transitoire s’il est possible d’en sortir.
5 L’espace des états SXn d’une chaîne de Markov se décompose comme suit :

SXn = D ∪ C1 ∪ C2 ∪ C3 ...

où D est l’enseble des état transitoires de la chaîne de Markov et les Ck , k = 1, 2, 3, ...

sont des ensembles d’états récurents (c’est-à-dire que les états de chacun de ces
ensembles communiquent).

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 29 / 49

 Dynamique d’une chaînes de Markov Etats récurrents et transients

Considérons la chaîne de Markov dont l’ensemble des états est E = {0, 1, 2, 3}, la matrice de
transition :  1 1 
2 2
0 0
 1 12 0 0 
G =  21 1 1 1 
4 4 4 4
0 0 0 1

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 30 / 49

 Dynamique d’une chaînes de Markov Etats récurrents et transients

Considérons la chaîne de Markov dont l’ensemble des états est E = {0, 1, 2, 3}, la matrice de
transition :  1 1 
2 2
0 0
 1 12 0 0 
G =  21 1 1 1 
4 4 4 4
0 0 0 1

La chaîne comporte trois classe {0, 1}, {2} et {3}. Les états {0, 1} et {3} sont récurrentes, la
classe {2} est transitoire. La classe {3} est absorbante.

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 30 / 49

 Dynamique d’une chaînes de Markov Etats récurrents et transients

Définition
Une chaîne de Markov pour laquelle il n’existe qu’une seule classe (forcément récurrente) est
dite irréductible.

Exemples
Considérons la chaîe de Markov dont l’ensemble des états est E = {0, 1, 2}, la matrice de
transition :
1 1
!
2 2
0
1 1 1
G= 2 4 4
0 13 2
3

La chaîne comporte une seule classe ; tous les états communiquent : c’est une chaîne irréductible.

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 31 / 49

 Dynamique d’une chaînes de Markov Etats récurrents et transients

Exercice
L’observation du développement d’un organisme animal au cours du temps fait apparaitre
l’ensemble des états suivants : juvenile, maturité, sénescence et décès, que nous noterons
respectivement j, m, s et d, avec des probabilités de passage d’un état vers un autre données par
la matrice suivante :  
0.2 0.2 0 0.6
0 0.55 0.15 0.3
T = 
0 0 0.1 0.9
0 0 0 1

1 Tracer le diagramme en points et flèche. La chaîne est-elle irréductible ?

2 Calculer la probabilité de passer en deux étapes de l’état de maturité à l’état de
sénescence. Calculer la matrice T 2 et vérifier la probabilité calculée précédemment.
3 Pour chaque état, indiquer s’il est absorbant, transitoire, récurrent.

Exercice
Déterminer quelles sont les chaînes irréductibles parmi les exemples précédents : Chaîne à deux
états et file d’attete simple.

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 32 / 49

 Dynamique d’une chaînes de Markov Etats récurrents et transients

Solution :
1 Un examen du schéma en points et flèches montre que la chaîne n’est pas irréductible : en
effet, on ne peux pas passer de l’état de maturité à l’état juvenile. De plus l’état décès est
absorbant.
2 Sur le schéma en points et flèches, on voit facilement que, partant de l’état m, on atteint
l’état s en deux étapes de deux façons exactement : soit on reste en m pendant la première
étape puis on va en s durant la seconde, soit on y va durant la première et on reste en s
durant la seconde. Il n’y a pas d’autres possibilités. Cela conduit au calcul suivant :

P(X2 = s/X0 = m) = P(X2 = s, X1 ∈ E /X0 = m)

= P(X2 = s/X1 = m).P(X1 = m/X0 = m) + P(X2 = s/X1 = s).P(X1 = s/X0 = m)
= 0, 15.0, 55 + 0, 15.0, 1 = 0, 0975.

La probabilité cherchée se lit aussi sur la matrice T 2 , c’est le coefficient de la deuxième

ligne et de la troisième colonne, ce qui confirme le résultat trouvé.
3 Les trois états j, m et s sont transitoires. L’état d est absorbant donc récurrent.

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 33 / 49

 Dynamique d’une chaînes de Markov Périodicité

Périodicité
Définition
Soit i ∈ E , on appelle d période de l’état i le plus grand commun diviseur de tous les n ∈ N∗
(n)
pour les quels Gii > 0. i.e.

(n)
d = pgcd{n ∈ N∗ t.q. Gii > 0}.

Si d = 1 on dira que l’état i est apériodique. La chaîne est dite est apériodique si tous ses états
sont apériodiques.

Remarque
n désigne le nombre d’étapes pour le retour à l’état i.
Une C.S. d’apériodicité est que le graphe possède une boucle dans un sommet i : alors
(1)
Gii = Gii > 0 et pgcd{1, ...} = 1. Ainsi, une chaîne irréductible est apériodique s’il y a
au moins un élément positif sur la diagonale de la matrice de transition G.
La chaîne donnée par l’exemple de la page 31 est apériodique :

(1) 1
G11 = >0 =⇒ pgcd{1, ...} = 1.
4

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 34 / 49

 Dynamique d’une chaînes de Markov Périodicité

Exemples
Soit
1 1
!
0 2 2
1 1
G= 2
0 2
1 1
2 2
0

La chaîne de Markov assoucié à G est irréductible et apériodique. En effet

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 35 / 49

 Dynamique d’une chaînes de Markov Périodicité

Exemples
Soit
1 1
!
0 2 2
1 1
G= 2
0 2
1 1
2 2
0

La chaîne de Markov assoucié à G est irréductible et apériodique. En effet

1 1
G01 × G12 × G20 = > 0. et G01 × G10 = > 0.
8 4

Et
(2) (3)
G00 > 0 et G00 > 0.

Donc
pgcd{2, 3, ..} = 1.

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 35 / 49

 Probabilités stationnaires Comportement asymptotique d’une chaîne de Markov

Dans ce paragraphe, on se limite aux chaînes finies c’est-à-dire ayant un nombre fini N d’états. Nous avons vu que
π (n) = π (0) G n où π (n) est la distribution de probabilité à l’instant n.

Question

A quelle conditions sur la matrice G, cette distribution π (n) a-t-elle une limite π lorsque n tend vers l’infini ?

Remarquons que si π existe, on doit avoir :

(n) (n−1) (n−1)

π= lim π = lim (π G) = lim π G = πG.
n−→∞ n−→∞ n−→∞

Ceci conduit à :

Définition

On appelle loi invariante ou loi stationnaire de la chaîne de Markov homogène X toute loi π qui vérifie

π = πG.

Remarque

Pour justifier la terminologie, on voit que si π est une probabilité invariante et si l’état initial de la chaîne X0 suit la loi
π, alors Xn suit également la loi π pour tout n (puisque la loi de Xn est π (n) = πG n = π).
Ceci signifie que la loi de la v. a. r. Xn pour tout n est la fonction de masse π.
Les probabilités invariantes représentent les états d’équilibre du système.
le vecteur colonne π est un vecteur propre de G t pour la valeur propre 1.

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 36 / 49

 Probabilités stationnaires Comportement asymptotique d’une chaîne de Markov

• Le calcul des probabilités stationnaires se réduit à la résolution d’un système linéaire. Il est
souvent très grand .
 P
i∈E
πi = 1
π = πG avec
πi ≥ 0 ∀i ∈ E ,

Remarque
Il est important dans un premier temps de souligner que si la chaîne de Markov n’est pas
irréductible, il peut y avoir plusieurs lois stationnaires. Par exemple
 
1 0
G=
0 1

La chaîne de Markov possède 2 classes {0} et {1}. Le système à résoudre pour obtenir Les πj est

π = πG et π1 + π2 = 1

On trouve

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 37 / 49

 Probabilités stationnaires Comportement asymptotique d’une chaîne de Markov

• Le calcul des probabilités stationnaires se réduit à la résolution d’un système linéaire. Il est
souvent très grand .
 P
i∈E
πi = 1
π = πG avec
πi ≥ 0 ∀i ∈ E ,

Remarque
Il est important dans un premier temps de souligner que si la chaîne de Markov n’est pas
irréductible, il peut y avoir plusieurs lois stationnaires. Par exemple
 
1 0
G=
0 1

La chaîne de Markov possède 2 classes {0} et {1}. Le système à résoudre pour obtenir Les πj est

π = πG et π1 + π2 = 1

On trouve
π = (1 − λ, λ)
pour tout λ ∈ [0, 1].

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 37 / 49

 Probabilités stationnaires Comportement asymptotique d’une chaîne de Markov

Question
A quelles conditions sur G la loi invariante est unique, i.e. l’équation

π = πG

admet une unique solution.

La réponse à cette question peut-être abordée par la structure spectrale (valeurs propres et
vecteurs propres) spéciale de la matrice de transition G.

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 38 / 49

 Probabilités stationnaires Comportement asymptotique d’une chaîne de Markov

Ergodicité

Définition
Lorsque la chaîne est irréductible et apériodique on dit que la chaîne est ergodique.

Remarque
L’ergodicité caractérise les systèmes qui possèdent un régime stationnaire indépendamment du
régime initial π (0) .
∃!π t.q. π = lim π n ∀π (0) .
n−→∞

Plus précisemment, on a le théorème suivant :

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 39 / 49

 Probabilités stationnaires Comportement asymptotique d’une chaîne de Markov

Théorème
Soit (Xn )n∈N est une chaîne homogène ergodique de matrice de transition G, alors
1. Il existe une unique loi invariante π ; i.e. π = πG.
2. ∀(i, k) ∈ E 2 limn−→+∞ (G n )ik = πk ,
3. Quelle que soit la loi de X0 , la suite de v. a. r. (Xn )n∈N converge en loi vers la loi de
probabilité invariante π :
lim π (n) = π
n∞

Autrement dit, pour n grand

P(Xn = k) = πk ∀k ∈ E .

Remarque
1. Ce résultat exprime qu’au bout d’un certain temps, le système se stabilise dans un régime
d’équilibre appelé " régime stationnaire" et que la probabilité d’être dans l’état k en
régime stationnaire est donnée par πk ,
2. Le point 2) implique que la matrice G ∗ = limn−→∞ G n a toutes ses lignes identiques et
égales au vecteur π.

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 40 / 49

 Probabilités stationnaires Comportement asymptotique d’une chaîne de Markov

Théorème Ergodique / Loi des grands nombres, (admis)

Le théorème ergodique généralise la LGN à des systèmes dynamiques où les observations

successives ne sont pas indépendantes mais proviennent d’une même trajectoire d’une chaîne de
Markov. Plus précisément :
Soit (Xn )n∈N une chaîne de Markov irréductible et apériodique admettant une mesure de
probabiliteé invariante π. Pour toute fonction f : E → R (où E est l’espace d’états de la chaîne)
telle que X
|f (e)|π(e) < ∞,
e∈E

on a
N−1
1 X X
f (Xn )) →p.s.
N→∞
= Eπ (f ) = f (e)π(e).
N
n=0 e∈E

Interprétation : La moyenne empirique des valeurs de f (Xk ) le long d’une trajectoire de la chaîne
converge presque sûrement vers l’espérance de f sous la distribution stationnaire π.

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 41 / 49

 Applications

Processus météo (Chaîne de Markov à deux états)

Exercice

Supposons qu’on modélise le temps à l’aide de deux états :

E = {ensoleillé, pluvieux}.

La matrice de transition est donnée par :  

0.8 0.2
P = ,
0.4 0.6

Question : Quel est le pourcentage à long terme de journées ensoleillées et pluvieuses ?

étapes de calcul : P
1. Distribution stationnaire : Résolvons πP = π, avec la contrainte π(i) = 1
i

  n
π(ensoleillé) 0.8π(ensoleillé) + 0.4π(pluvieux) = π(ensoleillé),
π= ,
π(pluvieux) 0.2π(ensoleillé) + 0.6π(pluvieux) = π(pluvieux).

2. Résolution :
2 1
π(ensoleillé) = , π(pluvieux) = .
3 3
3. Moyenne temporelle : On prend f = Iensoleillé , ce qui donne : Si f (ensoleillé) = 1 et f (pluvieux) = 0, alors :

n−1
1 2
X
f (Xk ) → Eπ [f ] = π(ensoleillé) = .
n 3
LAKHEL El Hassan k=0 Chaînes de Markov Université Cadi Ayyad 42 / 49
 Applications

Exercice

On modélise le fonctionnement d’une machine. Pour simplifier, on considérera qu’on observe la machine à chaque heure et
qu’elle a trois états possibles : 1 (bon état), 2 (mauvais état) et 3 (en panne). Le passage d’un état donné à l’état une heure
après se fait de la façon suivante :
quand la machine est en bon état, il y a 9 chances sur 10 qu’elle le reste, et 1 chance sur 10 qu’elle devienne en mauvais état ;
quand elle est en mauvais état, il y a 3 chances sur 5 qu’elle le reste, 1 chance sur 5 pour qu’elle tombe en panne, et 1 chance
sur 5 pour qu’un technicien s’en aperçoive et la répare. La réparation remet la machine en bon état.
quand la machine tombe en panne, un technicien vient immédiatement la réparer. Une heure après, elle redémarre en bon état.
On note Xn l’état de la machine au bout de n heures.
1 Dessiner le graphe de la chaîne de Markov représentant les états de la machine, et écrire sa matrice de transition.
2 Ce matin, la machine a démarré en bon état. Quelle est la probabilité que trois heures après elle soit en bon état ?
3 La chaîne est-elle irréductible ? Est-elle apériodique ?
4 A-t-elle une probabilité invariante ? Si oui, laquelle ?
5 Quelle est la probabilité qu’à un moment quelconque, longtemps après la mise en service de la machine, elle soit en bon
état ?
6 En moyenne sur une longue période, quelle proportion du temps est perdue pour cause de panne ?
Indication :
E = {1 Bon, 2 mauvais, 3 panne}
Ce matin, la machine a démarré en bon état signifie que la loi de X0 est µ0 = (1, 0, 0).

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 43 / 49

 Applications

Solution
1 (Xn ) est une chaîne de Markov homogène de graphe et de matrice
 9 1

10 10
0
G = 2 6 2
10 10 10
1 0 0

2 Ce matin, la machine a démarré en bon état signifie que la loi de X0

µ0 = (1, 0, 0).

Elle sera trois heures apreès dans l’état X3 de loi π (3)

(1) 9 1 (2) (1) 83 15 2 (3) (2) 797 173 30

π = µ0 G = ( , , 0) π =π G =( , , ) π =π G =( , , )
10 10 100 100 100 1000 1000 1000

La probabiliteé que trois heures après la machine soit en bon eétat est P(X3 = 1) = 1000 797 .

3 La chaîne est irréductible (tout état est accessible à partir des autres) donc tous les états ont la même période, qui vaut
1 car G11 > 0 par exemple. La chaîne est donc apériodique.

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 44 / 49

 Applications

Solution (suite)
La chaîne est ergodique sur un espace d’état fini, il existe une loi invariante uniqie π, elle doit satisfaire les conditions

π = πG π 1 + π2 + π3 = 1 et πi ≥ 0 i = 1, 2, 3.

Après le calcul, on trouve l’unique probabiliteé stationnaire est

20 5 1
π=( , , ).
26 26 26
La chaîne étant irréductible et apériodique de probabiliteé stationnaire π = ( 20 , 5 , 1 ), le théorème de convergence
26 26 26
en loi assure que pour tout eétat initial j, on a pour n grand
20
P(Xn = 1|X0 = j) = .
26
La chaine étant irréductible de proba. stationnaire π = ( 20 , 5 , 1 ). Le théoreème ergodique indique que :
26 26 26
Si (Xn ) une chaine de Markov irréductible sur un espace d’états fini, et π sa distribution invariante. Pour toute fonction
f : E → R intégrable, alors
n
1
X X
f (Xk ) → f := f (x )π(x ) = Eπ (f )
n
k=1 x ∈E

On prend f = Ix =3 , ce qui donne :

n 3
1
X X
p.s
IX =3 → Ix =3 π(x ) = π(3).
n k
k=1 x =1

1 .
En moyenne sur une longue période, la proportion du temps perdue pour cause de panne est de 26

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 45 / 49

 Applications

Exercice
(Chaîne à deux états)
Considérons l’état d’une ligne de téléphone Xn = 0 si la ligne est libre à l’instant n, et Xn = 1 si la ligne est occupée. Supposons
que sur chaque intervalle de temps, il y a une probabilité p qu’un appel arrive (un appel au plus). Si la ligne est déjà occupée,
l’appel est perdu. Supposons également que si la ligne est occupée au temps n, il y a une probabilité q qu’elle se libère au temps
n + 1.
On peut modèliser une chaîne de Markov à valeurs dans

E = {0, 1},

avec matrice de transition

 
1−p p
G = (Gij )0≤i,j≤1 = , 0 < p, q < 1.
q 1−q

1. Dessiner son graphe et montrer qu’elle est érgodique ?

2. Déterminer sa probabilité stationnaire Π.

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 46 / 49

 Applications

Solution :
1 Les états 0 et 1 communiquent, la chaîne est irréductible, de plus elle
(1)
est apériodique i.e. d = 1 puisque G00 > 0 . Donc la chaîne est
ergodique.
2 L’équation πG = π s’écrit sous la forme d’un système :
(
(1 − p)π0 + qπ1 = π0
pπ0 + (1 − q)π1 = π1

auquel on ajoute la condition π0 + π1 = 1. On trouve

q p
π0 = , π1 = .
p+q p+q
Interprétation : Au bout d’un temps long le processus se trouve à
q
l’état 0 avec probabilité π0 = p+q et il se trouve à l’état 1 avec
p
probabilité π1 = p+q .

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 47 / 49

 Applications

Exercice
Montrer que la matrice stochastique :
 
0.2 0.2 0.3 0.3
 0 0.1 0.8 0.1 
G =
 
0.1 0 0.2 0.7

 
0.6 0.2 0.1 0.1

élevée à la puissance n, tend vers

 
457 220 458 533
1  457 220 458 533 
G∗ = quand n −→ ∞.
 
457 220 458 533
 
1668  
457 220 458 533

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 48 / 49

 Applications

Solution :
Rappelons que pour une chaîne de Markov ergodique on a la matrice

G ∗ = limn→∞ G n

est une matrice dont toutes les lignes sont identiques, chacune étant égale
au vecteur ligne π.
La chaîne est ergodique : d’abord elle est irréductible, de plus elle est
(1)
apériodique i.e. d = 1 puisque G00 > 0 .
Il suffit de calculer π = (π0 , π1 , π2 , π3 ) solution du système :
(
πG = π
π0 + π1 + π2 + π3 = 1.

On trouve
457 220 458 533
π0 = , π1 = , π2 = , π3 = .
1668 1668 1668 1668

LAKHEL El Hassan Chaînes de Markov Université Cadi Ayyad 49 / 49