PLAN DU COURS

Partie I : Chaînes de Markov – Définitions et

propriétés.
Partie II : Théorie et Applications des chaînes
de Markov à temps discret.
Processus de branchement.

Partie III : Notions sur les chaînes de Markov à

temps continu.

MA62 LST-MA ‫فحصي‬

Vu .‫ن‬
Pham 1
 PRÉREQUIS POUR LE MODULE
Calcul matriciel ;
Espaces probabilisés : mesure de probabilité,
événement, … ;
Conditionnement : formule des probabilités totales;
Variables aléatoires ;
Loi de variables aléatoires : Espérance, variance, … ;
Fonctions génératrices de probabilités;
Lois de probabilité classiques discrètes et continues :
loi de Bernoulli, binomiale, de Poisson, géométrique,
exponentielle, normale.

MA62 LST-MA ‫فحصي‬

Vu .‫ن‬
Pham 2
 PROCESSUS ALÉATOIRES : GÉNÉRALITÉS

MA62 LST-MA ‫فحصي‬

Vu .‫ن‬
Pham Processus aléatoires : Généralités 3
 PROCESSUS ALÉATOIRES : GÉNÉRALITÉS

MA62 LST-MA ‫فحصي‬

Vu .‫ن‬
Pham Processus aléatoires : Généralités 4
 PROCESSUS ALÉATOIRES : GÉNÉRALITÉS

État du processus
à l’instant 𝑡.

MA62 LST-MA ‫فحصي‬

Vu .‫ن‬
Pham Processus aléatoires : Généralités 5
 PROCESSUS ALÉATOIRES : GÉNÉRALITÉS

MA62 LST-MA ‫فحصي‬

Vu .‫ن‬
Pham Processus aléatoires : Généralités 6
 PROCESSUS ALÉATOIRES : GÉNÉRALITÉS

MA62 LST-MA ‫فحصي‬

Vu .‫ن‬
Pham Processus aléatoires : Généralités 7
 PROCESSUS ALÉATOIRES : GÉNÉRALITÉS

Ce cours traite un exemple très important de

processus stochastiques :

LES CHAÎNES DE MARKOV

MA62 LST-MA ‫فحصي‬
Vu .‫ن‬
Pham Processus aléatoires : Généralités 8
 PARTIE I

MA62 LST-MA Vu Pham

CHAPITRE 1
CHAÎNES DE MARKOV
DÉFINITIONS ET PROPRIÉTÉS DE BASE

10
 I-1. UN EXEMPLE
EXEMPLE
La figure ci-dessous schématise une grenouille sautillant sur 7 feuilles
de nénuphar. Les nombres à côté des flèches indiquent les
probabilités de saut d’une feuille à une autre feuille de nénuphar
voisine. Ainsi, par exemple, la probabilité de saut de la feuille n° 3 à
la feuille n°1 est égale à 1/2, alors que la probabilité que la grenouille
reste sur la feuille n°3 est égale à 1/2.

MA62 LST-MA ‫فحصي‬

Vu .‫ن‬
Pham 11
 UN EXEMPLE DE CHAÎNE DE MARKOV
Il y a 7 «états» (nénuphars). Dans la matrice 𝑃 l'élément 𝑝57 (= 1/2)
est la probabilité que, lors du démarrage de l'état 5, le prochain
saut prend la grenouille à l'état 7. Nous aimerions savoir où va la
grenouille, combien de temps faut-il pour y arriver, et qu’est ce qui
se passe à long terme ? Plus précisément :

1. À partir de l'état 1, quelle est la probabilité que la grenouille est

3
encore à l'état 1 après 3 pas ? (𝑝11 = 1/4) après 5 étapes ?
(𝑛)
(𝑝115 = 3/16) ou après 1000 pas? (≈ 1/5 comme lim 𝑝11 = 1/5)
𝑛→∞
2. Partant de l’état 4, quelle est la probabilité que la grenouille
n’atteint jamais la feuille n° 7? (= 1/3)
3. Partant de l’état 4, combien de temps en moyenne faut-il pour
atteindre soit 3 ou 7? (= 11/3).

MA62 LST-MA ‫فحصي‬

Vu .‫ن‬
Pham Chaînes de Markov : Un exemple 12
 CHAÎNES DE MARKOV

Les chaînes de Markov constituent l’exemple

le plus simple des processus stochastiques.
Elles ont été introduites en 1906 par Andrei
A. Markov.
Markov (1856-1922)

Elles sont intuitivement très simples à définir. Un système

peut admettre un certain nombre d’états différents. L’état
change au cours du temps discret. A chaque changement,
le nouvel état est choisi avec une probabilité fixée au
préalable, et ne dépendant que de l’état présent.
MA62 LST-MA ‫فحصي‬
Vu .‫ن‬
Pham Chaînes de Markov : Définitions et propriétés 13
 I-2. DÉFINITION ET PREMIÈRES PROPRIÉTÉS
