Polycopié

RO pour le GI
Modèles stochastiques pour la prise de décision

Mohammed Hadda

4ème année GI-IADS (2022-2023)

ENSAM de Meknès
Université Moulay Ismail
 Table des matières

1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2 Notions générales de probabilités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.1 Espace probabilisé
7
2.1.1 Espace mesurable . . . . . . . . . . . . . . . . . . . . ............................ 7
2.1.2 Mesurabilité
................................... ............................ 8
2.1.3 Probabilités conditionnelles :
................................... . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.4 Mesure image ; Lois
................................... . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.5 Variables aléatoires discrètes
................................... . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1.6 Lois discrètes usuelles :
................................... . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1.7 Variables aléatoires réelles et Lois à densité
................................... . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2 Théorèmes de convergence 16
2.2.1 Lois des grands nombres :
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.2 Théorème central limite :
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3 Simulation de Variables aléatoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.1 Simulation de Variables aléatoires discrètes 19
3.2 Simulation de Variables aléatoires à densité 19
3.2.1 Simulation d’une v.a. admettant une densité continue par inversion de la fonction
de répartition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2.2 Simulation d’une v.a. bornée à densité bornée par la méthode de rejet . . . . 20
3.2.3 Simulation d’une loi normale : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.3 Méthode de Monte Carlo pour le calcul des intégrales et des moments :
20
3.3.1 Méthode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.3.2 Précision (estimation d’erreur) : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.3.3 Inérêts de la méthode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.3.4 Calcul approché des moments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.4 Méthode de "simulation Monte Carlo" 22

4 Modèles stochastiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.1 Processus stochastiques 23
4.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.1.2 Processus stochastiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.2 Processus de Wiener ou mouvement brownien 24
4.3 Processus gaussien 25
4.4 Processus de Poisson 25
4.5 Chaines de Markov 25
4.5.1 définitions et propriétés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.5.2 Probabilités et matrice de transition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.5.3 Propriétés des chaines de Markov homogènes . . . . . . . . . . . . . . . . . . . . . . . . 27
4.5.4 Classification des états d’une une chaine de Markov . . . . . . . . . . . . . . . . . . . 31
4.5.5 Lois ou probabilités stationnaires ; Temps moyen de premier retour . . . . . . . . . 36
4.6 Application : 39

5 Processus de décision markoviens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

5.1 Processus de décision markoviens 43
5.2 Problèmes décisionnels de Markov 53
5.3 Politiques d’actions 53
5.4 Politique markovienne et chaine de Markov valuée 55
5.5 Critères de performance 56
5.6 Fonctions de valeur 57
5.6.1 1- cas du crière fini . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.6.2 2- cas du crière moyen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.7 Politiques markoviennes 58
5.7.1 Equivalence des politiques histoire-dépendantes et markoviennes . . . . . . . . . 58
5.8 Caractérisation des politiques optimales 58
5.8.1 Cas du critère fini . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.8.2 Cas du critère moyen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.9 Algorithmes de résolution des MDP 61
5.10 Etude de cas et Application Industrielle ; cas d’un MDP 63
5.10.1 Exemple de système de production . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
 1. Introduction

Dans le cas d’un problème d’optimisation déterministe, les valeurs de tous les paramètres sont
supposées connues.
Alors que dans un problème d’optimisation stochastique un certain nombre de paramètres peuvent
être considérés comme inconnues et sont modélisés par des variables aléatoires.
Plus généralement, l’incertitude est représentée par des expériences aléatoires dont l’issue est notée
ω. L’ensemble de toutes les issues possibles est l’espace fondamental Ω.
Par exemple, si les éléments de Ω sont les conditions climatiques, ils permettent de décrire des
variables aléatoires telles que la consommation éléctrique.

Ainsi, L’optimisation stochastique est un cadre qui permet de formuler un problème d’optimisation
dans lequel les données sont incertaines (par exp. les prix des énergies). C’est aussi un ensemble de
méthodes et de techniques de résolution.
Dans un problème d’optimisation stochastique, on cherche souvent à prendre une décision avant
que les valeurs des réalisations des variables aléatoires ne soient observées.
 2. Notions générales de probabilités

Dans ce chapitre introductif nous présentons les notions basiques de théorie des probabilités qui
seront utilisées dans la suite de ce cours.

2.1 Espace probabilisé

2.1.1 Espace mesurable