Soit 𝑋𝑛 𝑛≥0 une suite de variables aléatoires à valeurs
dans l’ensemble 𝐸 des états, supposé ⊆ ℕ. On dit que
cette suite est une chaîne de Markov, si pour tout 𝑛 ≥ 1 et
toute suite (𝑖0 , … , 𝑖𝑛−1 , 𝑖, 𝑗) d’éléments de 𝐸 , pour
lesquelles ℙ 𝑋0 = 𝑖0 , … , 𝑋𝑛−1 = 𝑖𝑛−1 , 𝑋𝑛 = 𝑖 > 0, on a la
relation suivante entre probabilités conditionnelles :

ℙ 𝑋𝑛+1 = 𝑗 |𝑋0 = 𝑖0 , … , 𝑋𝑛−1 = 𝑖𝑛−1 , 𝑋𝑛 = 𝑖 (1)

= ℙ 𝑋𝑛+1 = 𝑗 |𝑋𝑛 = 𝑖 .

Propriété de Markov

MA62 LST-MA ‫فحصي‬

Vu .‫ن‬
Pham Chaînes de Markov : Définitions et propriétés 14
 I-2. DÉFINITION ET PREMIÈRES PROPRIÉTÉS
Dans l’évolution au cours du temps, l’état du processus à
l’instant (𝑛 + 1)ne dépend que de celui à l’instant 𝑛
précédent, mais non de ses états antérieurs. Le processus
est sans mémoire ou non héréditaire.

Définition 1. La chaîne de Markov est dite homogène (dans

le temps), si la probabilité précédente ne dépend pas de 𝑛.
Soit
𝑝𝑖,𝑗 ≔ ℙ 𝑋𝑛+1 = 𝑗 𝑋𝑛 = 𝑖) (𝑛 ≥ 0) (2)
cette probabilité est appelée la probabilité de passage de
l’état 𝑖 à l'état 𝑗, en une étape, ou en une transition.

MA62 LST-MA ‫فحصي‬

Vu .‫ن‬
Pham Chaînes de Markov : Définitions et propriétés 15
 I-2. DÉFINITION ET PREMIÈRES PROPRIÉTÉS

Définition 2. La matrice

𝑝0,0 𝑝0,1 𝑝0,2 ⋯

𝒫 = 𝑝1,0 𝑝1,1 𝑝1,2 ⋯
⋮ ⋮ ⋮ ⋮⋮⋮

dont les coefficients sont les probabilités de transition 𝑝𝑖,𝑗

est appelée matrice de transition de la chaîne. C'est une
matrice finie ou infinie dénombrable, suivant que
l'ensemble des états 𝐸 est fini ou dénombrable.

MA62 LST-MA ‫فحصي‬

Vu .‫ن‬
Pham Chaînes de Markov : Définitions et propriétés 16
 I-2. DÉFINITION ET PREMIÈRES PROPRIÉTÉS
Propriété 1. Toute matrice de transition 𝒫 = (𝑝𝑖,𝑗 )
( 𝑖, 𝑗 ∈ 𝐸 2 ) vérifie les propriétés suivantes :
(1) pour tout couple (𝑖, 𝑗), on a : 𝑝𝑖,𝑗 ≥ 0 ;
(2) pour tout 𝑖 ∈ 𝐸, on a
𝑝𝑖,𝑗 = 1
𝑗∈𝐸
Preuve:… … … … ∎

Une matrice vérifiant les propriétés (1) et (2) est appelée

matrice stochastique. La somme des éléments de chaque
ligne vaut 1.
MA62 LST-MA ‫فحصي‬
Vu .‫ن‬
Pham Chaînes de Markov : Définitions et propriétés 17
 I-2. DÉFINITION ET PREMIÈRES PROPRIÉTÉS
Propriété 2. Soit 𝒫une matrice de transition. Alors
(1)𝒫admet la valeur propre 1 ;
(2) on peut associer à cette valeur propre le vecteur
propre 𝑉 = (1,1, … , 1, … ).
Preuve:… … … … ∎
Graphe associé à une matrice de transition.
À toute matrice de transition, on peut associer son graphe.
Les différents états de la chaîne sont les sommets du
graphe. Entre le sommet 𝑖 et le sommet 𝑗, Il y a une flèche
étiquetée 𝑝𝑖,𝑗 , si et seulement si 𝑝𝑖,𝑗 > 0.
Cette présentation est très utile lorsque 𝐸 est fini.
MA62 LST-MA ‫فحصي‬
Vu .‫ن‬
Pham Chaînes de Markov : Définitions et propriétés 18
 I-3. EXEMPLES DE CHAÎNES DE MARKOV
1. La chaîne à deux états
La matrice de transition correspondant à une chaîne à
deux états s’écrit
1−𝛼 𝛼
𝒫= 0 < 𝛼, 𝛽 ≤ 1 .
𝛽 1−𝛽
Dans ce cas, les calculs sont explicites.
Le graphe :

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ Chaînes de Markov : exemples 19
 I-3. EXEMPLES DE CHAÎNES DE MARKOV
2. Le modèle de diffusion d'Ehrenfest
C’est un système motivé par la physique, qui a
été introduit pour modéliser de manière
simple la répartition d’un gaz entre deux
récipients.
Paul Ehrenfest
Deux urnes A et B contiennent, à elles (1880-1933)
deux, 𝑎 boules, numérotées de 1 à 𝑎 . À
chaque instant, on choisit un nombre de 1à 𝑎,
avec une probabilité 1/𝑎. Si ce nombre est 𝑖,
on change d'urne la boule numérotée 𝑖.

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ Chaînes de Markov : exemples 20
 I-3. EXEMPLES DE CHAÎNES DE MARKOV

L'ensemble des états est l'ensemble 𝐸 = {0,1, … , 𝑎}. Le

processus est dit être dans l’état 𝑗 si l'urne A contient 𝑗
boules. Dans ces conditions, si le processus est dans l'état
0 (l'urne A est vide) (resp. l'état 𝑎, à savoir l'urne B est
vide), la probabilité est égale à 1 qu'il passe dans l'état 1
(resp. l'état (𝑎 — 1)).

Pour 𝑎 = 3

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ Chaînes de Markov : exemples 21
 I-3. EXEMPLES DE CHAÎNES DE MARKOV
Le graphe associé est

La matrice de transition est

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ Chaînes de Markov : exemples 22
 I-3. EXEMPLES DE CHAÎNES DE MARKOV
3. Promenade aléatoire sur ℤ
Considérons une chaîne de Markov, homogène dans le
temps, caractérisée par l'ensemble des états 𝐸 ≔ ℤ et
la matrice de transition 𝒫 = (𝑝𝑖,𝑗 ) ( 𝑖, 𝑗 ∈ 𝑍), avec,
pour tout 𝑖, 𝑗 ∈ ℤ2 ,
𝑝, si 𝑗 = 𝑖 + 1;
𝑝𝑖,𝑗 = 1 − 𝑝, si 𝑗 = 𝑖 − 1;
0, dans les autres cas

où 𝑝 est un nombre fixé tel que 0 < 𝑝 < 1.

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ Chaînes de Markov : exemples 23
 I-3. EXEMPLES DE CHAÎNES DE MARKOV

Un tel processus est appelé promenade aléatoire sur ℤ.

Son graphe peut être décrit comme suit :

𝑝 𝑝
…… ……
…… ……
𝐢 − 𝟏 𝑞 𝐢 𝑞 𝐢 + 𝟏

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ Chaînes de Markov : exemples 24
 I-3. EXEMPLES DE CHAÎNES DE MARKOV
4. Le modèle de la ruine du joueur
Un joueur A joue contre un joueur B une suite de parties
de «pile» ou «face», indépendantes. La somme totale
de leurs fortunes est de 𝑎 dirhams. À chaque partie, on
convient que le joueur A gagne un dirham (que lui donne
le joueur B) avec une probabilité 𝑝 et perd un dirham
(qu'il rend donc à B) avec une probabilité 𝑞 (0 < 𝑝
< 1; 𝑞 = 1 — 𝑝). Le jeu s'arrête dès que l'un des
joueurs est ruiné.
Pour chaque 𝑛 > 0, on désigne par 𝑋𝑛 la fortune du
joueur A à l'issue de la 𝑛 −ième partie.

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ Chaînes de Markov : exemples 25
 I-3. EXEMPLES DE CHAÎNES DE MARKOV
La suite (𝑋𝑛 ) (𝑛 > 0) est une chaîne de Markov, dont
l'ensemble des états est 𝐸 ∶= {0,1, . . , 𝑎}. Sa matrice de
transition est donnée par
1 0 0 ⋯ 0 0 0
𝑞 0 𝑝 ⋯ 0 0 0
𝒫= ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ ⋮
0 0 0 ⋯ 𝑞 0 𝑝
0 0 0 ⋯ 0 0 1
États absorbants
Le graphe associé est :

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ Chaînes de Markov : exemples 26
 I-3. EXEMPLES DE CHAÎNES DE MARKOV

Remarque : Il existe un site de visualisation dynamique

des graphes de chaînes de Markov à espaces d’états finis.

Markov Chains
Explained Visually [Link]
By Victor Powell

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ Chaînes de Markov : exemples 27
 I-4. LA RELATION DE CHAPMAN-KOLMOGOROV

Cette propriété relie, pour une chaîne de Markov homogène,

les probabilités de transition en 𝑛 étapes aux probabilités en
une seule étape.
On pose pour 𝑛 ≥ 0 et 𝑖, 𝑗 ∈ 𝐸 2
(𝑛)
𝑝𝑖,𝑗 ≔ ℙ 𝑋𝑛 = 𝑗 𝑋0 = 𝑖). (3)
C’est la probabilité, partant de l'état 𝑖 en l'instant 0, d'être
dans l'état 𝑗 en l'instant 𝑛.
On pose aussi
𝑛
𝒫 (𝑛) = 𝑝𝑖,𝑗
𝑖,𝑗∈𝐸

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ Chapman-Kolmogorov 28
 I-4. LA RELATION DE CHAPMAN-KOLMOGOROV
Théorème 1 (Relation de Chapman-Kolmogorov).
Pour tout 𝑛 > 0, la matrice de transition en 𝑛
étapes est égale à la puissance 𝑛 −ième de la
matrice de transition en une étape :
𝒫 (𝑛) = (𝒫)𝑛 .
Sydney Chapman
Preuve : Exercice (voir TD). ∎ (1880-1970)

Corollaire 2. Pour tout 𝑛 > 0, la matrice 𝒫 (𝑛) est