On considère un ensemble quelconque Ω, qui modélise le caractère aléatoire d’un certain phéno-
mène et portera dans la suite le nom d’ensemble fondamental, ou d’espace d’issues (des chances,
d’échantillons). On note P(Ω) l’ensemble des parties de Ω.
Rappelons que si Card P(Ω) = n ; alors Card P(Ω) = 2n : Par exp si Ω = {1, 2, 3} alors P(Ω) =
{0,
/ {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, Ω}.
Quand Ω est fini ou dénombrable, l’ensemble P(Ω) décrit les événements aléatoires associés à
l’expérience considérée.
Quand Ω est inflni non-dénombrable, l’ensemble P(Ω) est parfois trop gros pour pouvoir étudier
mathématiquement la probabilité de ces événements. On a alors recours à la notion de tribu :

Définition 2.1.1 Une tribu ou σ -algèbre F sur Ω est un sous-ensemble de P(Ω) contenant
Ω et vériflant les propriétés suivantes :
• Si A ∈ F alors Ac ∈ F (stabilité par passage au complémentaire).
• Si (An )n est une suite de F alors ∪n An ∈ F (stabilité par réunion dénombrable).

Remarque : F est stable par réunion finie et par intersection finie.

Il faut comprendre une tribu comme la quantité d’information assocée à une certaine expérience
aléatoire. Remarquons qu’une tribu contient forcément 0.
/

Exemples de tribus sur Ω : {0, / Ω} tribu triviale (la plus petite) et P(Ω) tribu complète (la
/ A, Ac , Ω}.
plus grande) ; ou {0,
Si F est une tribu sur Ω, on dit que (Ω, F ) est un espace mesurable, ou aussi probabilisable
 8 Chapitre 2. Notions générales de probabilités

lorsqu’on va le munir d’une mesure de probabilté, et les éléments de F sont des parties F mesu-
rables (événements).
Une sous-tribu S de F est une tribu incluse dans F au sens où A ∈ S =⇒ A ∈ F .

Remarque : Toute inersection de tribus sur Ω est une tribu sur Ω. Mais une réunion de tribus n’est
pas forcément une tribu ; en effet si A1 , A2 ⊂ Ω, alors F1 = {0,
/ A1 , Ac1 , Ω} et F1 = {0,
/ A2 , Ac2 , Ω}
sont des tribus, mais pas F1 ∪ F2 en général, par exp si A1 ∩ A2 ∈/ F1 ∪ F2 .

Définition 2.1.2 Soit A une partie quelconque de P(Ω). On appelle tribu engendrée par A ,
et on note σ (A ) l’intersection de toutes les tribus contenant A .

Définition 2.1.3 On appelle tribu des boréliens de R, on note B(R), la tribu engendrée par
les intervalles ouverts ]a, b[, a < b ∈ R.

Exemples d’espace mesurable :

1. (Ω, P(Ω)) si Ω est fini.
2. (R, B(R).

Remarque :
1. Dans cette définition, on peut remplacer "ouvert" par "fermé" ou par "ouvert à droite" ou ...
2. B(R) ( P(R).

2.1.2 Mesurabilité

Définition 2.1.4 Soit (Ω, F ) et (E, E ) deux espaces mesurables. Une application X : Ω → E
est dite F − E mesurable si X −1 (A) ∈ F pour tout A ∈ E où X −1 (A) = {ω ∈ Ω : X(ω) ∈ A} ;
autrement dit si X −1 (E ) ⊂ F .

Remarque : La mesurabilité d’une application est conservée chaque fois que l’on diminue (au sens
de l’inclusion) la tribu de l’espace d’arrivée ou que l’on agrandit celle de l’espace de départ.

Une fonction X : R → R est dite borélienne si elle est B(R) − B(R) mesurable, c-à-d si X −1 (A) ∈
B(R) pour tout A ∈ B(R). En fait, il suffit que cette propriété soit vérifiée pour les intervalles
ouverts A.

En particulier, les focntions continues sont boréliennes car l’image réciproque d’un intervalle
ouvert par une fonction continue est une réunion d’intervalles ouverts, donc un borélien.

Définition 2.1.5 Soit (Ω, F ) un espace mesurable. Une variable aléatoire réelle (v.a.r.) X est
une application mesurable de (Ω, F ) dans (R, B(R).
Si X(Ω) est au plus dénombrable et X est F − P(R) mesurable, X est dite variable aléatoire
discrète réelle.

Définition 2.1.6 Soit (Ω, F ) un espace mesurable. Un vecteur aléatoire X est une application
mesurable de (Ω, F ) dans (Rd , B(Rd ) (d > 1).
Si X(Ω) est au plus dénombrable et X est F − P(Rd ) mesurable, X est dit vecteur aléatoire
discret.

Exemple : Un exemple simple, mais important, d’application mesurable de Ω dans R (et de v.a.
2.1 Espace probabilisé
9
discrète) est La fonction indicatrice d’un ensemble A ∈ F :

1 si ω ∈ A
1A : (ω) →
0 sinon

En effet pour tout B ⊂ R, on a



 0/ si 0 ∈ / B et 1 ∈
/B
A si 0 ∈
/ B et 1 ∈ B

(1A )−1 (B) = c

 A si 0 ∈ B et 1 ∈ /B
Ω si 0 ∈ B et 1 ∈ B


Remarquons bien que (1A )−1 (P(R)) = σ ({A}). Ceci montre que 1A est σ ({A}) − P(R) mesu-
rable.
De même, on vérifie aisément qu’une fonction constante de Ω → R est mesurable pour toute tribu
sur Ω et toute tribu sur R.
Remarquons également que les v.a.r. sont stables par composition avec les fonctions boréliennes :
si X est une v.a.r. S mesurable et f une fonction borélienne, alors f (X) est une v.a.r S mesurable.
Les v.a.r. peuvent être approchées en limite croissante simple par des v.a.r. "en escalier" qui sont du
n
type ∑ ai 1A , avec ai ∈ R, Ai ∈ S .
i
i=1

Définition 2.1.7 La tribu engendée par une variable aléatoire X déflnie sur (Ω, F ) est l’en-
semble σ (X) = {X −1 (A), A ∈ B(R}.
σ (X) est la plus petite tribu sur Ω rendant X mesurable. En plus, σ (X) est une tribu contenue
dans F .

Définition 2.1.8 Soit (Ω, F ) un espace mesurable. Une mesure de probabilité ou simplement
une probabilité sur (Ω, F ) est une application P de F dans [0, 1] vérifiant
• P(Ω) = 1
• Si (An )n∈N est une suite d’éléments de F deux à deux disjoints, alors
∞
[  ∞
P An = ∑ P(An ) (propriété de σ − additivité).
n=0 n=0

On utilise souvent l’écriture avec les fonctions indicatrices :

Z Z
P(A) = dP = 1A dP.
A Ω

Le triplet (Ω, F , P) est appelé espace de probabilité ou espace probabilisé.

Proposition 2.1.1 On a
(i) P(A) + P(Ac ) = 1 ∀A ∈ F
(ii) A ⊂ B =⇒ P(A) ≤ P(B)
(iii) P(A ∪ B) + P(A ∩ B) = P(A) + P(B) ∀A, B ∈ F .

Exemple : (Lancé de dés) On considère l’expérience aléatoire du lancer de deux dés.

L’espace d’échantillonnage est Ω = {(1, 1), (1, 2), · · · , (6, 6)}. Soit X la variable aléatoire définie
par la somme des résultats des deux dés. Dans ce cas on a
P(X = 1) = P(0)
/ = 0;
2 1
P(X = 3) = P({ω ∈ Ω/X(ω) = 3} = P({(1, 2), (2, 1)}) = 36 = 18 ;
 10 Chapitre 2. Notions générales de probabilités
1
P(X ≤ 2) = P(X = 2) = P({ω ∈ Ω/X(ω) = 2} = P({(1, 1)}) = 36 ;
6 1
P(X ≤ 4) = P({(1, 1)(1, 2), (1, 3), (2, 1), (2, 2), (3, 1)}) = 36 = 6 .

Remarque : Il existe une unique mesure de probabilité λ sur ([0, 1], B([0, 1]) telle que λ (]a, b[) =
b − a, pour tous a, b ∈ [0, 1], a < b ; appelée mesure de Lebesgue sur [0, 1].
Définition 2.1.9 Soit (Ω, F , P) un espace de probabilité. Un ensemble A ∈ F est dit négli-
geable pour P si P(A) = 0.

Par exemple les singletons, les ensembles dénombrables de [0, 1] sont négilgeables pour la mesure
de Lebesgue.

2.1.3 Probabilités conditionnelles :

Si A et B sont deux événements tels que P(B) > 0, la probabilité conditionnelle de A sachant B,
notée P(A|B) est définie par

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

• B ⊂ A =⇒ P(A|B) = 1
• A et B indépendants =⇒ P(A|B) = P(A).

Rappel : Un système d’événements (Bi )i∈I est dit exhaustif ou complet si Ω = ∪i∈I Bi , union
au plus dénombrable (I ⊂ N) et disjointe (Bi ∩ B j = 0,
/ ∀ i 6= j).

Formule des probabilités totales

Si (Bi )i∈I est un système exhaustif (fini ou dénombrable) d’événements, et si ∀i ∈ I, P(Bi ) 6= 0,
alors pour tout événement A on a

P(A) = ∑ P(A|Bi )P(Bi ) = ∑ P(A ∩ Bi ).

i∈I i∈I

Formule de Bayes
Avec les notations précédentes, si P(A) > 0 on a

P(A|B j )P(B j )
P(B j |A) = .
∑i∈I P(A|Bi )P(Bi )

2.1.4 Mesure image ; Lois

Les applications mesurables permettent de « transporter » la mesure d’un espace à un autre. Dans
le cas d’une variable (ou d’un vecteur) aléatoire, la " mesure image " ainsi obtenue s’appelle la loi
de la variable (ou du vecteur) aléatoire.
Définition 2.1.10 Soit une v.a.r. définie sur (Ω, F , P). La loi de X (sous P) est la probabilité
PX sur(R, B(R) définie comme mesure-image de P par X : pour tout A ∈ B(R),

PX (A) = P(X −1 (A)) = P{ω ∈ Ω/X(ω) ∈ A}.

Pour simplifier, on note PX (A) = P(X ∈ A).

 2.1 Espace probabilisé
11

2.1.5 Variables aléatoires discrètes

La loi d’une v.a discrète X est la donnée de toutes les valeurs P(X = xk ) = pk (pk ∈ [0, 1]) lorsque
xk prend toutes les valeurs possibles dans X(Ω).
Dans ce cas ∀B ∈ B(R), P(X ∈ B) = ∑ P(X = xk ) = ∑ pk .
xk ∈B xk ∈B

Définition 2.1.11 Soit (Ω1 , F1 , P1 ) et (Ω2 , F2 , P2 ) deux espaces de probabilité. Soit X (resp.
Y ) une variable aléatoire discrète définie sur Ω1 (resp. sur Ω2 ). On dit que X et Y ont même loi
si X(Ω1 ) = Y (Ω2 ) et si pour tout x ∈ X(Ω1 ) on a P1 (X = x) = P2 (Y = x). On note X ∼ Y .

Définition 2.1.12 • Soient X et Y deux v.a. discrètes. La loi conjointe du couple (X,Y ) est la
donnée de toutes les valeurs de P(X = x,Y = y) pour (x, y) ∈ X(Ω) ×Y (Ω). Les lois de X et de
Y sont les lois marginales de X et de Y .
• Soit x ∈ X(Ω) tel que P(X = x) > 0. On appelle loi conditionnelle de Y sachant (X = x) la
probabilité Px définie sur Y (Ω) par

P(X = x,Y = y)
∀y ∈ Y (Ω), Px ({y}) = P(Y = y|X = x) = .
P(X = x)

Proposition 2.1.2 — v.a. discrètes indépendantes. Deux v.a. discrètes X et Y sont indépen-
dantes ssi pour tout A ⊂ X(Ω) et tout B ⊂ Y (Ω), on a
P(X ∈ A,Y ∈ B) = P(X ∈ A)P(Y ∈ B).

Définition 2.1.13 — Espérance. Soit X une v.a. prenant ses valeurs dans {xk , K ≥ 1}. Si
la famille (xk P(X = xk ))k est sommable c-à-d si ∑ |xk |P(X = xk ) < +∞, on dit que X est
K≥1
intégrable et on définit l’espérance de X par

E(X) = ∑ xk P(X = xk ).
K≥1

Formule de transfert : Soit ϕ : R −→ R telle que ϕ(X) est intégrable, alors

E(ϕ(X)) = ∑ ϕ(xk )P(X = xk ).
K≥1

Définition 2.1.14 — Variance. Si E(X 2 ) < ∞, on appelle

• variance de X le réel

2
Var(X) = E (X − E(X))2 = ∑ (xk − E(X))2 P(X = xk ) ( Var(X) = E(X 2 ) −
 
E(X) ).
K≥1
p
• écart-type de X le réel σ (X) = Var(X).
• covariance de X et de Y (si les moments d’ordre 2, E(X 2 ) < ∞ et E(Y 2 ) < ∞) le réel



Cov(X,Y ) = E (X − E(X) (Y − E(Y ) = E(XY ) − E(X)E(Y ).

2.1.6 Lois discrètes usuelles :

Loi de Bernoulli. On dit qu’une v.a. X suit une loi de Bernoulli de paramètres p ∈ [0, 1] et on note
X ∼ B(p) si X est à valeurs dans {0, 1} et que
P(X = 1) = p et P(X = 0) = 1 − p
12 Chapitre 2. Notions générales de probabilités

On a E(X) = p et Var(X) = p(1 − p).

Dans ce cas, la v.a. X vaut 1 s’il y’a succès et 0 s’il y’a échec.

Loi uniforme. On dit qu’une v.a. X suit une loi uniforme sur {1, · · · , n} et on note X U ({1, · · · , n})
si X prend ses valeurs dans {1, · · · , n} et

1
P(X = k) = pour tout k ∈ {1, . . . , n}.
n
n+1 n2 − 1
On a E(X) = et Var(X) = .
2 12
Loi binomiale. On dit qu’une v.a. X suit une loi binomiale de paramètres n ≥ 1 et p ∈ [0, 1]
et on note X ∼ B(n, p) si X prend ses valeurs dans {0, · · · , n} et

P(X = k) = Cnk pk (1 − p)n−k ∀ k ∈ {0, · · · , n}.

On a E(X) = np et Var(X) = np(1 − p).

La loi binomiale donne le nombre de succès qu’on peut obtenir en répétant n épreuves simi-
laires (de même loi) et indépendantes ayant pour issues un échec et un succès (c-à-d n épreuves de
Bernoulli).

Loi de Poisson. On dit qu’une v.a. X suit une loi de Poisson de paramètre λ > 0 et on note
X ∼ P(λ ) si X prend ses valeurs dans N et

λk
pk = P(X = k) = e−λ ∀ k ∈ N.
k!
On a E(X) = λ et Var(X) = λ .

La loi de Poisson décrit le comportement du nombre d’événements se produisant dans un in-

tervalle de temps donné, lorsque la probabilité de réalisation d’un événement est très faible et que
le nombre d’essais est très grand.
Si le nombre moyen d’événements dans un intervalle de temps fixé est λ , alors la probabilté qu’il
existe exactement k événements (k entier naturel, k = 0, 1, 2 . . . ) est donnée par pk .

Exemples :
1. Si un événement se produit en moyenne 5 fois par seconde, pour étudier le nombre d’événements
se produisant pendant 60 secondes, on choisit comme modèle une loi de Poisson de paramètre
λ = 60 × 5 = 300.

2. Soit X la variable aléatoire du nombre de personnes réservant un billet d’avion pour la Mecque
le 20 mars à 9H30. X suit une loi binomiale dont l’effectif est très grand, tous les clients potentiels,
des millions ; et le paramètre p est très petit, la probabilité pour qu’un individu choisi au hasard ait
envie de se rendre à la Mecque le 20 mars par le vol de 9H30. On approxime en général la loi de X
par la loi de Poisson de paramètre np.

3. Soit X la variable aléatoire égale au nombre d’appels re¸us par un standard téléphonique dans un
intervalle de temps [0, T ], la loi de X est une loi de Poisson.
2.1 Espace probabilisé
13

4. Les clients arrivent à une banque ou un supermarché de manière aléatoire, ce qui signifie
que l’on ne peut pas prédire quand certains arriveront.
La loi ou la fonction de densité de probabilité décrivant de telles arrivées durant une une période
spécifique est la loi de Poisson.
Soit X la v. a. désignant le nombre d’événements c-à-d d’arrivées qui prend place durant une unité
de temps spécifique par exp. une minute ou une heure.
Etant donné que λ est une constante connue, la loi de probabilité est définie par :

λk
P(X = k) = e−λ , k = 0, 1, 2, . . . .
k!

La moyenne E(X) = λ signifie que λ doit représenter le taux ou la vitesse avec laquelle l’événe-
ment se produit.
On rencontre la distribution de Poisson dans l’étude des files d’attente.

Par exp., les travaux de réparation arrivent à un petit atelier de réparation de moteurs de fa¸con
totalement aléatoire à un taux de 10 par jour.

1. Quel est le nombre moyen de travaux re¸cus par jour ?

2. Quelle est la probabilité qu’aucun travail de réparation n’arrive pendant une heure, en suppo-
sant que l’atelier est ouvert 8 heures par jour.

En effet,
1. le nombre moyen de travaux re¸cus par jour est égal à λ = 10.
2. Pour calculer la probabilité qu’aucun travail de réparation n’arrive pendant une heure, on a besoin
10
de calaculer le taux d’arrivées par heure, c-à-d λheure = = 1.25 travaux par heure. Ainsi
8
0
(λheure )e−λheure
P{aucune arrivée par heure} = P(X = 0) = = 0.2865
0!
Loi géométrique. On dit que X suit une loi géométrique de paramètre p ∈ [0, 1] et on note X ∼ G (p)
si X elle est à valeurs dans N∗ et si

P(X = n) = p(1 − p)n−1 ∀ n ∈ N∗ .

1 1− p
On a E(X) = et Var(X) = 2 .
p p
la loi géométrique représente le nombre d’essais nécessaires de réalisation d’une expérience
jusqu’à son premier succès. En d’autres termes, cette loi correspond à la loi du temps d’attente dans
un processus de Bernoulli.

Remarque : Pour chacune des lois précédentes, on a ∑ P(X = n) = 1.

n
Proposition 2.1.3 On a
• Une loi de Bernoulli de paramètre p est une loi binomiale de paramètres 1 et p.
• La somme de 2 v.a. indépendantes suivant des lois binomiales de paramètres (n1 , p) et (n2 , p)
respectivement suit une loi binomiale de paramètres (n1 + n2 , p).
• La somme de deux v.a. indépendantes suivant respectivement des lois de Poisson de paramètres
λ1 et λ2 suit une loi de Poisson de paramètre λ1 + λ2 .
 14 Chapitre 2. Notions générales de probabilités

Proposition 2.1.4 Si (Xn )n est une suite de variables aléatoires de Bernoulli indépendantes de
même paramètre p, et si X est la variable aléatoire qui donne le rang du premier succès dans cette
successions d’épreuves, alors X suit une loi géométrique de paramètre p.

Théorème 2.1.5 — Caractérisation comme loi sans mémoire. Soit X une variable aléatoire
à valeurs dans N. X est sans mémoire c-à-d que ∀n, k ∈ N, P(X > n + k)|X > n) = P(X > k) si
et seulement si X suit une loi géométrique.

L’unique loi de probabilité discrète à perte de mémoire est la loi géométrique.

Cette propriété est le plus souvent exprimée en termes de « temps d’attente ». Supposons qu’une
variable aléatoire X soit définie comme le temps passé dans un magasin de l’heure d’ouverture
(disons 9H du matin) à l’arrivée du premier client. On peut donc voir X comme le temps qu’un
serveur attend avant l’arrivée du premier client.
La propriété de perte de mémoire fait une comparaison entre les lois de probabilité du temps
d’attente du serveur de 9H à l’arrivée du premier client, et celle du temps d’attente du serveur pour
qu’un client arrive à compter d’un délai arbitraire après l’ouverture (disons, par exp, une heure
après l’ouverture soit à partir de 10H du matin) sachant qu’aucun client n’est arrivé de l’ouverture
à l’écoulement de ce délai arbitraire. La propriété de perte de mémoire affirme que ces lois sont les
mêmes.
Ainsi, dans cet exemple, ce n’est pas parce que le serveur a déjà attendu, pendant une heure l’arrivée
d’un premier client qu’il peut espérer que le délai avant qu’arrive effectivement son premier client
soit plus faible qu’au moment de l’ouverture.

Attention : La perte de mémoire d’une loi de probabilité d’un nombre d’essais X jusqu’au premier
succès signifie

P(X > 50|X > 40) = P(X > 10),

cependant, elle n’implique pas

P(X > 50| > 40) = P(X > 50)

à moins que les événements (X > 50) et (X > 40) sont indépendants, ce qui n’est pas le cas.

2.1.7 Variables aléatoires réelles et Lois à densité

Proposition 2.1.6 — v.a. indépendantes. Soient X et Y deux v.a.r. sur Ω. On dit que X et Y sont
indépendantes si pour tout A, B ⊂ R,

P(X ∈ A,Y ∈ B) = P(X ∈ A)P(Y ∈ B).

Définition 2.1.15 — Lois à densité. Soit f : R → R une fonction positive d’intégrale 1

Z +∞ 
f (x)dx = 1 . On dit qu’une variable aléatoire X : Ω → R a pour densité f si sa loi
−∞
est définie par
Z
∀B ⊂ R, P(X ∈ B) = f (x)dx.
B
2.1 Espace probabilisé
15

Dans ce cas, pour a < b réels on a

Z Z b
P(a < X < b) = P(X ∈]a, b[) = f (x)dx = f (x)dx
]a,b[ a

Lois usuelles :

1
Loi uniforme sur [a, b] (a < b), notée U ([a, b]), de densité f (x) = 1 (x).
b − a [a,b]
Loi exponentielle de paramètre λ (λ > 0), notée E (λ ), de densité f (x) = λ e−λ x 1R+ (x).
La loi exponentielle est l’analogue dans le cas continu de la loi géométrique : c’est la seule loi à
densité continue sans mémoire, c-à-d vérifiant

P(X > s + t)|X > t) = P(X > s), ∀s, t > 0.

Loi gaussienne ou normale de moyenne m et de variance σ 2 > 0, notée N (m, σ 2 ), de densité

1  (x − m)2 
f (x) = √ exp − , ∀x ∈ R.
σ 2π 2σ 2

Proposition 2.1.7 Si X1 et X2 sont deux v.a. indépendantes suivant respectivement des lois
N (m1 , σ12 ) et N (m2 , σ22 ), alors X1 + X2 ∼ N (m1 + m2 , σ12 + σ22 ).

Définition 2.1.16 — Fonction de répartition. Soit X une v.a. réelle sur Ω. On appelle fonction
de répartition de X, et on note FX , la fonction définie par

∀t ∈ R, FX (t) = P(X ≤ t).

Proposition 2.1.8 On a
• ∀a, b ∈ R, P(a < X < b) = FX (b) − FX (a).
• FX est croissante et satisfait lim FX (t) = 0, lim FX (t) = 1.
t→−∞ t→+∞
La loi d’une v.a.r. X est entièrement déterminée par la fonction de répartition FX de X.
Si X est une v.a.r. admettant une densité f , alors
Z t
FX (t) = f (x)dx, ∀t ∈ R.
−∞

Exemple : (Lancé de dés) Soit X la somme des résultats des deux dés. On a
6
FX (1) = P(X ≤ 1) = 0 ; FX (4) = P(X ≤ 4) = 36 ; FX (12) = 1.

Proposition 2.1.9 Si (X,Y ) est un couple de variables aléatoires qui admet pour densité f(X,Y ) :
R2 → R, et si fX , fY sont les densités marginales de X et Y respectivement, X et Y sont indépen-
dantes ssi

f(X,Y ) (x, y) = fX (x) fY (y) pour presque tout (x, y) ∈ R2 .

Proposition 2.1.10 Si X et Y sont deux v.a.r. indépendantes et de carré intégrable alors elles sont
décorrélées, c-à-d E(XY ) = E(X)E(Y ).

Définition
Z 2.1.17 — Espérance. Soit X une variable aléatoire admettant pour densité f . Si
|x| f (x)dx < +∞, on dit que X est intégrable et on définit l’espérance (moment d’ordre 1) de
R
 16 Chapitre 2. Notions générales de probabilités

X par
Z
E(X) = x f (x)dx.
R
Proposition 2.1.11 Soient X et Y deux v.a.r. intégrables sur Ω. Alors, on a
1. ∀a, b ∈ R, E(aX + b) = aE(X) + b ;
2. E(X +Y ) = E(X) + E(Y ).

Z X : Ω → R une v.a.r. admettant pour densité f . Soit ϕ : R −→ R telle que

Proposition 2.1.12 Soit
ϕ(X) est intégrable ( |ϕ(x)| f (x)dx < +∞), alors
R
Z
E(ϕ(X)) = ϕ(x) f (x)dx.
R

La variance de X est le réel positif

 2
 Z
2
Var(X) = E (X − E(X)) = x − E(X) f (x)dx.
R
Proposition 2.1.13 Soit X une v.a.r. de carré intégrable. On a
1. Var(X) = E(X 2 ) + (E(X))2 ;
2. ∀a, b ∈ R, Var(aX + b) = a2Var(X).

2.2 Théorèmes de convergence

2.2.1 Lois des grands nombres :

Théorème 2.2.1 — Loi forte des grands nombres. Soit (Xn )n≥1 une suite de variables aléa-
toires réelles 2 a 2 indépendantes, de même loi (i.i.d.) d’espérance m. Pour tout n, on note
X1 + · · · + Xn
Xn =
n
Alors pour tout ε > 0, on les estimations
  C 
2  C
P Xn − m > ε ≤ 2 et E Xn − m ≤
nε n
De plus, la suite (X n )n≥1 converge presque sûrement vers m.

Remarque : La loi des grands nombres exprime que la moyenne des n premiers termes d’une suite
de variables aléatoires converge vers une constante qui est leur moyenne, c-à-d que la moyenne
empirique de cette suite se concentre autour de son espérance.

2.2.2 Théorème central limite :

On rappelle ici l’importance de la loi normale, comme étant la loi limite apparaissant lorsqu’on
examine les fluctuations de la moyenne empirique d’une suite de v.a. i.i.d. autour de l’espérance.
L’on sait que la moyenne empirique d’une suite de variables aléatoires undépendantes se concentre
autour de son espérance ; la question suivante est naturelle : que peut-on dire des fluctuations de la
2.2 Théorèmes de convergence 17

moyenne empirique autour de l’espérance, c’est-à-dire de la distribution de X n − m ? La réponse à

cette question, est le théorème Central Limite, il affirme que :
√
1- X n − m est de l’ordre de 1/ n

X n −m
2- La distribution de σ
√ approche la même distribution, lorsque n devient grand, quelle que soit
n
la distribution des Xi , tant que ceux-ci ont une variance σ 2 finie.

Théorème 2.2.2 — Théorème central limite. Soit (Xn )n∈N∗ une suite de v.a.r. i.i.d. de carré
X1 + · · · + Xn
intégrable, de moyenne m = E(X1 ) et de variance σ 2 . Soit X n = , alors pour tout
n
n ∈ N∗ on a
X −m
n
L σ −→n N (0, 1)
√
n
 3. Simulation de Variables aléatoires

La majorité des langages informatiques permettent de générer des nombres pseudo-aléatoires. Ce

sont en fait des suites récurrentes entières initialisées avec des paramètres liés à l’ordinateur puis
renormalisées pour être à valeurs dans [0, 1].
Via sa fonction "random", un langage fournit une suite de v.a. indépendantes de loi uniforme sur
[0, 1]. A partir de cette suite de v.a. indépendantes, on doit être capable de construire une suite de
v.a. indépendantes suivant n’importe quelle loi.

3.1 Simulation de Variables aléatoires discrètes

Simulation d’une v.a. de Bernoulli. Pour simuler une v.a. de Bernoulli de paramètre p ∈]0, 1[, il
suffit de simuler une v.a. U uniforme sur ]0, 1[ et de poser X = 1(U≤p) ; c-à-d X = 1 si U ≤ p avec
probabilité p et 0 sinon.

Simulation d’une v.a. binomiale. Pour simuler une v.a. binomiale de paramètres n ≥ 1 et p ∈]0, 1[,
il suffit de sommer n v.a. de Bernoulli de paramètre p indépendantes.

Simulation d’une v.a. discrète. Pour simuler une v.a. discrète à valeurs dans {xk / xk ∈ N} de
loi pk = P(X = xk ), k ∈ N, il suffit de simuler une v.a. U uniforme sur ]0, 1[ et de poser X = xk si
Pk−1 ≤ U < Pk où Pk est le cumul des pk : Pk = p1 + p2 + · · · + pk avec P0 = 0.

3.2 Simulation de Variables aléatoires à densité

3.2.1 Simulation d’une v.a. admettant une densité continue par inversion de la fonction
de répartition
Proposition 3.2.1 Soit X une v.a. de densité f continue et de fonction de répartition F inversible.
On pose Y = F(X). Alors Y suit une loi uniforme sur [0, 1].
 20 Chapitre 3. Simulation de Variables aléatoires

Pour simuler la v.a. X, si F −1 est connue analytiquement, il suffit donc de simuler une loi uniforme
sur ]0, 1[ et de calculer F −1 du résultat obtenu.

3.2.2 Simulation d’une v.a. bornée à densité bornée par la méthode de rejet
Proposition 3.2.2 Soit X une v.a. presque sûrement bornée de densité f presque partout bornée.
On suppose pour simplifier que X ∈ [0, 1] et on choisit m tel que f ≤ m p.p. Soient U et V deux
v.a. indépendantes de lois uniformes sur [0, 1] et [0, m] respectivement. Alors, conditionnellement à
[V < f (U)], U a même loi que X.
A partir de ce résultat, on construit la procédure de simulation suivante : étant donnée une v.a. X
comme dans la proposition, on procède à la simulation de U et V indépendantes. Si les réalisations
u et v de ces v.a. satisfont v < f (u) la réalisation de la simulation de X est u, sinon on procède à un
autre tirage des v.a. U et V .

3.2.3 Simulation d’une loi normale :

Danns certains cas, la connaissance des v.a. repose sur un changement de variable ; ainsi si une v.a.
s’exprime comme une fonction de v.a. indépendantes il est plus simple de simuler ces v.a. et de
reconstituer la v.a. de départ à travers une fonction que de chercher à la simuler directement. La loi
normale est un exemple de ce principe :

Proposition 3.2.3 Soient U et V deux v.a. indépendantes de loi uniforme sur ]0, 1[. On pose
√ √
X= −2 lnU cos 2πV, Y= −2 lnU sin 2πV.

Alors X et Y sont des v.a. indépendantes de loi N (0, 1).

Pour générer une v.a. N (0, 1), il faut générer deux v.a. indépendantes de loi uniforme sur ]0, 1[.
puis utiliser l’une des deux formules précédentes.

3.3 Méthode de Monte Carlo pour le calcul des intégrales et des moments :

La méthode de Monte Carlo pour faire des calculs d’intégrales est une méthode basée sur la
simulation aléatoire, elle repose sur la loi des grands nombres.
Sous certaines hypothèses, on peut approcher presque sûrement l’espérance d’une v.a. (une intégrale
dans le cas à densité) par la moyenne arithmétique de v.a. de même espérance.
Le principe de la méthode est alors de simuler ces v.a. et de considérer la réalisation de leur
moyenne arithmétique comme une approximation numérique de leur espérance commune.

3.3.1 Méthode Z
On suppose que l’on cherche à calculer numériquement I = f (x)dx pour une fonction f
R
intégrable.
Z 1
A l’aide de changements de variables, on se ramène au calcul de g(u)du pour une certaine
0
fonction g.
Etant donnée U une v.a. de loi uniforme sur ]0, 1[. Alors la formule de transfert s’écrit
Z Z 1
E(g(U)) = g(u)1]0,1[ (u)du = g(u)du
R 0
 3.3 Méthode de Monte Carlo pour le calcul des intégrales et des moments :
21
 u
u
 1
Ainsi en posant g(u) = f +f − pour u ∈ ]0, 1[ on a
1−u 1 − u (1 − u)2
Z Z 1
f (x)dx = g(u)du
R 0

Soit (U)n≥1 une suite de v.a. indépendantes suivant une loi uniforme sur ]0, 1[. La loi des grands
nombres affirme que
1 n
Z 1
∑ g(Ui ) −→n
n i=1 0
g(u)du p.s. quand n −→ +∞.

Une approximation numérique (estimateur) de l’intégrale I est alors donnée par la réalisation de
cette somme.

3.3.2 Précision (estimation d’erreur) :

On approche donc une constante (l’intégrale ou l’espérance) par la réalisation d’une v.a.
Remarquons qu’il n’est pas possible de caractériser avec certitude l’erreur d’approximation que
l’on commet, cependant on a les informations suivantes sur la v.a. :
1 n 
Z1
E ∑ i g(U ) = E g(U) = g(u)du,
n i=1 0

ceci veut dire que l’on approche la valeur de I sans erreur en moyenne.
d’autre part,
1 n  1

Var ∑ g(U i ) = Var g(U) ,
n i=1 n
ce qui montre que l’erreur quadratique moyenne tend vers 0 en O(1/n) quand n tend vers +∞.

3.3.3 Inérêts de la méthode

Cette méthode converge assez lentement et repose sur la qualité du générateur de nombres aléatoires
dont on dispose mais elle est très robuste. En particulier, en grandes dimensions (≥ 3), elle est plus
rapide et plus simple d’utilisation que les intégrateurs numériques.

3.3.4 Calcul approché des moments

On peut aussi utiliser cette méthode pour l’approximation des moments des v.a.
En effet, toujours par la loi des grands nombres, l’espérance E[ϕ(X)] d’une v.a. X pour une fonction
à valeurs réelles ϕ telle que ϕ(X) est intégrable, peut être approchée p.s. quand n grand par

1 n
E ϕ(X) ≈ ∑ ϕ(Xi )
n i=1
pour toute suite (Xi )i≥1 iid à X.

Même lorsque X admet une densité f , cette approximation peut être beaucoup plus précise
à n petit que le calcul direct de la valeur
Z
ϕ(x) f (x)dx
R
car les points alors choisis par la méthode de Monte Carlo se font selon la densité f et non unifor-
mément.
 22 Chapitre 3. Simulation de Variables aléatoires

3.4 Méthode de "simulation Monte Carlo"

La méthode de "simulation Monte Carlo" est un moyen qui permet de calculer une approximation
numérique de la fonction de répartition, mais également de calculer des probabilités faisant interve-
nir des phénomènes dont on ne connaît pas la distribution explicitement (phénomènes complexes
dépendant de variables multiples).

On suppose que l’on sait simuler une v.a. X (par exemple X est fonction d’un vecteur aléatoire dont
on connait la loi). Pour calculer la probabilité P(X ∈ B), on remarque que, si X a pour densité f ,
Z Z

P(X ∈ B) = f (x)dx = 1B (x) f (x)dx = E 1B (X) .
B R

Cette valeur, d’après la section précédente, peut s’approcher en simulant un grand nombre de fois
la variable X et en faisant la moyenne arithmétique des valeurs des réalisations obtenues de 1B (X),
c-à-d :
1 n
P(X ∈ B) ≈ ∑ 1B (Xi )
n i=1

pour des v.a. Xi iid de même loi que X. Autrement

card{i/ Xi ∈ B}
P(X ∈ B) ≈
n
c-à-d la probabilité que X soit dans B est approchée par la proportion de simulations observées
dans B.

- Enfin, grâce à cette méthode, on peut également calculer une distribution approchée de phé-
nomènes aléatoires complexes.

- Dans le cas d’une variable aléatoire X à densité, par exemple, il s’agit d’obtenir une densité
approchée, par exemple par une fonction constante par morceaux.
Pour cela, on discrétise l’ensemble des valeurs prises par X en intervalles I " assez petits ", puis on
approche P(X ∈ I) par la méthode de Monte Carlo pour chaque intervalle I. On obtient ainsi une
approximation discrète de la densité de X.

Exercice (calcul de π par méthode de Monte Carlo)

Z 1Z 1
On cherche à évaluer π en remarquant que π = 1D (x, y)dxdy, par une méthode de Monte
−1 −1
Carlo.

1. Montrer que π = 4.E 1D (X,Y ) , où X et Y sont deux variables aléatoires indépendantes
uniformes sur [−1, 1].
2. Proposer un estimateur Pn de π par la méthode de Monte Carlo.
3. Quelle est l’espérance et la variance de Pn .
 4. Modèles stochastiques

4.1 Processus stochastiques

4.1.1 Introduction
• Dans un modèle déterministe, partant d’un état initial, on a un seul état final. Ce modèle est
parfaitement connu et il n’ya aucun phénomène aléatoire.

• Un modèle stochastique intégre une part d’aléa.

En fait dans la réalité, il y’a de l’aléa : ( une panne de réveil , un retard à la SNCF, rencon-
trer un ami, qui va gagner un match de foot-ball ? ...) Dans la réalité, partant d’un état initial, il y’a
plusieurs états finaux ; la connaissance est imparfaite en plus il y’a des phénomène aléatoires.

On parle alors de stochasticité pour tout ce qui échappe au déterminisme.

Un système stochastique est un système évoluant de manière probabiliste dans le temps. On

trouve plusieurs exemples tels que la température quotidienne ou un centre d’appels téléphoniques.
Un modèle stochastique est une représentation mathématique d’un système stochastique.

Parmi les modèles stochastiques, on peut citer les processus stochastiques tels que les proces-
sus de Wiener, de Poisson, de comptage, de Markov, les processus gaussiens et les files d’attente.

4.1.2 Processus stochastiques

Définition 4.1.1 Soit (Ω, F , P) un espace probabilisé. Un processus stochastique est une famille
de variables aléatoires X = (Xt )t∈T , T appelé ensemble d’indices souvent assimilé au temps
(T = R+ , N, · · · ), définies sur (Ω, F , P) et à valeurs dans un espace métrique S muni de la tribu
borélienne.

Pour chaque ω fixé dans Ω, l’application qui à t associe Xt (ω) est appelée trajectoire ou réalisa-
tion du processus.
 24 Chapitre 4. Modèles stochastiques

S est appelé espace des états ou des phases. Par exp. S peut être R, C, un ensemble fini ou dénom-
brable.
Si T est fini ou dénombrable, on dit que le processus est discret ; si T n’est pas dénombrable, on
parle de processus continu.

Exemple : Marche aléatoire

la marche aléatoire discrète à une dimension sur le réseau périodique Z est le modèle de marche
aléatoire le plus simple. Imaginons un individu (ou " particule ") sur un escalier, qui tire à pile ou
face pour décider si le prochain pas sera vers le haut ou vers le bas. A chaque étape, il n’y a que
deux possibilités : un pas en avant ou un pas en arrière.
Notons :
p (0 < p < 1) la probabilité que la particule fasse un saut en avant (plutôt qu’un saut en arrière) ;
c’est le seul paramètre libre du problème ;
q = 1 − p la probabilité que la particule fasse un saut en arrière.
Le cas le plus simple (mouvement brownien), consiste à faire considérer que les directions "avant /
arrière" sont équivalentes (équiprobabilité) : p = q = 1/2.
Chacun des tirs au hasard pour choisir le mouvement constitue une épreuve de Bernoulli avec issues
équiprobables.
Après n pas, si Nn désigne le nombre de fois où on tire "pile", alors Nn suit la loi binomiale
B(n, 1/2) et on a

1 k
P(Nn = k) = C .
2n n
Notons Xn la position de la particule après n pas. En prenant X0 = 0 au départ et en ajoutant
1 pour chaque pas en avant (pile) et en retranchant 1 pour chaque pas en arrière (face), on a
Xn = Nn − (n − Nn ) = 2Nn − n.
Ceci montre que par rapport à la loi binomiale classique, ça revient à décaler les résultats de n/2
et de multiplier par 2. Dans ce cas, Xn = k si 2Nn − n = k, nécessairement n + k est pair ; ainsi
Nn = n+k
2 avec n et k de même parité ; On en déduit que
( n+k
1 2
P(Xn = k) = 2n Cn si n et k ont même parité
0 sinon

Définition 4.1.2 — Processus à accroissements indépendants. Un processus (Xt )t∈R+ est

dit à accroissements indépendants si ∀n ≥ 1, 0 < t1 < · · · < tn , les accroissements Xt2 − Xt1 , · · · ,
Xtn − Xtn−1 sont indépendants.

Définition 4.1.3 — Processus à accroissements stationnaires. Soit un processus (Xt )t∈R+ .

La propriété de statonnarité des accroissements signifie que la loi de Xt − Xs ne dépend que de
la longueur t − s de l’intervalle de temps : pour t ≥ s, Xt − Xs est de même loi que Xt−s .

4.2 Processus de Wiener ou mouvement brownien

Un processus (Wt )t∈R+ réel est un processus de Wiener ou mouvement brownien standard s’il
est issu de 0 c-à-d W (0) = 0 et s’il est à accroissements indépendants et stationnaires tel que
Wt ∼ N(0,t) pour tout t ≥ 0.
Le mouvement brownien est le nom donné aux trajectoires irrégulières du pollen en suspension
dans l’eau, observé par le botaniste Robert Brown en 1828.
 4.3 Processus gaussien 25

4.3 Processus gaussien

Un processus (Xt )t∈T à valeurs dans R est dit processus gaussien si toute combinaison linéaire finie
de (Xt )t∈T est une variable gaussienne (suit une loi normale), c-à-d

∀n ≥ 1 , t1 < t2 < · · · < tn , ∀α1 , α2 , · · · , αn ∈ R : α1 Xt1 + α2 Xt2 + · · · + αn Xtn ∼ N (mt , σt2 ).

4.4 Processus de Poisson

Définition 4.4.1 — Processus de comptage. Désignons par N(t) le nombre de "tops" se
produisant dans l’intervalle de temps [0,t]. Le processus (N(t)t≥0 est dit processus de comptage
s’il vérifie :
• N(0) = 0 ;
• ∀t ≥ 0, N(t) ∈ N ;
• t 7→ N(t) est croissante.

Pour tout 0 < a < b, N(b) − N(a) représente le nombre de tops se produisant dans l’inervalle de
temps ]a, b].
Si (Tn )n∈N est une suite de v.a.r. positives, alors le processus (N(t)t≥0 défini par N(t) = ∑ 1{Tn ≤t}
n≥1
est un processus de comptage. et on a

0 si t < T1
N(t) =
n si Tn < t < Tn+1

Définition 4.4.2 — Processus de Poisson. Un processus de Poisson de densité λ > 0 est un

processus de comptage (N(t)t≥0 tel que :
• le processus est à accroissements indépendants ;
• le nombre de tops se produisant dans un intervalle de temps de longueur t ≥ 0 suit une loi de
Poisson de paramètre λt, c-à-d

(λt)n
P N(s + t) − N(s) = n = e−λt


∀s ≥ 0, t ≥ 0, ∀n ∈ N,
n!
Remarque : Les processus de Poisson sont souvent utilisés pour modéliser des files d’attente,
chaque top représentant l’appel d’un client au guichet.

4.5 Chaines de Markov

4.5.1 définitions et propriétés
Définition 4.5.1 — Processus de Markov. Un processus de Markov est un processus stochas-
tique satisfaisant la propriété de Markov, c-à-d

∀t1 < t2 < · · · < tn < t, ∀A ∈ B(R),

P Xt ∈ A|Xt1 , Xt2 , · · · , Xtn = P Xt ∈ A|Xtn p.s.

Cette propriété (de Markov) exprime que le passé et le futur sont inconditionnellement indépendants,
le présent étant donné.
En d’autres termes, pour un processus de Markov l’information utile pour la prédiction du futur est
entièrement contenue dans l’état présent et ne dépend pas des états antérieurs ; un tel processus est
sans mémoire.
Un processus de Markov en temps discret est une suite (Xn )n de variables aléatoires vérifiant la
propriété précédente. La valeur Xn étant l’état du processus à l’instant n.
 26 Chapitre 4. Modèles stochastiques

Définition 4.5.2 — Chaine de Markov. Une chaine de Markov est un processus de Markov à
temps discret ou à temps discret et à espace d’états fini ou dénombrable.

Dans ce cas, la loi conditionnelle de Xn+1 sachant le passé s’exprime par

∀n ∈ N, ∀i0 , i1 , · · · , in−1 , i, j, P Xn+1 = j|X0 = i0 , X1 = i1 , · · · , Xn−1 = in−1 , Xn = i = P Xn+1 = j|Xn = i .
n
Exemple : Soit Rn , n ≥ 0 des variables indépendantes à valeurs dans E = N. Alors Sn = ∑ Ri et
i=1
n
Pn = ∏ Ri sont des chaines de Markov.
i=1

Une chaine de Markov peut être vue comme un système dynamique, ce qui veut dire que
Xn+1 = fn (Xn ), où fn est une "transformation aléatoire" indépendante du passé. Dans l’exemple
précédent, fn (Xn ) est la somme (ou le produit) de Xn (ici Xn = Sn ou Pn ) avec Rn+1 .
Si la transformation aléatoire fn ne dépend pas de n, c-à-d si Xn+1 = f (Xn ) pour tout n pour une
certaine transformation f , on dit que X est une chaine de Markov homogène.
Définition 4.5.3 Soit X = (Xn )n≥0 une chaine de Markov à valeurs dans E fini. On appelle
probabilité de transition de l’état i à l’état j en un
pas (ou simplement probabilité de transition
de l’état i à l’état j) le nombre P Xn+1 = j|Xn = i . On note pi j = P Xn+1 = j|Xn = i).

Définition 4.5.4 Une chaine de Markov est dite homogène si ses probabilités de transition ne
dépendent pas de n, c-à-d si

∀n ≥ 1, ∀(i, j) ∈ E 2 ,



P Xn+1 = j|Xn = i = P Xn = j|Xn−1 = i .

Remarque : Une chaine de Markov est homogène si

∀n ≥ 1, ∀(i, j) ∈ E 2 , P Xn+1 = j|Xn = i = P X1 = j|X0 = i .

Proposition 4.5.1 Soit une suite Y = (Yn )n≥1 de variables aléatoires indépendantes et de même
loi, à valeurs dans un espace F, et soit f : E × F → E une application mesurable. Soit la suite
X = (Xn )n≥0 définie par : ∀n ∈ N, Xn+1 = f (Xn ,Yn+1 ). On suppose que la suite Y est indépendante
de X0 . Alors X est une chaine de Markov homogène.

Remarque : Toute chaine de Markov homogène peut être simulée via une relation de récurrence
de la forme Xn+1 = f (Xn ,Yn+1 ) pour une fonction f bien choisie.

Dans la suite, toutes les chaines de Markov sont supposées homogènes.

4.5.2 Probabilités et matrice de transition

Il s’agit de modéliser une chaine de Markov à l’aide de représentations synthétiques afin de
connaitre l’évolution des états du système. On utilisera les matrices ou les graphes.

Définition 4.5.5 On appelle matrice de transition (quand E est fini) ou noyau de transition ou
opérateur de transition (quand E est infini) la famille des nombres P = (pi j )(i, j)∈E 2 .

Proposition 4.5.2 La matrice de transition P = (pi j )(i, j)∈E 2 est stochastique, c-à-d
• ∀(i, j) ∈ E 2 , pi j ≥ 0
• ∀i ∈ E, ∑ pi j = 1 (la somme des termes de chaque ligne de P est égale à 1).
j∈E
 4.5 Chaines de Markov 27

Remarque : La matrice d’une chaine de Markov est forcément stochastique et inversement, toute
matrice stochastique est la matrice d’une chaine de Markov.

Pour k ≥
1, la probabilité de transition de l’état i à l’état

j en k pas (sur k
étapes), P Xn+k =
j|Xn = i ne dépend pas de n, c-à-d P Xn+k = j|Xn = i = P Xk = j|X0 = i .
(k)

On note pi j = P Xk = j|X0 = i .

Exemple : Une grenouille monte sur une échelle. Chaque minute, elle peut monter d’un barreau
avec probabilité 1/2, ou descendre d’un barreau avec probabilité 1/2. L’échelle a 5 barreaux. Si la
grenouille arrive tout en haut, elle saute en bas de l’échelle avec probabilité 1/2 ou redescend d’un
barreau.
On appelle Xn la position de la grenouille sur l’échelle. L’espace d’états est donc E = {0, 1, 2, 3, 4, 5}.
Si a un instant n la grenouille est au niveau i ∈ {1, 2, 3, 4} de l’échelle, alors à l’instant n + 1 elle
sera :
au barreau i + 1 avec probabilité 1/2
au barreau i − 1 avec probabilité 1/2.

ce qui s’exprime par

P Xn+1 = i + 1|Xn = i
= 1/2 = P X1 = i + 1|X0 = i

,
P Xn+1 = i − 1|Xn = i = 1/2 = P X1 = i − 1|X0 = i .
Ces probabilités ne dépendent pas de n, il parait qu’il s’agit d’une chaine de Markov homogène. Si
c’est le cas, la matrice de transition se traduit par :

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

Si la grenouille se retrouve à l’état 5, alors elle peut soit passer à l’état 4, soit passer à l’état 0. La
dernière ligne de la matrice est donc


1/2 0 0 0 1/2 0 ,

là encore cela ne dépend pas de l’instant n.

Si la grenouille est à l’état 0, elle ne peut que passer à l’état 1. La première ligne de la matrice est
alors


0 1 0 0 0 0

(Xn ) est bien une chaine de Markov homogène, avec matrice de transition P.

4.5.3 Propriétés des chaines de Markov homogènes

Soit X = (Xn )n≥0 une chaine de Markov. Soit n ∈ N. Il ne faut pas confondre "loi de Xn " et "loi
conditionelle de Xn sachant Xn−1 ". La seconde se calcule facilement à l’aide de la matrice de
transition.
28 Chapitre 4. Modèles stochastiques

Définition 4.5.6 On appelle loi initiale de X la loi de X0 , c-à-d la donnée des valeurs :
π 0 (i0 ) = P X0 = i0 ), i0 ∈ E.

Proposition 4.5.3 — loi de dimension finie d’une chaine de Markov . La loi d’une chaine de
Markov X = (Xn )n≥0 est caractérisée par sa matrice de transition P et sa loi initiale : pour tout
n ≥ 1, la loi jointe de (X0 , X1 , . . . , Xn ) est donnée par

P X0 = i0 , X1 = i1 , . . . , Xn−1 = in−1 , Xn = in ) = P X0 = i0 ) pi0 i1 pi1 i2 . . . pin−1 in

Définition 4.5.7 Un chemin est simplement la donnée d’un vecteur fini (x0 , x1 , . . . , xn ) ∈ E n .

Dans la prop. précédente, la probabilté P X0 = i0 , X1 = i1 , . . . , Xn−1 = in−1 , Xn = in ) est la probabi-

lité de suivre le chemin (i0 , i1 , . . . , in ).

Dém. : En effet, en posant ak = P X0 = i0 , X1 = i1 , . . . , Xk−1 = ik−1 , Xk = ik ) ; par récurrence sur n

on a :


an+1 = P Xn+1 = in+1 |X0 = i0 , X1 = i1 , . . . , Xn−1 = in−1 , Xn = in an


= P Xn+1 = in+1 |Xn = in ) P X0 = i0 pi0 i1 pi1 i2 · · · pin−1 in (pté de Markov)


= P X0 = i0 pi0 i1 pi1 i2 . . . pin−1 in pin in+1 .

Proposition 4.5.4 —


Propriété de Chapman-Kolmogorov. la matrice de transition en k pas,
P Xn+k = j|Xn = i est égale à la puissance kème de la matrice de transition P. En notant
(i, j)∈E 2
(k) (k)

pi j = P Xn+k = j|Xn = i et P(k) = pi j (i, j)∈E 2 , on a P(k) = Pk .

Proposition 4.5.5 — lois marginales. La loi de Xn+k est donnée par

(k)
P(Xn+k = j) = ∑ P(Xn = i) pi j .
i∈E

En particulier, on a

P(Xn+1 = j) = ∑ P(Xn = i) pi j ,
i∈E

et par récurrence, on a
(n)
P(Xn = j) = ∑ P(X0 = i) pi j
i∈E

Forme matricielle : On note π n la loi ou distribution de Xn ; c’est le vecteur-ligne π n = (πin )i∈E

où πin = P(Xn = i).
Les deux formules précédentes se réecrivent

π n+k = π n Pk et π n+1 = π n P , ainsi π n = π 0 Pn (équations de Chapman-Kolmogorov).

Exercice : Une chaine de Markov avec états E = {1, 2} a la matrice de transition

 
a 1−a
P= , a ∈]0, 1[.
1−a a

1. Diagonaliser P.
2. Calculer Pn pour n ≥ 1.
4.5 Chaines de Markov 29

3. Calculer la loi de Xn pour tout n, sachant que l’on part de l’état X0 = 1.

Exemple 1 : Doudou le hamster

Exemple 2 : The Gardener Problem (Problème du jardinier : [voir H. Taha]

Every year, during the March-through-September growing season, a gardener uses a chemical test
to check soil condition. Depending on the outcome of the test, productivity for the new sea- son can
be one of three states : (1) good, (2) fair, and (3) poor. Over the years, the gardener has observed that
last year’s soil condition impacts current year’s productivity and that the situation can be described
by the following Markov chain :

F IGURE 4.5.1
The transition probabilities show that the soil condition can either deteriorate or stay the same but
never improve.
For example, if this year’s soil condition is good (state 1), there is a 20% chance it will not change
next year, a 50% chance it will be fair (state 2), and a 30% chance it will deteriorate to a poor
condition (state 3). The gardener alters the transition probabilities by using organic fertilizer. In this
case, the transition matrix becomes :

F IGURE 4.5.2
The use of fertilizer can lead to improvement in soil condition.

Il y’a 10% de chance que l’état du sol change de moyen vers bon c-à-d de l’état 2 vers l’état 1 ; 5%
de faible vers bon et 40% faible vers moyen.

Exercice 1 : An engineering professor acquires a new computer once every two years.
The professor can choose from three models : M1, M2, and M3. If the present model is M1, the
next computer can be M2 with probability .25 or M3 with probability .1. If the present model is
M2, the probabilities of switching to M1 and M3 are .5 and .15, respectively. And, if the present
model is M3, then the probabilities of purchasing M1 and M2 are .7 and .2, respectively. Represent
the situation as a Markov chain.

Exercice 2 : A police car is on patrol in a neighborhood known for its gang activities. During a
patrol, there is a 60% chance of responding in time to the location where help is needed ; else
regular patrol will continue. Upon receiving a call, there is a 10chance for cancellation (in which
30 Chapitre 4. Modèles stochastiques

case normal patrol is resumed) and a 30% chance that the car is already responding to a previous
call. When the police car arrives at the scene, there is a 10% chance that the instigators will have
fled (in which case the car returns back to patrol) and a 40% chance that apprehension is made
immediately. Else, the officers will search the area. If apprehension occurs, there is a 60% chance
of transporting the suspects to the police station ; else they are released and the car returns to patrol.
Express the probabilistic activities of the police patrol in the form of transition matrix.

Retour au problème du jardinier avec les engrais : Dans la suite la matrice P1 est notée P.

F IGURE 4.5.3
The initial condition of the soil is good that is x(0) = 1 0 0 . Determine the absolute

probabilities of the three states of the system after 1, 8 and 16 gardening seasons.

F IGURE 4.5.4
 4.5 Chaines de Markov 31

F IGURE 4.5.5
Ainsi x(1) vaut

F IGURE 4.5.6

x(8) vaut
F IGURE 4.5.7

x(16) vaut
F IGURE 4.5.8
The rows of P8 and the vector of absolute probabilities a x(8) are almost identical. The result is
more evident for P16 . It demonstrates that, as the number of transitions increases, the absolute
probabilities become independent of the initial x(0) . The resulting probabilities are known as the
steady-state probabilities.

4.5.4 Classification des états d’une une chaine de Markov

On s’intéresse à la "dynamique" des chaines de Markov.
les états d’une chaine de Markov peuvent être classés sur la base de la probabilité de transition pi j
de P.

Etats accessibles à partir d’un état donné : On considère une chaine de Markov homogène. Soit
(i, j) ∈ E 2 :
Définition 4.5.8 On dit qu’un état j est accessible à partir d’un état i (ou qu’un état i conduit à
(n)
un état j) si il existe n ≥ 0 tel que P(Xn = j|X0 = i) > 0, c-à-d si ∃n ≥ 0 tel que pi j > 0. On
note { j ← i}.
(0)
En particulier, un état j est toujours accessible depuis lui même, puisque p j j > 0.

Classes de communication :
32 Chapitre 4. Modèles stochastiques

Définition 4.5.9 On dit que i et j communiquent si j est accessible à partir de i et i accessible

(n) (m)
à partir de j, c- à-d s’il existe (n, m) ∈ N2 tels que pi j > 0 et p ji > 0. On note { j ↔ i}.

Proposition 4.5.6 La relation communiquer "{ j ↔ i}" est une relation d’équivalence.
Ceci signifie que l’on peut regrouper les éléments de E en paquets, chaque paquet regroupant tous
les éléments qui communiquent entre eux. Ainsi on a une partition de E en classes d’équivalence
appelées classes de communication.

Définition 4.5.10 Une chaine X est irréductible s’il existe une seule classe d’équivalence,
c-à-d si tous les états communiquent.

La notion d’irréductibilité est liée à la matrice de transition de la chaine et non à la loi initiale. Pour
montrer qu’une chaine de Markov est irréductible, il peut être utile de tracer un graphe orienté dont
les sommets sont les états de la chaine et où une arête représente une transition possible (l’arête
(i, j) existe uniquement si pi j > 0). La chaine est alors irréductible si et seulement s’il existe un
chemin fermé passant au moins une fois par tous les états de la chaine.

La relation être accessible, notée ← s’étend aux classes d’équivalence : pour deux classes C et C0
on a

{C ← C0 } ⇔ ∃(i, j) ∈ C ×C0 , i ← j ⇔ {∀(i, j) ∈ C ×C0 , i ← j}

Une classe C est dite finale ou fermée si elle ne conduit à aucune autre c-à-d si la classe est
minimale pour la relation ← ; ceci s’exprime par : pour tout i, j ∈ E : i ∈ C et i → j −→ j ∈ C
Sinon, elle est dite transitoire ou transiente.
Si C = {i0 } est fermée, i0 est dit état absorbant.
Définition 4.5.11 On dit que
• un état j est absorbant s’il retourne à lui-même avec certitude dans une transition c-à-d si
p j j = 1.
• un état j est transient s’il peut atteindre un autre état mais ne peut pas lui-même être atteint à
(n)
partir d’un autre état, c-à-d si lim pi j = 0 pour tout i.
n→∞
• un état j est récurrent si la probabilité d’être revisité à partir d’autres états est 1 (c-à-d partant
de j, la chaine repasse en j presque sûrement). Cela peut se produire ssi l’état j n’est pas
transient.
• un état j est périodique de période t > 1 si un retour n’est possible qu’en t, 2t, 3t, . . . étapes,
(n)
dans ce cas la période est d( j) = t = pgcd{n/p j j > 0} > 1.
(n)
Ceci signifie que p j j = 0 chaque fois que n n’est pas divisible par t.
Si d( j) = 1, l’état j est dit apériodique.

Proposition 4.5.7 Les états d’une même classe ont même période.
on peut donc parler de la période d’une classe d’états.

Définition 4.5.12 Une chaine de Markov est

• irréductible récurrente si elle est irréductible et si tous les états sont récurrents ;
• irréductible transiente si elle est irrééuctible et si tous les états sont transitoires.
Proposition 4.5.8 Une chaine de Markov irréductible sur un espace E fini est irréductible récur-
rente.
Par exp., considérons la chaine de Markov définie par la matrice de transition
4.5 Chaines de Markov 33

 
0 1 0 0
 0 0 1 0 
P= 
 0 0 .3 .7 
0 0 .4 .6
les états 1 et 2 sont transients parce qu’ils ne peuvent pas être atteints à nouveau une fois que le
système se trouve dans les états 3 et 4.
En plus, les états 3 et 4 peuvent être à la fois des états absorbants si p33 = p44 = 1. Dans un tel cas,
chaque état forme un ensemble fermé.

F IGURE 4.5.9

F IGURE 4.5.10
34 Chapitre 4. Modèles stochastiques

F IGURE 4.5.11
Exemple 1 : Considérons la chaine de Markov définie par le graphe :

F IGURE 4.5.12
cette chaine de Markov est réductible.
On a 3 classes : {1, 3}, {2}, {4, 5}.
Létat 2 est transitoire.
Les classes {1, 3}, et {4, 5} sont finales.
Quitte à renuméroter les états, on peut écrire :
4.5 Chaines de Markov 35

F IGURE 4.5.13
Exemple 2 : Soit le graphe

F IGURE 4.5.14
Les classes sont {1, 2} et {3}.
Une seule classe finale : {3}.
L’état 3 est absorbant.

Exemple 3 : Considérons cette fois-ci la chaine de Markov définie par le graphe :

F IGURE 4.5.15
Ici, la chaine est irréductible.
Chaque état est périodique de période 2.

F IGURE 4.5.16
 36 Chapitre 4. Modèles stochastiques

Exercice : On considère la chaine de Markov sur 5 états 1, 2, 3, 4 et 5 de matrice de transition P :

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

1. Dessiner la chaine de Markov.

2. Classifier les états.
3. Quelle est la probabilité en partant de 1 et en 4 étapes d’arriver en 5 ?

Définition 4.5.13 Une chaine de Markov fermée (irréductible) est dite ergodique si tous les
états sont récurrents et apériodiques (c-à-d si la matrice P admet une puissance Pn > 0).

Dans ce cas les probabiltés absolues, après n étapes, π n = π 0 Pn convergent vers une distribution
limite, quand n → ∞, qui est indépendante de la loi initiale π 0 .

4.5.5 Lois ou probabilités stationnaires ; Temps moyen de premier retour

Lois ou probabilités stationnaires :
L’une des problématiques les plus courantes concernant les chaines de Markov homogènes consiste
à déterminer leurs distributions (ou probabilités) invariantes (ou stationnaires) et à étudier la
convergence éventuelle de la chaine vers ces distributions.
Définition 4.5.14 On appelle probabilté invariante ou loi stationnaire pour P (pour la chaine)
toute mesure π = (πi )i∈E sur l’espace d’états E vérifiant :
• π = πP,
• ∀i ∈ E, πi ≥ 0,
• ∑ πi = 1.
I∈E

Définition 4.5.15 Une chaine de Markov, de matrice de transition P, est stationnaire si et

seulement si sa loi initiale π 0 est une probabilté stationnaire, c-à-d si elle vérifie π 0 P = π 0 .
Dans ce cas pour tout n, la loi de Xn vérifie π n = π 0 .

Proposition 4.5.9 1. Si l’espace d’états est fini, il existe au moins une mesure stationnaire.
2. Si la chaine est irréductible, il existe au plus une mesure stationnaire.
Proposition 4.5.10 Si la chaine est irréductible sur un espace d’états fini, il existe une unique
probabilité stationnaire.

Proposition 4.5.11 Soit (Xn )n∈N une chaine de Markov à états finis {1, . . . , N}. On suppose que
pour tout i ∈ {1, . . . , N}, (P(Xn = i))n∈N converge et on note πi sa limite. Alors π = (π1 , . . . , πN )
est une distribution invariante pour la chaine.
4.5 Chaines de Markov 37

Temps moyen de premier retour d’une chaine ergodique :

F IGURE 4.5.17
38 Chapitre 4. Modèles stochastiques

F IGURE 4.5.18
 4.6 Application : 39

F IGURE 4.5.19

F IGURE 4.5.20

4.6 Application :
On dispose de deux machines identiques fonctionnant indépendamment et pouvant tomber en panne
au cours d’une journée avec la probabilité q = 41 . On note Xn le nombre de machines en panne au
début de la n-ième journée.
1. On suppose que, si une machine est tombée en panne un jour, elle est réparée la nuit suivante
et qu’on ne peut réparer qu’une machine dans la nuit. Montrer que l’on peut définir ainsi une
chaine de Markov dont on déterminera le graphe, la matrice de transition et éventuellement
les distributions stationnaires.
2. Même question en supposant qu’une machine en panne n’est réparée que le lendemain, le
réparateur ne pouvant toujours réparer qu’une machine dans la journée.
3. Le réparateur, de plus en plus paresseux, met maintenant 2 jours pour réparer une seule
machine. Montrer que (Xn ) n’est plus une chaine de Markov, mais que l’on peut construire
un espace de 5 états permettant de décrire le processus par une chaine de Markov dont on
donnera le graphe des transitions. Calculer la probabilité que les 2 machines fonctionnent
après n jours (n = 1, n = 2 et n = 3) si elles fonctionnent initialement.

Corrigé :

1. L’ensemble des états est E = {0, 1} car si le soir il y a une ou aucune machine en panne, le
lendemain matin, il y en aura 0 ; et si le soir, il y en a 2, le lendemain matin, il y en aura une
seule.
Le nombre de machines en panne le matin ne dépend que de celui de la veille au matin et de
ce qu’il s’est passé dans la journée, ceci indépendamment de la période de l’année. On a
40 Chapitre 4. Modèles stochastiques

donc bien une chaine de Markov dont il faut déterminer la matrice de transition.
On a
• p00 = (1 − q)2 + 2q(1 − q) = 1 − q2 où
(1 − q)2 correspond à aucune panne dans la journée et
2q(1 − q) à une seule panne qui peut provenir d’une machine ou de l’autre ;
• p01 = q2 (les 2 machines tombent en panne dans la journée et ces pannes sont indépendantes
entre elles) ;
• p10 = 1 − q (la machine en panne est réparée et l’autre fonctionne tjs) ;
• p11 = q (la machine en panne
 est réparéeet l’autre est tombée en panne).
1 − q2 q2
Ainsi, on a la matrice : P = .
1−q q
La distribution stationnaire est déterminée en résolvant
1 − q2 q2
 
(π0 π1 ) = (π0 π1 ) avec π0 + π1 = 1.
1−q q
1−q 2
q 1 12 1
On obtient π0 = 1−q+q 2 et π1 = 1−q+q2 ; or q = 4 ainsi π0 = 13 et π1 = 13 .
0
2. Dans ce cas, l’ensembles des états est E = {0, 1, 2} car aucune machine n’est réparée la
nuit. On a
p000 = (1 − q)2 (c-à-d aucune panne dans la journée) ;
p001 = 2q(1 − q) (une des 2 machines est tombée en panne) ;
p010 = 1 − q (la machine qui fonctionne ne tombe pas en panne) ;
p011 = q (la machine qui fonctionne tombe en panne, l’autre est réeparée ;
p012 = 0 ((la machine en panne est sûre de refonctionner le lendemain) ;
p020 = p022 = 0 ;
p021 = 1 (une seule des 2 machines en panne est réparée). D’où la matrice

(1 − q)2 2q(1 − q) q2
 

P0 =  1 − q q 0 
0 1 0
La distribution stationnaire est déterminée en résolvant
(1 − q)2 2q(1 − q) q2
 

(π0 π1 π2 ) = (π0 π1 π2 )  1 − q q 0  avec π0 +π1 +π2 = 1.

0 1 0
1−q 2q−q2 q2 −q3 48 28
On obtient π0 = 1+q+−q3
, π1 = 1+q+−q3
et π2 = 1+q+−q3
; d’où π0 = 79 , π1 = 79 et
3
π2 = 79 .
3. Si on garde l’ensemble des états E 0 , on n’a pas une chaine de markov car, lorque l’on a 2
machines en panne par exemple, on ne peut pas savoir si le lendemain, on en aura 1 ou 2 en
panne : tout dépend si c’est le premier jour de réparation ou le second. On est donc amené à
introduire 2 états supplémentaires :
1’ : 1 machine en panne dont c’est le deuxième jour de réparation,
2’ : 2 machines en panne et deuxième jour de réparation pour la première.
D’où l’espace de 5 états E” = {0, 1, 2, 10 , 20 }. Dans ce cas, on a
p”00 = (1 − q)2 , p”01 = 2q(1 − q), p”02 = q2 , p”010 = p”020 = 0 ;
p”110 = 1 − q, p”120 = q, p”10 = p”11 = p”12 = 0 ;
p”10 1 = q, p”220 = 1, p”210 = 1 ; les autres probabilités sont nulles.
La probabilité que les 2 machines fonctionnent après n jours, ceci revient à calculer les puissances
de la matrice de transition P” :
4.6 Application : 41

• n = 1 cette proba est égale P(X1 ) = 0|X0 = 0) = p”00 = (1 − q)2 (le premier terme ds la matrice
de transition P”) ;
• n = 2 cette proba est égale P(X2 ) = 0|X0 = 0) = p”00 p”00 = (1 − q)4 (le premier terme ds la
matrice de transition P”2 ) ;
• n = 3 cette proba est égale P(X3 ) = 0|X0 = 0) = p”00 p”00 p”00 + p”01 p”110 p”10 0 = (1 − q)6 +
2q(1 − q)3 (le premier terme ds la matrice de transition P”3 ).
 5. Processus de décision markoviens

5.1 Processus de décision markoviens

Définition 5.1.1 Un processus de décision markovien (Markov decision process, ou MDP) est
un processus stochastique contrôlé satisfaisant la propriété de Markov et défini par :
• un ensemble d’états S (incluant un étant initial s0 ) dans lequel évolue le processus ;
• un ensemble d’actions A qui contrôlent la dynamique de l’état ;
• un espace des temps T , ou axe temporel ;
• une fonction ou modèle de transition p(s, a, s0 ) = P(s0 |s, a) (les probabilités de transition entre
états), où a ∈ A(s) ; cette fonction définit l’effet des actions de l’agent sur l’environnement ;
• une fonction de récompense r qui permet de déterminer le(les) but(s) à atteindre et les
éventuelles zones dangereuses de l’environnement.

Cette fonction r peut être définie de différentes manières, suivant le problème à résoudre :
* r : S × A × S × R → [0, 1] cas général. r(s, a, s0 , v) désigne la probabilité d’obtenir une récompense
v pour être passé de l’état s à s0 en ayant effectué l’action a ;
* r : S × A × S → R , récompense déterministe ;
* r : S × A → R , récompense déterministe ratachée à l’action en ignorant son résultat ;
* r : S → R , récompense déterministe ratachée à un état donné.

Pour une action a fixée, P(s0 |s, a) représente la probabilité que le système passe dans
l’état s0 après avoir exécuté l’action a dans l’état s.
Evidemment, on a ∑ P(s0 |s, a) = 1.
s0
44 Chapitre 5. Processus de décision markoviens

F IGURE 5.1.1 – Processus décisionnel de Markov

Dans le MDP représenté par la figure ci-dessus, à chaque instant t de T , l’action at est appliquée
dans l’état courant st , influençant le processus dans sa transition vers l’état st+1 . La récompense rt
est émise au cours de cette transition.
Un MDP est un modèle général pour un environnement stochastique dans lequel un agent peut
prendre des décisions (et où les résultats de ses actions sont aléatoires) et reçoit des récompenses.

On suppose A et S finis.

• Comme résultat d’avoir choisi l’action a dans l’état s à l’instant t, l’agent décideur re-
çoit une récompense, ou revenu rt = r(s, a) ∈ R.
Les valeurs de rt positives peuvent être considéerés comme des gains et les valeurs négatives
comme des côuts.
• La représentation vectorielle de la fonction de récompense r(s, a) consiste en |A| (=card(A))
vecteurs ra de dimension |S|.

Remarques :

1. Les MDP sont utilisés pour étudier des probèmes d’optimisation à l’aide d’algorithmes de
programmation dynamique ou d’apprentissage par renforcement qui consiste, pour un agent
autonome, à apprendre les actions à prendre à partir d’expériences, de façon à optimiser une
récompense quantitative au cours du temps.
2. On peut également considérer des récompenses aléatoires r(s, a) et dans ce cas on considère
la valeur moyenne rt = r̄(s, a). En particulier, rt peut dépendre de l’état d’arrivée s0 selon
r(s, a, s0 ). On considère alors la valeur moyenne r̄(s, a) = ∑s0 P(s0 |s, a)r(s, a, s0 ).
5.1 Processus de décision markoviens 45

F IGURE 5.1.2

F IGURE 5.1.3
46 Chapitre 5. Processus de décision markoviens

F IGURE 5.1.4

F IGURE 5.1.5
5.1 Processus de décision markoviens 47

F IGURE 5.1.6

F IGURE 5.1.7
48 Chapitre 5. Processus de décision markoviens

F IGURE 5.1.8
5.1 Processus de décision markoviens 49

Exemple 1 de MDP :
Cet exemple représente un processus de Décision Markovien à trois états distincts {s0 , s1 , s2 }
représentés en vert. Depuis chacun des états, on peut effectuer une action de l’ensemble {a0 , a1 }.
Les nœuds rouges représentent donc une décision possible (le choix d’une action dans un état
donné).
Les nombres indiqués sur les flèches sont les probabilités d’effectuer la transition à partir du nœud
de décision. Enfin, les transitions peuvent générer des récompenses (dessinées ici en jaune).

F IGURE 5.1.9
50 Chapitre 5. Processus de décision markoviens

F IGURE 5.1.10
5.1 Processus de décision markoviens 51

Exemple 2 : Schéma d’interaction entre agent (intelligence artificielle) et son environnement ;

cas du contrôle d’un drone :
Dans le cadre du contrôle d’un drone, l’idée de l’apprentissage par renforcement est de concevoir
un agent implanté au sein de notre drone et dictant à ce dernier les décisions rationnelles à prendre
dans chacune des situations rencontrées.

A chaque instant, ces décisions seront prises selon les informations disponibles sur l’environnement :
le signal de perception sur l’environnement (signal d’observation) et le signal de récompense.
En intégrant l’environnement dans notre schéma, il apparait que nous avons décrit une boucle
d’interaction entre, d’une part, l’agent et, d’autre part, l’environnement dans lequel évolue l’agent.

F IGURE 5.1.11

St , At , rt , St+1 , At+1 , rt+1 , St+2 , At+2 , rt+2 , . . .

Processus de génération des données d’apprentissage

Ainsi, à chaque instant, l’agent exécute une décision, laquelle influence les informations (signaux
de perception et de récompense) transmises à l’agent par le biais de l’environnement. Ce proces-
sus se répète encore et encore. Cette boucle d’interactions définit une série temporelle, composée de :

• décisions (ou actions), notées At ;

• signaux d’observations, notées St ;
• signaux de récompenses, notées rt .

C’est cette série qui engendre nos données d’apprentissage.

• Description du processus stochastique à contrôler :

Question : sur quels modèles formels et sur quelles représentations de l’environnement

s’appuie un agent afin qu’un drone autonome puisse interpréter une scǹe complexe et y agir de fa¸on
rationnelle ?
52 Chapitre 5. Processus de décision markoviens

Les MDP constituent un de ces modèles, capable de décrire formellement les interactions
entre un environnement et un drone autonome. Un MDP peut représenter de nombreux problèmes
de prise de décisions séquentielles traités en apprentissage par renforcement.

• Etat d’un processus de Markov :

On rappelle que la boucle d’interactions entre un agent et son environnement produit deux signaux :
un signal de récompense et une observation.
Si l’observation contient toutes les données sur le système (composé de l’environnement et l’agent)
nécessaires et suffisantes pour décrire l’évolution future de celui-ci, alors l’observation décrit
parfaitement l’état du système et aucune autre information n’est nécessaire pour son contrôle.
Cette propriété est appelée observation complète de l’état. Un système doté d’une telle propriété est
dit totalement observable.
En fait, Un état est la totalité de l’information nécessaire et suffisante pour prédire l’évolution
future d’un système.
Question : Comment un drone passe t-il d’un état à un autre ?

On note bien que rien dans la définition d’un processus de Markov ne permet de commander un
drone. En effet, on peut tout au plus suivre l’évolution de celui-ci au travers des états dans les-
quels il passera. Le contrôle d’un processus de Markov requiert l’introduction de la notion d’actions.

• Actions d’un MDP :

Jusqu’ici, on a défini une chine de Markov comme un modèle capable de décrire la dynamique
d’un système non contrôlé. Pour permettre la commande d’un système, on doit ajouter à une chaine
de Markov un ensemble d’actions.

On remarque bien que la fonction de transition d’un MDP contient autant de matrices de
transition qu’il y a d’actions. Cela signifie que l’état successeur St+1 = s0 dépend de l’état courant
St = s mais aussi de l’action courante At = a à travers la probabilité conditionnelle P(s, a, s0 ).

Prenons un exemple trivial afin d’illustrer un MDP. Considérons un drone déployé dans une
grille 3 × 3. Initialement, en bas à gauche de la grille, le drone souhaite se rendre en haut à
droite de celle-ci. Il dispose pour cela de 4 actions : gauche, droite, bas et haut. L’action haut
réussit avec une probabilité de 0, 8 et échoue en allant soit à gauche soit à droite avec probabilité 0, 1.

Question : Quel est la séquence d’actions qui offre la probabilité d’être en haut à droite ?

— Si les actions sont déterministes, leurs effets sont prédictibles avec certitude, alors la séquence
recherchée est celle dont le chemin, allant de la cellule en bas à gauche jusqu’à la cellule en
haut à droite, est le plus court, par exemple haut, haut, gauche, gauche.
— Si au contraire les actions sont stochastiques, leurs effets sont tirés suivant une loi de proba-
bilité ; alors la séquence haut, haut, gauche, gauche est peut-être l’une de celles recherchées.
 5.2 Problèmes décisionnels de Markov 53

F IGURE 5.1.12

5.2 Problèmes décisionnels de Markov

5.3 Politiques d’actions
Une politique ou stratégie notée π (pour contrôler un MDP) décrit la procédure suivie par l’agent
pour choisir dans chaque état (à chaque instant) l’action à exécuter. Il s’agit d’une fonction
• π : S → A dans le cas déterministe ;
• π : S × A → [0, 1] dans le cas stochastique.

• Une politique déterministe définit précisément l’action à effectuer ;

• Une politique stochastique est une famille de distributions de probabilité selon laquelle une
action a doit être sélectionnée pour chaque état (ou historique observé ht ).
54 Chapitre 5. Processus de décision markoviens

On obtient ainsi quatre familles distinctes de stratégies, comme indiqué sur le tableau :

F IGURE 5.3.1
• Une politique déterministe est notée π = {πt (st ), ∀t, ∀st } ou π = {πt (ht ), ∀t, ∀ht } ; πt (ht )
définit l’action a choisie à l’instant t si on a observé l’historique ht .
• Une politique stochastique est notée π = {πt (a, st ), ∀t, ∀st , ∀a} ou π = {πt (a, ht ), ∀t, ∀ht , ∀a} ;
où πt (a, st ) = πt (a|st ) = P(at = a|st = s) représente la probabilité de choisir l’action a à l’instant t
sachant que l’état à l’instant t est s.

Ces quatre familles de politique définissent les quatre ensembles suivants :

– ΠHS l’ensemble des politiques histoire-dépendantes stochastiques (aléatoires) cà-d l’en-

semble le plus général des politiques ;
– ΠHD l’ensemble des politiques histoire-dépendantes déterministes ;
– ΠMS l’ensemble des politiques markoviennes stochastiques (aléatoires) ;
– ΠMD l’ensemble des politiques markoviennes déterministes.

F IGURE 5.3.2
Remarque : La définition des politiques peut ou non dépendre explicitement du temps.

Définition 5.3.1 — Politique stationnaire. Une politique est stationnaire si elle ne dépend pas
du temps c-à-d si ∀t, t 0 , πt = πt 0 .

Parmi ces politiques stationnaires, les politiques markoviennes déterministes sont centrales dans
l’étude des MDP. Il s’agit du modèle le plus simple de stratégie décisionnelle, on nomme leur
 5.4 Politique markovienne et chaine de Markov valuée 55

ensemble D.
Définition 5.3.2 — Politiques markoviennes déterministes stationnaires. D est l’ensemble
des fonctions π qui à tout état de S associent une action de A :

π : s ∈ S → π(s) ∈ A

Un autre ensemble important, noté DA est constitué des politiques markoviennes aléatoires
(stochastiques) stationnaires.
Les politiques de D et DA sont très importantes car, comme on le verra, D et DA contiennent les
politiques optimales pour les principaux critères.

5.4 Politique markovienne et chaine de Markov valuée

Un MDP et une politique markovienne π forment une chaine de Markov dont la matrice de transition
est définie par

∀s, s0 Pπ (s, s0 ) = Pπ (st+1 = s0 |st = s) = ∑ π(a, s)P(s0 |s, a)

a∈A

Dans le cas où π est déterministe, Pπ (s, s0 ) = p(s0 |s, π(s)). La matrice Pπ est construite simplement
en retenant pour chaque état s la ligne correspondante dans la matrice Pπ avec a = π(s).

De même, on note Rπ le vecteur de composantes R(s, π(s)) pour π markovienne détermi-

niste et ∑ π(a, s)R(s, a) pour π markovienne stochastique.
a∈A
Le triplet (S, Pπ , Rπ ) est appelé un processus de Markov valué, ou chaine de Markov va-
luée. Il s’agit simplement d’une chaine de Markov avec des revenus associés aux transitions.

Exemple : Imaginons un sujet qui, pendant l’hiver, souhaite décider chaque jour de prendre ou
non un médicament pour lutter contre le rhume. On considère un horizon de temps infini (T = N).
L’état du sujet, chaque matin, est soit malade (1) soit en bonne santé (0) : S = {0, 1}. Et il peut
choisir de prendre un traitement (1) ou non (0) : A = {0, 1}.
On suppose que l’état du sujet au jour j + 1 dépend uniquement de l’état du sujet le jour j et du fait
qu’il ait pris ou non un traitement le jour j.
L’évolution de la maladie est aléatoire et le traitement n’est pas systématiquement efficace. On
suppose que la fonction de transition est connue et donnée par la matrice :

F IGURE 5.4.1
Chaque jour, le sujet obtient une récompense réelle modélisant son niveau de satisfaction de son
état de santé, et prenant en compte le coût du traitement :
 56 Chapitre 5. Processus de décision markoviens

F IGURE 5.4.2
une politique markovienne stationnaire déterministe possible est de choisir de prendre le traitement
uniquement si on est malade : ∀t ∈ T , πt (st ) = 0 si st = 0, πt (st ) = 1 si st = 1.
L’état de santé suit alors une chaine de Markov de matrice de transition :

F IGURE 5.4.3

5.5 Critères de performance

Se poser un problème décisionnel de Markov, c’est rechercher parmi une famille de politiques
celles qui optimisent un critère de performance donné pour le processus décisionnel markovien
considéré. Ce critère a pour ambition de caractériser les politiques qui permettront de générer des
séquences de récompenses les plus importantes possibles.

En termes formels, cela revient toujours à évaluer une politique sur la base d’une mesure
du cumul espéré des récompenses instantanées le long d’une trajectoire, comme on peut le voir sur
les critères les plus étudiés au sein de la théorie des MDP, qui sont respectivement :
• le crière fini : E(R0 + R1 + R2 + · · · + RN−1 |s0 )
• le critère γ-pondéré : E(R0 + γR1 + γ 2 R2 · · · + γ t Rt |s0 )
• le critère total : E(R0 + R1 + R2 + · · · + Rt + . . . |s0 )
• le critère moyen : lim 1n E(R0 + R1 + R2 + · · · + Rn−1 |s0 ).
n→∞

Les deux caractéristiques communes à ces 4 critères sont en effet d’une part leur formule additive
en Rt , qui est une manière simple de résumer l’ensemble des récompenses reçues le long d’une
trajectoire et, d’autre part, l’espérance E(.) qui est retenue pour résumer la distribution des
récompenses pouvant être reçues le long des trajectoires, pour une même politique et un même état
de départ.

Ce choix d’un cumul espéré est bien sûr important, car il permet d’établir le principe
d’optimalité de Bellman (" les sous-politiques de la politique optimale sont des sous-politiques
optimales "), à la base des nombreux algorithmes de programmation dynamique permettant de
résoudre efficacement les MDP.

On va maintenant caractériser successivement les politiques optimales et présenter les

algorithmes permettant d’obtenir ces politiques optimales pour chacun des critères précédents.
 5.6 Fonctions de valeur 57

5.6 Fonctions de valeur

Les 4 critères qu’on viens de voir permettent de définir une fonction de valeur qui, pour une
politique π fixée, associe à tout état initial s ∈ S la valeur du critère considéré en suivant π à partir
de s : pour π fixée, V π : S → R.

On note V l’espace des fonctions de S dans R, identifiable à l’espace vectoriel R|S| . L’en-
semble V est muni d’un ordre partiel naturel :

∀U, V ∈ V U ≤ V ⇔ ∀s ∈ S U(s) ≤ V (s)

L’objectif d’un problème décisionnel de Markov est alors de caractériser et de rechercher – si elles
existent – les politiques optimales π ∗ ∈ ΠHS telles que
∗
∀π ∈ ΠHS ∀s ∈ S V π (s) ≤ V π (s)

c-à-d

π ∗ ∈ argmaxπ∈ΠHS V π
∗
On note V ∗ = maxπ∈ΠHS V π = V π . Dans le cadre des MDP, on recherche donc des politiques
optimales meilleures que toute autre politique, quel que soit l’état de départ. Remarquons que
l’existence d’une telle politique optimale n’est pas en soi évidente.

La spécificité des problèmes décisionnels de Markov est alors de pouvoir être traduits en
terme d’équations d’optimalité portant sur les fonctions de valeur, dont la résolution est de
complexité moindre que le parcours exhaustif de l’espace global des politiques de ΠHS (la taille du
simple ensemble D est déjà de |A||S| ).

5.6.1 1- cas du crière fini

On suppose ici que l’agent doit contrôler le système en N étapes, avec N fini. Le critère fini conduit
naturellement à définir la fonction de valeur (à horizon fini) qui associe à tout état s l’espérance de
la somme des N prochaines récompenses obtenues en suivant la politique π à partir de s :

Définition 5.6.1 — Fonction de valeur pour le critère fini. Si T = {0, 1, . . . , N − 1}, on pose

 N−1 
∀s ∈ S VNπ (s) = E π ∑ Rt (st , at )|s0 = s
t=0

Dans cette définition, E π (.) dénote l’espérance mathématique sur l’ensemble des réalisations du
MDP en suivant la politique π. E π est associée à la distribution de probabilité Pπ sur l’ensemble de
ces réalisations.

Notons qu’il est parfois utile d’ajouter au critère une récompense terminale rN fonction
du seul état final sN . Il suffit pour cela de considérer une étape artificielle supplémentaire où ∀st , at ,
RN (st , at ) = RN (sN ) (récompense terminele). C’est le cas par exemple lorsqu’il s’agit de piloter un
système vers un état but en N étapes et à moindre coût.

5.6.2 2- cas du crière moyen

Lorsque la fréquence des décisions est importante, avec un facteur d’actualisation proche de 1,
ou lorsqu’il n’est pas possible de donner une valeur économique aux récompenses, on préfère
 58 Chapitre 5. Processus de décision markoviens

considérer un critère qui représente la moyenne des récompenses le long d’une trajectoire et non
plus leur somme pondérée. On associe ainsi à une politique l’espérance du gain moyen par étape.
On définit alors le gain moyen ρ π (s) associé à une politique particulière π et à un état s :
Définition 5.6.2 Le gain moyen est

 1 n−1 
∀s ∈ S ρ π (s) = lim E π R (s , a
∑ t t t 0 )|s = s
n→∞ n t=0
∗
Pour le critère moyen, une politique π ∗ est dite gain-optimale si ρ π (s) ≥ ρ π (s) pour toute politique
π et tout état s.
Ce critère est particulièrement utilisé dans des applications de type gestion de file d’attente, de
réseau de communication, de stock etc.

5.7 Politiques markoviennes

5.7.1 Equivalence des politiques histoire-dépendantes et markoviennes
En voici une propriété fondamentale des MDP pour ces différents critères, qui est d’accepter
comme politiques optimales des politiques simplement markoviennes, sans qu’il soit nécessaire de
considérer l’espace total ΠHA des politiques histoire-dépendantes.

Proposition 5.7.1 Soit π ∈ ΠHS une politique aléatoire histoire-dépendante. Pour chaque état
initial x ∈ S, il existe alors une politique stochastique markovienne π 0 ∈ ΠMS telle que
0
1. VNπ (x) = VNπ (x),
0 0
2. Vγπ (x) = Vγπ (x),
0
3. V π (x) = V π (x),
0
4. ρ π (x) = ρ π (x).

Ce résultat permet d’affirmer que lorsque l’on connaît l’état initial (ou une distribution de probabilité
sur l’état initial), toute politique histoire-dépendante aléatoire peut être remplacée par une politique
markovienne aléatoire ayant la même fonction de valeur.

5.8 Caractérisation des politiques optimales

5.8.1 Cas du critère fini
Equations d’optimalité :
Supposons que l’agent se trouve dans l’état s lors de la dernière étape de décision, confronté au
choix de la meilleure action à exécuter. Il est clair que la meilleure décision à prendre est celle qui
maximise la récompense instantanée à venir, qui viendra s’ajouter à celles qu’il a déjà percues. On
a ainsi :
∗
πN−1 (s) ∈ argmaxa∈A RN−1 (s, a),

et

V1∗ (s) = max RN−1 (s, a),

a∈A

∗
où πN−1 est la politique optimale à suivre à l’étape N − 1 et V1∗ la fonction de valeur optimale pour
un horizon de longueur 1, obtenue en suivant cette politique optimale.
5.8 Caractérisation des politiques optimales 59

Supposons maintenant l’agent dans l’état s à l’étape N − 2. Le choix d’une action a va

lui rapporter de façon sûre la récompense RN−2 (s, a) et l’aménera de manière aléatoire vers
un nouvel état s0 à l’étape N − 1. Là, il sait qu’en suivant la politique optimale πN−1
∗ , il pourra
∗
récupérer une récompense moyenne V1 (s ). 0

Le choix d’une action a à l’étape N − 2 conduit donc au mieux en moyenne à la somme de

récompenses RN−2 (s, a) + ∑s0 pN−2 (s0 |s, a)V1∗ (s0 ).
Ainsi, le problème de l’agent à l’étape N − 2 se ramène simplement à rechercher l’action qui
maximise cette somme, soit :

∗
πN−2 (s) ∈ argmaxa∈A {RN−2 (s, a) + ∑ pN−2 (s0 |s, a)V1∗ (s0 )
s0

et

V2∗ (s) = max {RN−2 (s, a) + ∑ pN−2 (s0 |s, a)V1∗ (s0 ).
a∈A
s0

Ce raisonnement peut s’étendre jusqu’à la première étape de décision, où l’on a donc :

π0∗ (s) ∈ argmaxa∈A {R0 (s, a) + ∑ p0 (s0 |s, a)VN−1

∗
(s0 )
s0

et

VN∗ (s) = max {R0 (s, a) + ∑ p0 (s0 |s, a)VN−1

∗
(s0 )}.
a∈A
s0

L’évaluation d’une politique à horizon fini se fait donc en partant de la fin, en résolvant des
problèmes à un pas de temps, ce qui est à la base de la programmation dynamique.

D’où le
Théorème 5.8.1 — Equations d’optimalité pour le critère fini. Soit N < ∞. Les fonctions de
valeurs optimales V ∗ = (VN∗ , . . . ,V1∗ ) sont les solutions uniques du système d’équations
∗
∀s ∈ S Vn+1 (s) = max {RN−1−n (s, a) + ∑ pN−1−n (s0 |s, a)Vn∗ (s0 )},
a∈A
s0

avec n = 0, . . . , N − 1 et V0 = 0. Les politiques optimales pour le critère fini π ∗ =

(π0∗ , π1∗ , . . . , πN−1
∗ ) sont alors déterminées par :

∀s ∈ S πt∗ (s) ∈ argmaxa∈A {Rt (s, a) + ∑ pt (s0 |s, a)VN−1−t

∗
(s0 )},
s0

pour t = 0, . . . , N − 1.

On voit donc ici dans le cadre du critère fini que les politiques optimales sont de type markovien
déterministe, mais non stationnaire (le choix de la meilleure décision à prendre dépend de l’instant t).

Evaluation d’une politique markovienne déterministe :

Soit une politique π markovienne déterministe. La même démarche permet alors de caractériser sa
fonction de valeu VNπ .
 60 Chapitre 5. Processus de décision markoviens

Théorème 5.8.2 — Caractérisation de VNπ . Soient N < ∞ et π = (π0 , π1 , . . . , πN−1 ) une po-
litique markovienne. Alors VNπ = V avec V = (VN ,VN−1 , . . . ,V1 ) sont solutions du système
d’équations linéaires

∀s ∈ S Vn+1 (s) = RN−1−n (s, πN−1−n (s)) + ∑ pN−1−n (s0 |s, πN−1−n (s))Vn (s0 ),
s0

pour n = 0, . . . , N − 1 et V0 = 0.

5.8.2 Cas du critère moyen

On se limite ici au cadre des MDP récurrents (pour toute politique markovienne déterministe,
la chaine de Markov correspondante est constituée d’une unique classe récurrente), unichaines
(chaque chaine de Markov est constituée d’une unique classe récurrente plus éventuellement
quelques états transitoires) ou multichaines (il existe au moins une politique dont la chaine de
Markov correspondante soit constituée de deux classes récurrentes irréductibles ou plus). On
suppose de plus ici que pour toute politique, la chaîne de Markov correspondante est apériodique.

Evaluation d’une politique markovienne stationnaire :

Soit π ∈ DA une politique stationnaire et (S, Pπ , Rπ ) le processus de Markov associé. Rap-

pelons que le gain moyen ou critère moyen est défini par :
1 N−1 
∀s ∈ S ρ π (s) = lim E π ∑ Rπ (st )|s0 = s
N→+∞ N t=0

Sous forme matricielle, on a

1 N−1 t
ρ π = lim ∑ Pπ Rπ .
N→+∞ N
t=0

Soit Pπ∗ = limN→+∞ N1 ∑t=0

N−1 t
Pπ la matrice limite de Pπ . On montre que Pπ∗ existe et est une matrice
stochastique pour tout S fini. De plus, Pπ∗ vérifie
Pπ∗ Pπ∗ = Pπ∗ .
Le coefficient Pπ, ∗
s, s0 peut être interprété comme la fraction de temps que le système passera dans
l’état s0 en étant parti de l’état s. Pour des MDP apériodiques, on a de plus Pπ∗ = limN→+∞ PπN et
∗
Pπ, s, s0 peut être interprété comme la probabilité à l’équilibre d’être dans l’état s0 en étant parti de s.
Enfin, pour un MDP unichaine, Pπ∗ est alors la matrice dont toutes les lignes sont identiques et
∗ 0
égales à la mesure invariante µπ de la chaine contrôlée par la politique π. Ainsi Pπ, s, s0 = µπ (s ).

De la définition précédente de ρ π , on déduit que ρ π = Pπ∗ Rπ . Pour un MDP unichaine on

établit ainsi que ρ(s) = ρ est constant pour tout s, avec
ρ = ∑ µπ (s)Rπ (s).
s∈S

Dans le cas général d’un MDP multichaine, ρ(s) est constant sur chaque classe de récurrence.

Cette première caractérisation de ρ π fait intervenir Pπ∗ qu’il n’est pas facile de calculer. Il
est toutefois possible d’obtenir autrement ρ π , en introduisant une nouvelle fonction de valeur pour
le critère moyen, dite fonction de valeur relative :
 5.9 Algorithmes de résolution des MDP 61

Définition 5.8.1 — Fonction de valeur relative pour le critère moyen.

 +∞ 
∀s ∈ S U π (s) = E π ∑ (Rt − ρ π )|s0 = s
t=0

Théorème 5.8.3 Soit (S, Pπ , Rπ ) un processus de Markov valué assicié à une politique π ∈ DA .
Alors Si ρ π et U π sont le gain moyen et la fonction de valeur relative de π, on a
1. (I − Pπ )ρ π = 0 ;
2. ρ π + (I − Pπ )U π = Rπ .

On retiendra que la fonction de valeur relative U π est l’unique solution de (I − Pπ )U = (I − Pπ∗ )Rπ
telle que Pπ∗U = 0.

Dans le cas simplifié d’un processus unichaine, la première équation se simplifie en ρ π (s) = ρ π et
la seconde peut s’écrire

∀s ∈ S U(s) + ρ = Rπ (s) + ∑ Pπ, s, s0 U(s0 ) (1)

s0 ∈S

Théorème 5.8.4 — Equations d’optimalité uniichaine. Il existe une solution ρ,U au système
d’équations définies pour tout s ∈ S :

ρ(s) = max
a∈A
∑ p(s0 |s, a)ρ(s0 ),
s0 ∈S
 
U(s) + ρ = max R(s, a) + ∑ p(s0 |s, a)U(s0 ) (2)
a∈A
s0 ∈S

On a alors ρ = ρ ∗.

5.9 Algorithmes de résolution des MDP

1. Cas du critère fini :
Le cas de l’horizon fini est assez simple. Les équations d’optimalité permettent en effet de calculer
récursivement à partir de la dernière étape les fonctions de valeur optimales V1∗ , . . . ,VN∗ selon
l’algorithme du premier théorème.

2. Cas du critère moyen :

On présente ici deux principaux algorithmes de programmation dynamique pour calculer des
politiques gain-optimales, dans le cas simplifié de MDP unichaines (toutes les politiques sont
unichaines) pour lesquels le gain moyen ρ est constant. Le test d’arrêt est ici basé sur l’emploi de
la semi-norme span sur V :

∀V ∈ V , span(V ) = max V (s) − min V (s).

s∈S s∈S

Contrairement à ||V || qui mesure l’écart de V à 0, la semi-norme span(V ) mesure l’écart de V à un

vecteur constant.

Algorithme d’itération sur les valeurs relatives :

C’est un algorithme d’itération sur les valeurs relatives U(s) = V (s) − ρ.
62 Chapitre 5. Processus de décision markoviens

Algorithme d’itération sur les valeurs relatives - Critère moyen

initialiser U0 ∈ V
choisir s∗ ∈ S
n←0
répéter
ρn+1 = maxa∈A {R(s∗ , a) + ∑s0 p(s0 |s∗ , a)Un (s0 )}
pour s ∈ S faire
Un+1 (s) = maxa∈A {R(s, a) + ∑s0 p(s0 |s, a)Un (s0 )} − ρn+1
n ← n+1
jusqu’à span(Un+1 −Un ) < ε
pour s ∈ S faire
π(s) ∈ argmaxa∈A {R(s, a) + ∑s0 p(s0 |s, a)Un (s0 )}
retourner ρn , Un , π.

Sous différentes hypothèses techniques, on peut montrer sa convergence pour ε → 0 vers

une solution (ρ ∗ ,V ∗ ) des équations d’optimalité (E) et donc vers une politique optimale π ∗ .
Algorithme modifié d’itération sur les politiques :

L’algorithme ci-dessous est un algorithme modifié d’itération sur les politiques, qui ne né-
cessite pas la résolution de l’équation (1) pour évaluer la fonction de valeur relative.

Algorithme modifé d’itération sur les politiques - Critère moyen

initialiser V0 ∈ V
f lag ← 0
n←0
répéter
pour s ∈ S faire
πn+1 (s) ∈ argmaxa∈A {R(s, a) + ∑s0 p(s0 |s, a)Vn (s0 )}
(πn+1 (s) = πn (s) si possible)
Vn0 (s) = maxa∈A {R(s, a) + ∑s0 p(s0 |s, a)Vn (s0 )}
m←0
si span(Vn0 −Vn ) < ε alors f lag ← 1
sinon
répéter
pour s ∈ S faire
Vnm+1 (s) = {R(s, πn+1 (s)) + ∑s0 p(s0 |s, a)πn+1 (s)Vnm (s0 )}
m ← m+1
jusqu’à span(Vnm+1 −Vnm ) < δ
Vn+1 ← Vnm
n ← n+1
jusqu’à f lag = 1
retourner Vn , πn+1 .

Pour δ élevé, l’algorithme est équivalent à l’itération sur les valeurs (non relative car on
ne gère pas ici explicitement le revenu moyen ρn ). Pour δ proche de 0, on retrouve une itération sur
les politiques classiques. Sous les mêmes conditions techniques précédentes, on montre que cet
algorithme converge pour tout δ vers une politique optimale pour ε → 0. Plus précisément, lorsque
l’algorithme s’arrête, on a
min(Vn0 (s) −Vn (s)) ≤ ρ πn+1 ≤ ρ ∗ ≤ max(V 0 (s) −Vn (s)),
s∈S s∈S
 5.10 Etude de cas et Application Industrielle ; cas d’un MDP 63

qui assure |ρ πn+1 − ρ ∗ | ≤ ε.

5.10 Etude de cas et Application Industrielle ; cas d’un MDP

5.10.1 Exemple de système de production

Voir fichier joint "Application indust. MDP".

- Analyse du système de décision ;

- Objectif du problème : déterminer une politique optimale relativement au côut moyen par unité de
temps ;
- Identification d’une politique déterministe optimale par résolution exhaustive ;

On rappelle que
• Les états E de la chaine peuvent être partitionnés en classes d’équivalence appelées classes
irréductibles. Si E est réduit à une seule classe, la chaîne de Markov est dite irréductible.

• Une classe d’équivalence C est dite fermée si, pour tout x, y tels que x ∈ C et {x → y},
y ∈ C. Autrement dit, ∀x ∈ C, ∀n ∈ N, ∑y∈C P(n) (x, y) = 1, c-à-d encore C est une classe dont on
ne peut pas sortir.

• Une classe fermée réduite à un point C = {x} est appelée un état absorbant. Un état x
est absorbant ssi p(x, x) = 1.

• Si deux états communiquent alors ils ont même période.

• La période d’une classe est la période de chacun de ses éléments. Une classe est dite
apériodique si sa période est 1.

Exercices corrigés.

Exercice 1. Considérons une chaine de Markov définie sur un espace E = {0, . . . , 9} formé de 10
états, dont la matrice de transition est :
 64 Chapitre 5. Processus de décision markoviens

F IGURE 5.10.1
1. Tracer son graphe.
2. Déterminer les classes de la chaine et leurs périodes.

Solution :

1.
F IGURE 5.10.2
2. On constate qu’il y a deux cycles donc les états de chacun des deux cycles communiquent. De plus,
ces deux cycles contiennent le même état 0, ce qui implique qu’ils communiquent. Il n’y a donc
qu’une seule classe ; la chaine est irréductible. Afin de déterminer la période de cette chaine de
Markov, il suffit de déterminer celle d’un de ses états ; prenons x = 0. Partant de 0 nous sommes de
nouveau en 0 au bout de 4 transitions en passant par le petit cycle et au bout de 7 transitions en
passant par le grand cycle, on a :

P(4) (0, 0) = 0.7 et P(4) (0, 0) = 0.3.

On en déduit que le PGCD est égal à 1 ; la chaine est donc apériodique. En résumé, cette chaine est
formée d’une seule classe apériodique.

Exercice 2. On reprend la chaine précédente avec un état de moins dans le second cycle.
C’est-à-dire, considérons la chaine de Markov définie sur un espace E = {0, . . . , 8} formé de 9
 5.10 Etude de cas et Application Industrielle ; cas d’un MDP 65

états, dont la matrice de transition est :

F IGURE 5.10.3

1. Tracer son graphe.

2. Déterminer les classes de la chaine et leurs périodes.

Solution :

1.
F IGURE 5.10.4
2. Comme précédemment cette chaine de Markov ne contient qu’une seule classe et est donc irréduc-
tible. étudions la période en étudiant celle du sommet 0. Partant de 0, nous sommes de nouveau en
0 au bout de 4 transitions en passant par le petit cycle et au bout de 6 transitions en passant par le
grand cycle. De plus, pour revenir en 0 on est obligé de passer par le petit ou par le grand cycle
("ou" non exclusif). Ainsi, nous avons P(n) (0, 0) > 0 ssi n = 4p + 6q pour (p, q) 6= (0, 0). Donc
pgcd{n ≥ 1|P(n) (0, 0) > 0} = pgcd{4p + 6q|(p, q) 6= (0, 0)} = pgcd{4, 6} = 2.

Ainsi la chaine est périodique de période 2.

Exercice 3. Soit la chaine de Markov à 10 états E = {0, . . . , 9} de matrice de transition :
66 Chapitre 5. Processus de décision markoviens

F IGURE 5.10.5
1. Tracer son graphe.
2. Déterminer les classes de la chaine et leurs périodes.

Solution :

1.
F IGURE 5.10.6
 5.10 Etude de cas et Application Industrielle ; cas d’un MDP 67

2. Nous constatons l’existence de 4 classes :

- la classe {0} qui est fermée et réduite à un point, et forme donc un état absorbant 0 ;
- la classe {1, 5} qui est fermée et apériodique en raison des boucles en 1 et 5 ;
- la classe {2, 3, 6, 7, 9} qui est fermée et de période 3, les 3 sous-classes étant dans l’ordre{2},
{3, 6} et {7, 9} ;
- enfin la classe {4, 8}, que nous pouvons quitter vers les classes {0} et {1, 5} et qui n’est donc pas
fermée.
Nous pouvons voir que nous quittons la classe non-fermée {4, 8} vers les classes fermées {0} et
{1, 5}. Or, nous voyons que nous quittons la classe {4, 8} de 4 ou de 8, et que nous avons toujours
deux fois plus de chance de nous retrouver en 0 que dans la classe {1, 5}. Par suite la probabilité
2 2
de se retrouver en 0 est de et en {1, 5} de .
3 3