stochastique.
Preuve : ………. ∎
Andrei Kolmogorov
(1903-1987)

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ Chapman-Kolmogorov 29
 I-4. LA RELATION DE CHAPMAN-KOLMOGOROV

Corollaire 3. Pour tout 𝑖, 𝑗 ∈ 𝐸 2 et tout couple

𝑚, 𝑛 d'entiers positifs, on a l’identité :

(𝑛+𝑚) (𝑛) (𝑚)

𝑝𝑖,𝑗 = 𝑝𝑖𝑘 𝑝𝑘𝑗 (4)
𝑘∈𝐸
Preuve : ……….. ∎

Remarque. Parfois c’est la formule (4) qui porte le nom de

RELATION DE CHAPMAN-KOLMOGOROV.

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ Chapman-Kolmogorov 30
 I-4. LA RELATION DE CHAPMAN-KOLMOGOROV

EXEMPLE
Calculer la matrice de transition en 𝑛 étapes pour la CM à deux
états (voir exemple 1).
1−𝛼 𝛼
𝒫= 0 < 𝛼, 𝛽 ≤ 1 .
𝛽 1−𝛽

Réponse :
𝑛 𝑛
𝑏 + 𝑎 1 − 𝛼 − 𝛽 𝑎(1 − 1 − 𝛼 − 𝛽 )
𝒫 (𝑛) 𝑛
=𝒫 = 𝑛 𝑛 ,
𝑏(1 − 1 − 𝛼 − 𝛽 ) 𝑎 + 𝑏 1 − 𝛼 − 𝛽
𝛽 𝛼
où 𝑏 =
𝛼+𝛽
, et 𝑎=
𝛼+𝛽
.
MA62 LST-MA Vu‫فحصي‬
Pham.‫ن‬ Chapman-Kolmogorov 31
 I-4. LA RELATION DE CHAPMAN-KOLMOGOROV

EXEMPLE
Calculer la matrice de transition en 𝑛 étapes pour la CM à 3
états dont la matrice de transition est

0 1 0
𝒫= 0 1/2 1/2
1/2 0 1/2

Calculer
(𝑛)
lim 𝑝𝑖,𝑗 pour 𝑖, 𝑗 = 1,2,3.
𝑛→∞
Interpréter.
MA62 LST-MA Vu‫فحصي‬
Pham.‫ن‬ Chapman-Kolmogorov 32
 I-4. LA RELATION DE CHAPMAN-KOLMOGOROV

EXEMPLE
Calculer la matrice de transition en 𝑛 étapes pour la marche
aléatoire sur les sommets du graphe complet 𝐾4 .
(les sommets d’un tetrahedron)
0 1 1 1
1 1 0 1 1
𝒫=
3 1 1 0 1
1 1 1 0

Calculer
(𝑛)
lim 𝑝𝑖,𝑗 pour 𝑖, 𝑗 = 1,2,3,4. Interpréter.
𝑛→∞
MA62 LST-MA Vu‫فحصي‬
Pham.‫ن‬ Chapman-Kolmogorov 33
 I-4. LA RELATION DE CHAPMAN-KOLMOGOROV

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ Chapman-Kolmogorov 34
 I-4. LA RELATION DE CHAPMAN-KOLMOGOROV

EXERCICE

Soit 𝑋𝑛 𝑛 > 0 une chaîne de Markov à valeurs dans 𝐸

de matrice de transition 𝒫 . Montrer que 𝑌𝑛 = 𝑋3𝑛 est
une chaîne de Markov de matrice de transition 𝒫 3 .

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ Chapman-Kolmogorov 35
 I-4. LA RELATION DE CHAPMAN-KOLMOGOROV

Lemme 4. On note 𝜈0 la loi de 𝑋0 :

𝜈0 𝑖0 = ℙ 𝑋0 = 𝑖0 .
On a alors pour tous (𝑖0 , . . . , 𝑖𝑛 ) dans 𝐸
𝑛−1

ℙ(𝑋𝑛 = 𝑖𝑛 , . . . , 𝑋0 = 𝑖0 ) = 𝜈0 𝑖0 𝑝𝑖𝑘, 𝑖𝑘+1

𝑘=0
Preuve : ……….. ∎

Définition 2: La loi 𝜈0 de la v.a 𝑋0 s’applelle la loi initiale de la

chaîne de Markov 𝑋𝑛 𝑛 .

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ Chapman-Kolmogorov 36
 I-4. LA RELATION DE CHAPMAN-KOLMOGOROV

La proposition suivante est un raccourcis de calcul souvent

utile

Proposition 5. Soient 𝑛 ≥ 0 et 𝑟 ≥ 1 deux entiers , Alors

ℙ 𝑋𝑛+𝑟 = 𝑗𝑛+𝑟 , . . . 𝑋𝑛+1 = 𝑗𝑛+1 𝑋𝑛 = 𝑖𝑛 , … 𝑋0 = 𝑖0
= 𝑝𝑖𝑛 ,𝑗𝑛+1 𝑝𝑗𝑛+1,𝑗𝑛+2 ⋯ 𝑝𝑗𝑛+𝑟−1,𝑗𝑛+𝑟 . (5)

Preuve : C’est immédiat à partir du lemme 4 ∎

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ Chapman-Kolmogorov 37
 I-4. LA RELATION DE CHAPMAN-KOLMOGOROV

Proposition 5. Pour une CM homogène 𝑋𝑛 𝑛 , la loi 𝜈𝑛 de la

v.a 𝑋𝑛 est entièrement caractérisée par la loi initiale 𝜈0 et la
matrice de transition 𝒫 :
𝜈𝑛 = 𝜈0 𝒫 𝑛
Preuve : ……... ∎

EXEMPLE
CM à 2 états
1−𝛼 𝛼
𝒫= 0 < 𝛼, 𝛽 ≤ 1
𝛽 1−𝛽

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ Chapman-Kolmogorov 38
I-5. CLASSIFICATION DES ETATS; DECOMPOSITION EN CLASSES

Nous allons définir une classification des états et en déduire

des propriétés des chaînes de Markov.
Les états d’une chaîne de Markov se répartissent en classes
que l’on définit à partir de la matrice de transition.

Définition 3 . On dit que l’état 𝑗 est accessible à partir de l’état

(𝑛)
𝑖, s’il existe un entier 𝑛 ≥ 0 tel que 𝑝𝑖,𝑗 > 0. On note 𝑖 ↝ 𝑗.
Sur le graphe, si 𝑖 ≠ 𝑗, 𝑖 ↝ 𝑗 s’il existe un chemin
(orienté) du sommet 𝑖 vers le sommet 𝑗.

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ Classification 39
I-5. CLASSIFICATION DES ETATS; DECOMPOSITION EN CLASSES

Propriété 3. La relation d'accessibilité entre états est réflexive

et transitive.
Preuve : Il faut montrer que
1. La relation ↝ est réflexive : ∀𝑖 ∈ 𝐸, 𝑖 ↝ 𝑖 ;
2. La relation ↝ est transitive :
∀ 𝑖, 𝑗, 𝑘 ∈ 𝐸 3 , 𝑖 ↝ 𝑗 et 𝑗 ↝ 𝑘 ⟹ 𝑖 ↝ 𝑘 ∎

Définition 4. On dit que deux états 𝑖 et 𝑗 communiquent et l'on

écrit 𝑖 ↭ 𝑗, si on a à la fois : 𝑖 ↝ 𝑗 et 𝑗 ↝ 𝑖.
Propriété 4. La relation de communication entre états est une
relation d'équivalence.
Preuve : ……….. ∎
MA62 LST-MA Vu‫فحصي‬
Pham.‫ن‬ Classification 40
I-5. CLASSIFICATION DES ETATS; DECOMPOSITION EN CLASSES
(0) (0)
Remarque. Pour tout 𝑖 ∈ 𝐸, on a 𝑝𝑖,𝑖 = 1 (car 𝑝𝑖,𝑗 = 𝛿𝑖𝑗 ).
Donc, tout état communique avec lui-même. Un état est
(𝑛)
appelé état de retour, s'il existe 𝑛 > 1 tel que 𝑝𝑖,𝑖 > 0. Un
(𝑛)
état 𝑖 tel que pour tout 𝑛 > 1 on ait 𝑝𝑖,𝑖 = 0 est appelé état
de non-retour.
Par exemple, l’état 1 dans la CM à deux états telle que
1 0
𝒫= ,
1 0
est un état de non-retour.

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ Classification 41
I-5. CLASSIFICATION DES ETATS; DECOMPOSITION EN CLASSES

La relation de communication, définit des classes disjointes

et non vides 𝐶𝑘 ⊆ 𝐸 𝑘 d’éléments qui communiquent
entre eux dites classes indécomposables (ou classes de
communication) et qui forment une partition de 𝐸. Si 𝐶1 et
𝐶2 sont deux classes distinctes, on peut éventuellement
aller, de 𝐶1 à 𝐶2 , mais on ne peut alors retourner de 𝐶2 à
𝐶1 . En revanche, tous les états d'une même classe
communiquent.

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ Classification 42
I-5. CLASSIFICATION DES ETATS; DECOMPOSITION EN CLASSES

État absorbant
EXEMPLE

On a 1 ↝ 2 ↝ 3 ↝ 1 , 4 ↝ 5 ↝ 6 ↝ 4 et 7 ↝ 7. Il y a
donc 3 classes indécomposables : {1,2,3} , {4,5,6} et 7 .
(0) (𝑛)
Un état 𝑖 est dit absorbant si 𝑝𝑖,𝑖 = 1 et 𝑝𝑖,𝑖 = 1, ∀𝑛

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ Classification 43
I-5. CLASSIFICATION DES ETATS; DECOMPOSITION EN CLASSES

Définition 5. On dit que la CM est irréductible s'il n'y a qu'une

seule classe pour la relation de communication, autrement dit,
si tous les états communiquent entre eux.

Exemples.
1. CM : 𝐸 = {0,1,2} et

1/2 1/2 0
𝒫 = 1/2 1/4 1/4
0 1/3 2/3

Cette chaîne est irréductible : tous les états communiquent

0↭1↭2
MA62 LST-MA Vu‫فحصي‬
Pham.‫ن‬ Classification 44
I-5. CLASSIFICATION DES ETATS; DECOMPOSITION EN CLASSES

2. CM : 𝐸 = {0,1,2,3} et

Il y a 3 classes {0,1}, {2} et {3}. L'état 3 est absorbant,

l'état 2 n'est plus visité après un certain temps. Dans
la terminologie qui est développée plus loin, les classes
{0,1} et {3} sont récurrentes, la classe {2} est transiente.

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ Classification 45
I-5. CLASSIFICATION DES ETATS; DECOMPOSITION EN CLASSES

3. CM : 𝐸 = {1,2,3,4,5,6} et
1/2 1/2

1/3 1/3

𝒫= 1/2 1/2

1
1 1/3

Trouver les classes de communication de cette chaîne de

Markov.

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ Classification 46
I-5. CLASSIFICATION DES ETATS; DECOMPOSITION EN CLASSES

4. CM : 𝐸 = {0,1,2,3,4} et

𝒫=

Trouver les classes de communication de cette chaîne de

Markov.

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ Classification 47
 Notation .
la probabilité qu’un événement 𝐴 se réalise, partant de
l'état 𝑖 sera notée :

ℙ 𝐴 𝑋0 = 𝑖) ∶= ℙ𝑖 (𝐴)

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ Classification 48
 I-6. ÉTATS RECURRENTS ET TRANSIENTS
Définition 7 : Pour tout état 𝑗, le temps d'atteinte 𝜏𝑗 de la
chaîne (𝑋𝑛 ) (𝑛 > 0) dans l'état 𝑗 à partir de l'instant 1 est
le temps nécessaire pour que le système visite l’état 𝑗 pour
la première fois. C’est le temps de premier retour en 𝑗.
Autrement dit,
𝜏𝑗 ≔ inf 𝑛 ≥ 1 ∶ 𝑋𝑛 = 𝑗 . (6)
𝜏𝑗 est une v.a qui prend ses valeurs dans l’espace des temps .

Remarque : l’événement (𝜏𝑗 = 𝑛) s’écrit

𝜏𝑗 = 𝑛 = 𝑋1 ≠ 𝑗, … , 𝑋𝑛−1 ≠ 𝑗, 𝑋𝑛 = 𝑗 .
Il ne dépend que de 𝑋1 , … , 𝑋𝑛 .
MA62 LST-MA Vu‫فحصي‬
Pham.‫ن‬ États récurrents et états transients 49
 I-6. ÉTATS RECURRENTS ET TRANSIENTS
Définition 7 : Pour tout couple (𝑖, 𝑗) d'états et tout 𝑛 > 1, la
probabilité pour que le processus, partant de l'état 𝑖, atteigne
l'état 𝑗, pour la première fois, à l'instant 𝑛 est
(𝑛)
𝑓𝑖,𝑗 ≔ ℙ𝑖 𝜏𝑗 = 𝑛 . (7)
(0)
par convention, on pose 𝑓𝑖,𝑗 ≔ 0, ∀ 𝑖, 𝑗 ∈ 𝐸 2 .
La probabilité pour que le processus, partant de 𝑖, passe par 𝑗
au moins une fois au cours du temps est
(𝑛)
𝑓𝑖,𝑗 : = ℙ𝑖 (𝜏𝑗 < +∞) = 𝑓𝑖,𝑗 . (8)
𝑛≥1

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ États récurrents et états transients 50
 I-6. ÉTATS RECURRENTS ET TRANSIENTS
Définition 8 : On dit que l'état 𝑗 est récurrent, si 𝑓𝑗,𝑗 = 1.
On dit qu'il est transient ou transitoire, si 𝑓𝑗,𝑗 < 1. La
chaîne de Markov est appelée récurrente, respectivement
transiente, si tous ses états sont récurrents, respectivement
transients.

Le fait qu’un état soit récurrent signifie que la chaîne

revient vers cet état presque sûrement, et donc qu’elle y
revient infiniment souvent. Le fait qu’un état soit transient
signifie que la chaîne a une probabilité positive de ne
jamais retourner dans cet état.

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ États récurrents et états transients 51
 I-6. ÉTATS RECURRENTS ET TRANSIENTS

Exercice . Pour tout entier 𝑛 > 1, montrer l’identité

𝑛
(𝑛) (𝑘) (𝑛−𝑘)
𝑝𝑖,𝑗 = 𝑓𝑖,𝑗 𝑝𝑗,𝑗 (9)
𝑘=0

Voir TD.

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ États récurrents et états transients 52
 I-6. ÉTATS RECURRENTS ET TRANSIENTS
Théorème 4 (Critères de récurrence). Un état 𝑗 est récurrent
ou transient selon que
+∞
(𝑛)
𝑝𝑗𝑗 = +∞ (la série diverge) (10)
𝑛=0
ou que
+∞
(𝑛)
𝑝𝑗𝑗 < +∞ (La série converge) (11)
𝑛=0
Ces formules ont une interprétation intuitive : notons
𝑁𝑗 = 𝑛≥0 𝕀 𝑋𝑛 =𝑗 le nombre de retours dans l'état 𝑗 après
(𝑛)
l'instant 0. Alors le nombre moyen 𝔼 𝑁𝑗 = 𝑛≥0 𝑝𝑗𝑗 est infini
si et seulement si 𝑗 est récurrent.
MA62 LST-MA Vu‫فحصي‬
Pham.‫ن‬ États récurrents et états transients 53
 I-6. ÉTATS RECURRENTS ET TRANSIENTS
Exemple. Revenons à l’exemple

Pour tout 𝑛 > 0, on trouve :

(𝑛) (𝑛) (𝑛) (𝑛)
𝑝0,0 = 𝑝1,1 = 1/2, 𝑝2,2 = (1/4)𝑛 et 𝑝3,3 = 1.
(𝑛) (𝑛) (𝑛)
Les séries 𝑝0,0 , 𝑝1,1 , 𝑝3,3 divergent. Les états 0, 1, 3
(𝑛)
sont récurrents. La série 𝑝2,2 converge, l'état 2 est transient.

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ États récurrents et états transients 54
 I-6. ÉTATS RECURRENTS ET TRANSIENTS
Exemple. CM : 𝐸 = {0,1,2,3,4} et

𝒫=

Trouver les états récurrents et les états transients.

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ États récurrents et états transients 55
 I-6. ÉTATS RECURRENTS ET TRANSIENTS
Exemple. CM : 𝐸 = {0,1,2,3,4} et
𝒫=

Pour 𝑛 > 1 ∶

1 1
0 0 0
2 2
1 1 1
− 3𝑛−2 41−𝑛 21−2𝑛 3𝑛−1 3 − 3𝑛 41−𝑛 21−2𝑛 3𝑛−1 − 21−2𝑛 3𝑛−2
4 6 4
𝒫𝑛 = 0 0 1 0 0
1 1 1
− 21−2𝑛 3𝑛−2 3𝑛−1 4−𝑛 − 3𝑛−1 4−𝑛 3𝑛−1 4−𝑛 − 3𝑛−2 4−𝑛
4 2 4
1 1
0 0 0
2 2

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ États récurrents et états transients 56
 I-6. ÉTATS RECURRENTS ET TRANSIENTS

Exemple. CM : 𝐸 = {0,1,2,3,4} et 𝒫=

Les états 0, 2 et 4 sont récurrents, et les états 1 et 3 sont

transients.
1/2 1/2

0 1

1/2 1/2 1/2 1/4 1

2

1/4 1/4
4 3
1/2 1/4
Classe récurrente Classe absorbante
Classe transiente
MA62 LST-MA Vu‫فحصي‬
Pham.‫ن‬ États récurrents et états transients 57
 I-6. ÉTATS RECURRENTS ET TRANSIENTS

Proposition 5. Tout état de non-retour est transient; tout

état absorbant est récurrent.
Preuve :
(𝑛)
Rappel : Un état 𝑖 est de non-retour si 𝑝𝑖,𝑖 = 1 si 𝑛 = 0 et
0 autrement;
(𝑛)
Un état 𝑖 est absorbant si ∀𝑛 ≥ 0, 𝑝𝑖,𝑖 = 1. ∎

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ États récurrents et états transients 58
 I-6. ÉTATS RECURRENTS ET TRANSIENTS
Proposition 6. Soit 𝐶 une classe de communication. Alors,
les états dans 𝐶 sont soit tous récurrents soit tous transients.
La récurrence est donc une propriété de classe.
Preuve : Soient 𝑖 et 𝑗 deux états de 𝐶. On suppose que l’état
(𝑛) (𝑚)
𝑖 est transient. ∃ 𝑛, 𝑚 t.q 𝑝𝑖,𝑗 > 0 et 𝑝𝑗,𝑖 > 0, et , pour
tout 𝑟 ≥ 0,
(𝑛+𝑚+𝑟) 𝑛 𝑟 𝑚
𝑝𝑖,𝑖 ≥ 𝑝𝑖,𝑗 𝑝𝑗,𝑗 𝑝𝑗,𝑖 . car 𝑖 est
transient
Donc
(𝑟) 1 (𝑛+𝑚+𝑟)
𝑝𝑗,𝑗 ≤ (𝑛) (𝑚)
𝑝𝑖,𝑖 < ∞.
𝑟≥0 𝑝𝑖,𝑗 𝑝𝑗,𝑖 𝑟≥0

L’état 𝑗 est alors transient. ∎

MA62 LST-MA Vu‫فحصي‬
Pham.‫ن‬ États récurrents et états transients 59
 I-6. ÉTATS RECURRENTS ET TRANSIENTS

On peut donc parler de classe récurrente et de classe

transiente. En fait, on a une propriété plus forte que celle
décrite dans la proposition précédente : il suffit que 𝑗 soit
seulement accessible d'un état 𝑖 récurrent pour que 𝑗 lui-
même soit récurrent. En particulier, une chaîne de
Markov ne peut aller d'un état récurrent vers un état
transient.

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ États récurrents et états transients 60
 I-6. ÉTATS RECURRENTS ET TRANSIENTS

Exemple. CM : 𝐸 = {0,1,2,3,4} et 𝒫=

1/2 1/2

0 1

1/2 1/2 1/2 1/4 1

2

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

Classe Classe Classe

récurrente transiente absorbante

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ États récurrents et états transients 61
 I-6. ÉTATS RECURRENTS ET TRANSIENTS
Proposition 7. Si une chaîne de Markov a un nombre fini
d'états, elle a au moins un état récurrent.
Preuve : …... ∎

Cette proposition n'est pas vraie si la chaîne a une infinité

d'états. On peut avoir une chaîne, où tous les états sont
transients. C'est le cas, par exemple, de la chaîne ayant
𝐸 = ℤ et 𝒫 = 𝑝𝑖𝑗 , où
𝑝𝑖,𝑖+1 = 1 et 𝑝𝑖,𝑗 = 0 si 𝑗 − 𝑖 ≠ 1,
pour matrice de transition.

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ États récurrents et états transients 62
 I-6. ÉTATS RECURRENTS ET TRANSIENTS

On montre le résultat prévisible suivant :

Proposition 8. Soit 𝑅 l’ensemble des états récurrents

d'une chaîne de Markov finie. Alors, avec une probabilité
égale à 1, la chaîne se trouve dans 𝑅 au bout d'un temps
fini.

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ États récurrents et états transients 63
 I-7. PÉRIODICITÉ

Question : Dans quelles conditions le temps qui sépare

deux retours au même état 𝑗 est ou n'est pas multiple d'un
temps minimum ?
Pour répondre à cette question, on introduit la notion de
période.

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ Périodicité 64
 I-7. PÉRIODICITÉ

Définition 9 : Soit 𝑗 un état de retour ; on appelle période

de 𝑗, le p.g.c.d. de tous les entiers 𝑛 ≥ 1 pour lesquels
(𝑛)
𝑝𝑗,𝑗 > 0 . On note 𝑑(𝑗) la période de 𝑗 :
𝑛
𝑑 𝑗 = p. g. c. d. 𝑛 ≥ 1, 𝑝𝑗,𝑗 > 0 .

Si 𝑑(𝑗) > 2, on dit que 𝑗 est périodique de période 𝑑(𝑗); si

𝑑(𝑗) = 1, on dit que 𝑗 est apériodique. Si 𝑗 est un état de
non-retour, on pose 𝑑(𝑗) = +∞.

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ Périodicité 65
 I-7. PÉRIODICITÉ

La propriété de périodicité est une autre propriété de

classe :

Théorème 9. Si 𝑖 est périodique de période 𝑑 𝑖 = 𝑑 finie

et si 𝑖 ↭ 𝑗, alors 𝑗 est aussi périodique de période 𝑑.
Preuve : …... ∎

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ Périodicité 66
 I-7. PÉRIODICITÉ
Exemple. CM : 𝐸 = {0,1,2} et
1
0 1 0 0
𝑝
1
𝒫= 𝑝 0 𝑞 , 𝑝+𝑞 =1 1 𝑞
𝑝>0
1 0 0
2

L’état 0 est de retour ; les lacets (chemins fermés)

0 → 1 → 0 et 0 → 1 → 2 → 0
ont pour longueurs 2 et 3, respectivement, leur p.g.c.d
est 𝑑 = 1. Donc, l’état 0 est apériodique.
La chaîne est irréductible ⟹ les états 1 et 2 sont
apériodiques.
MA62 LST-MA Vu‫فحصي‬
Pham.‫ن‬ Périodicité 67
 I-7. PÉRIODICITÉ
Exemple. La promenade aléatoire sur ℤ (exemple 3, I-3)

𝑝 𝑝
…… ……
…… ……
𝐢 − 𝟏 𝑞 𝐢 𝑞 𝐢 + 𝟏

Ici, tous les lacets partant d’un état donné ont des
longueurs paires. Tous les états sont périodiques de
période 2.

Exercice . Calculer les périodes des états dans le modèle

de la ruine du joueur (exemple 4, I-3).

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ Périodicité 68
 I-7. PÉRIODICITÉ
Exemple. CM : 𝐸 = {0,1,2,3} et
1
0 0 1/2 1/2 0 1

1 0 0 0
1/2
𝒫= 1/2
1
0 1 0 0 1

0 1 0 0 3 2

Cette chaîne est irréductible. Il y a donc une seule

classe (récurrente). Partant de l’état 0, il existe 2
lacets de longueur 3 :
0 → 2 → 1 → 0 et 0 → 3 → 1 → 0.
Tous les états sont donc périodiques de période 3.

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ Périodicité 69
 I-7. PÉRIODICITÉ
Exemple. CM : 𝐸 = {0,1,2,3} et
1
0 0 1/2 1/2 0 1

1 0 0 0
1/2
𝒫= 1/2
1
0 1 0 0 1

0 1 0 0 3 2

(𝑛) (𝑛) 1 2𝑛𝜋

𝑝0,0 = 𝑝1,1 = 1 + 2 cos = {1,0,0,1,0,0,1,0,0,1,0, … }
3 3
(𝑛) (𝑛) 1 2𝑛𝜋 1 1 1 1
𝑝2,2 = 𝑝3,3 = 1 + 2 cos = ,0,0, ,0,0, ,0,0, ,0, … .
6 3 2 2 2 2

Ce sont des suites de période 3.

MA62 LST-MA Vu‫فحصي‬

Pham.‫ن‬ Périodicité 70
FIN DU CHAPITRE 1

71