Université Hassan II-Faculté des Sciences et Techniques

Département de Mathématiques-Laboratoire Mathématiques et Applications

Filière d’ingénieurs: Génie Mathématique et Informatique, 3ème Année
Année universitaire 2020-2021
Module: Chaı̂nes de Markov et Files d’attente
[Link] Amine

Séance du 12 Octobre 2020

Chapitre 1

Introduction: Déscription et
classification des files d’attente

2
1.1 Introduction
”Wait please” ou ”Patientez SVP” des phrases que l’on entend quotidien-
nement. Que l’on paye une facture devant un guichet ou par internet on est
obligé d’attendre son tour. Les phénomènes d’attente pour un service font
partie de la vie quotidienne
La modélisation mathématique des files d’attente est une théorie qui consiste
étudier les systèmes où des clients se présentent un serveur. Le but recherché
dans cette théorie est souvent d’évaluer l’attente subie par un client, de
comprendre comment elle se produit et aussi d’évaluer le nombre maximal
de clients qu’un système est capable de traiter par unité de temps. Le mot
client dépend du contexte. Dans un atelier le mot client peut signifier par
exemple une tâche, dans un hopital un client peut signifier un malade, dans
un réseau routier un client peut tre un véhicule, en informatique un client
peut signifier:
les trames d’un reseau local, ou les paquets d’un reseau commutation de
paquets, ou les requtes une base de données ou les tâches présentées à
l’unité centrale d’un ordinateur.
Le but de cette théorie est de construire des modèles mathématiques et de
définir des paramètres de performance d’un système de files d’attente comme:

• la taille moyenne de la file d’attente,

• le taux d’utilisation d’un serveur,

• le temps moyen d’attente d’un client

• le temps de séjour d’un client

L’objectif de ce cours est l’enseignement des techniques classiques les plus

utilisées dans la théorie des files d’attente.

3
 Figure 1.1: Schéma d’une file d’attente

Dscription et classsification des files d’attente

Toutes les files d’attente dans ce paragraphe sont caractérisées par:
I des clients qui arrivent dans un système,
I une salle d’attente,
I un ensemble de serveurs qui donnent aux clients le service demandé.
Une file d’attente est un systéme de service décrit par les objets suivants:
I Un processus d’arrivée: décrivant l’évolution aléatoire des arrivées des
clients . C’est un processus stochastique
I une salle d’attente permettant aux clients d’attendre leur tour pour accéde
à un serveur. Cette salle est caractérisée par sa taille; elle peut être finie ou
infinie
I un processus de service décrivant l’évolution aléatoire des durées des ser-
vices demandés par les clients. C’est un processus stochastique.
I le nombre de serveurs mis en place pour accomplir le service demandé par
les clients. Ce nombre peut être fini ou infini.
I une stratégie de service c’est à dire une politique d’attribution des serveurs
aux clients.

4
 Notation de Kendall
les files d’attente sont décrites par une suite de symboles:
A | B | s : d | e oú
I A décrit le processus d’arrivée
I B décrit le processus de service
I s le nombre de serveurs
I d la taille de la salle d’attente
I e la stratégie de service.

Exemples de stratégies de service

I FCFS(first come first served) signifie que les clients sont servis dans
l’ordre de leur arrivée au système. Le serveur s est attribué au client jusqu’à
la fin de son service. si s = 1 (un seul serveur) cette stratégie est appelé
FIFO( first in first out). En effet avec un seul serveur (unique) sous la
stratégie FCFS, les cliens sortent de la file dans le même ordre qu’ils sont
entrés. En français F CF S = P AP S(premier arrivé premier servi). Ce
terme moins utilisé que FCFS.
I LCFS(last come first served). En français LCF S = DAP S (dernier
arrivée, premier servi).Si s = 1 alors LCF S = LIF O( last in first out). Il
existe deux types de stratégies LIFO: la LIFO préemptive et la LIFO non
préemptive
Dans les deux stratégies, dans une file à n clients, si un client arrive à la
file trouve n clients, il déplace le client i à la place i + 1 et cela pour tout
1 < i < n − 1. Les deux stratégies se différencient par la place prise par le
client qui arrive:
∗ dans le cas non préemptif, il prend la place 2
∗ dans le cas préemptif, il prend la place 1 et déplace le client en service à
la place 2.
Deux possibilité se présentent alors:
• soit le travail déjà effectué sur le client 1 est perdu, on a alors une stratégie
préemptive ”non resume”
• soit le travail n’est pas perdu et le service continuera là où il est resté
quand le client accèdera de nouveau au serveur. On a alors une stratégie
préemptive ”resume”
I SIRO (service in random order) est une stratégie dans laquelle le serveur
est attribué par un tirage aléatoire sur l’ensemble des clients.
I SJF( shoted job first) est une politique dans laquelle le serveur est
attribué au client qui demande la plus petite quantité de travail. Quand un
client arrivant à la file fait une demande de service dont la durée est plus
courte que le temps résiduel service du client en service, soit il prend la
place 1 c’est le cas d’une stratégie préemptive ou il prend la place 2 dans le

5
cas d’une stratégie non préemptive; comme dans le LIFO
IPS( processor sharing) est une politique dans laquelle tous les client ssont
servis en même [Link] la capacité du serveur est C unités de travail par
unité de temps et s’il y’a n clients dans la file à un instant donné t, chaque
client est servi à un taux Cn unitè de travail par unité de temps.

Remarque 1.1.1. Dans la notation de Kendall, si la taille de la salle

d’attente n’est pas explicitée cela signifie qu’elle est infinie et quand la
stratégie e n’est spécifiée cela signifie qu’elle est FCFS.

Définition 1.1.1. On appelle temps de séjour d’un client dans une file
d’attente, le temps entre son instant d’arrivée et son instant de départ de la
file:

tattente = tséjour−tservice

6
 Figure 1.2: Temps de séjour: FIFO

Figure 1.3: Temps de séjour: LIFO( cas non préemptif)

Remarque 1.1.2. Il est très important d’observer le temps d’attente d’un

client quand la stratégie de service est telle que le service d’un client peut
être arrêté comme dans LIFO.

7
1.2 Motivations
Dans ce § on va introduire certaines applications de la théorie des files
d’attente à l’èvaluation de performances et au dimensionnement des réseaux
de télécommunications.

1.2.1 Les réseaux de paquets

Un réseau de paquets est un ensemble de napplés commutateurs et des liens
qui interconnectent les nœuds. Chaque équipement terminal est connecté à
un nœud du réseau appelé nœud d’accès du terminal.
Files d’attente du réseau:
? clients = paquetsdedonnées
? le temps de service d’un paquet est le necessaire à sa transmission
Ce temps est égal au rapport entre la longueur (en bits) du paquet et la
capacité( en bits) du lien. La capacité d’un lien n’est pas aléatoire.
Si le réseau utilise des paquets de taille constante alors le temps de service
sera modélisé par une variable déterministe.
Si les paquets sont de taille variable, un temps de service aléatoire sera
mieux adapté.
Le nombre de serveur est égal à 1 puisque la fille d’attente représente la
taille du buffer en nombre de paquets.
En général la stratégie de service utilisée est FIFO
Le modèle de files d’attente peut être aussi utilisé pour estimer les perfor-
mances d’un réseau existant ou pour estimer quelle est la charge maximale
que ce réseau peut admettre.

1.2.2 Les réseaux téléphoniques

Les modèles de files d’attente utilisés A|B|m : m seront utilisés pour
optimiser l’utilsation d’un réseau.

1.2.3 Les réseaux locaux à jeton

Un réseau local à jeton est un réseau dans lequel toutes les stations sont
connectées à un même mediunm, qu’elles partagent. Afin d’éviter des conflits
d’accès au mèdium, un jeton circule entre les stations. Seule la station qui
dispose d’un jeton peut transmettre. Pour évaluer les performances de ces
réseaux on les modélise per un ensemble de files d’attente, une pour chaque

8
station. Il y’a un seul serveur. Ce type de modèle est appelé un système de
polling.

1.3 Les files d’attente M/M/·

Dans ces files le processus d’arrivée est poissonien et celui du service
est exponentiel. Ces modéles sont utilisés pour modéliser et évaluer les
performances des systémes de télécommunication.

M/M/1 est souvent utilisé pour modéliser les liens des réseaux à
commutation de paquets. Nous verrons ultérieurement des paramétres de
performation importants pour un ingénieur réseau.

M/ M/s: ∞ un modéle de file d’attente avec s serveurs et une salle

d’attente infinie.

M/M/0 : ∞ cette file est importante pour le dimmensionnement

des réseaux téléphoniques commutés. Les serveurs ici sont les lignes
téléphoniques. Le temps de service modélise la duré e des appels. Un appel
pour lequel on ne trouve pas de ligne disponible est perdu: il n’y’a pas de
salle d’attente.

M/M/∞ La même file d’attente que ci dessus avec un nombre infini de

lignes.

M/M/1 : K files d’attente à un serveur et une salle d’attente de taille K.

9
Chapitre 2

Chaı̂nes de Markov à temps

discret

10
2.1 Chaı̂nes de Markov, définitions et pro-
priétés
Dans tout ce quit suit (Ω, A, P) désigne un espace de probabilité et X =
{Xn , n ∈ N} des variables aléatoires(v.a) définis sur Ω à valeurs dans un
espace de probabilité dénombrable E qui est appelé l’espace d’états du pro-
cessus X.

Définition 2.1.1. X est une chaı̂ne de Markov si et seulement si:


P(Xn+1 = jn+1 |Xn = jn , Xn−1 = jn−1 , . . . , X0 = j0 ) = P(Xn+1 = jn+1 |Xn = jn )
∀n ∈ N, ∀j0 , j1 , . . . , jn+1 ∈ E
(2.1)

La propriété (2.1) est appelée la propriété markovienne.

Remarque 2.1.1. Cette propiété markovienne signifie que l’état du pro-

cessus à la date n + 1 sachant ses ètats au présent (date n) et au passé
n − 1,n − 2, . . . , 0 ne dépend que de son état au présent càd à la date n.

Définition 2.1.2. X est une chaı̂ne de Markov homogène si elle est une
chaı̂ne de Markov et de plus:
P(Xn+1 = j|Xn = i) ne dépend pas de n ,∀i, j ∈ E

Dans tout ce chapitre, on travaillera avec des chaı̂nes de Markov

homogènes.

Notation: On note p(i, j) = P(Xn+1 = j|Xn = i) = pi,j

Définition 2.1.3. La matrice P = (pi,j )(i,j)∈E 2 est appelée la matrice de

transition de X.

 P possède la proprièté suivante:

pi,j ≥ 0,
P ∀(i, j) ∈ E 2 ,
j∈E pi,j = 1 ∀i ∈ E

11
Exemple 2.1.1. Lors d’une ronde, une méthode simple pour tromper
l’ennemi est d’avancer ou reculer de manière aléatoire, en tirant à Pile ou
Face une pièce de monnaie. Si Xn désigne la position du garde à l’instant
n, l’évolution peut se modéliser à l’aide d’une matrice de transition:

1 1
 
0 2
0 2
 1 0 1 0 
 2 1 2 1 
 0 0 2 
2
1
2
0 12 0

Exemple 2.1.2. Dans une assurance, il existe 6 classes de tarification de

1(fort bonus) à 6 fort malus.
• Si un assuré n’a pas eu de sinistre, il passe de i à max(1, i − 1)
• si l’assuré a eu au moins un sinistre, il passe de i à 6

Si p désigne la probabilité de ne pas avoir de sinistre; Xn désigne la v.a

déterminant la classe de l’assuré à la date n
P(Xn+1 = 1|Xn = 1) = p11 = p
P(Xn+1 = 2|Xn = 2) = P(∅) = 0
P(Xn+1 = 6|Xn = 6) = 1 − p
P(Xn+1 = 2|Xn = 1) = P(∅) = 0

D’où la matrice de transition

 
p 0 0 0 0 1−p
 p
 0 0 0 0 1−p  
 0
 p 0 0 0 1−p  
 0
 0 p 0 0 1−p  
 0 0 0 p 0 1−p 
0 0 0 0 p 1−p

12
 Exercice
Déterminer la matrice de transition si la compagnie change le barème de
tarification comme suit:
• si un assuré n’a pas fait de sinistre, il passe de i à M ax(1, i − 1)
• si l’assuré a k sinistres, il passe de i à M in(6, i + k)
et si de plus on sait que le nombre de sinistres suit une loi de Poisson.

Exemple 2.1.3. : La ruine du joueur

Deux joueurs jouent à plie ou face, chaque fois que X gagne, il touche 1dh
de Y et réciproquement. Ils partent respectivement d’un capital a et b et
le jeu s’arrête lorsqu’un joueur n’a plus d’argent pour payer. La fortune
d’un joueur prend les valeurs suivantes: {0, 1, 2, . . . , a + b}. Si le joueur X
possède une fortune Xn = k à la date n, à la date n + 1:
• sa fortune devient k − 1 avec une probabilité p et k + 1 avec la probabilité
1 − p pour tout 0 < k < a + b
• sa fortune reste 0 avec 1 si k = 0
• sa fortune reste a + b avec une probabilité 1 si k = a + b
(Xn )n∈N est une chaı̂ne de Markov dont l’ensemble des états est
E = {0, 1, ·, ·, a + b} et de matrice de transition P :
 
1 0 0 0 0 0 0
 p 0 1−p 0 0 0 0 
 
 · · · · · · 0 
P =  · ·

 · · · · 0  
 · · · · · · · 
0 · · · · 0 1

13
Séance du 19 Octobre 2020:( Suite du Chapitre2)

14
Exemple 2.1.4. Les processus de file d’attente
Soit une file d’attente à temps discret: le temps est divisé en intervalles
de longueur constante et on observe le système uniquement aux frontières
de ces intervalles. Pour simplifier les notations, on utilise comme unité de
temps, la longueur de ces intervalles. On suppose que la salle d’attente est
infinie, qu’il y’a un seul serveur et que la discipline de service est FCFS
(first come first served). Les clients arrivent et sortent du sytème à la fin
de chaque intervalle. On suppose que les départs se produisent avant les
arrivées afin d’éviter les temps de service nuls.
Le processus d’arrivée est défini comme suit:
à chaque intervalle, il y’a une arrivée avec une probabilité p et aucune
arrivée avec une probabilité 1 − p et ceci independemment de tout le passé
du processus.
Le processus de service est comme suit:
si à la fin d’un intervalle, il y’a un client dans la file, celui-ci finit son
service avec probabilité q et ne le finit pas avec une probabilité 1 − q et
ceci independemment du passé du processus. De plus, on suppose que les
processud’arrivée et de service sont indépendants.

Remarque 2.1.2. La probabilité d’avoir plus d’une arrivée ou plus d’un

départ dans le nême intervalle est égale 0

Le processus d’arrivée est un processus de renouvellement de loi

géométrique de paramètre p
La suite des temde service est un processus de renouvellement de loi
géométrique de paramètre q.

15
 Soit

1, s’il y’a une arrivée au nème intervalle, avec une probabilité p
An =
0, sinon, avec une probabilté 1 − p

Soit

1, s’il y’a un départ au nème intervalle, avec une probabilité q
Dn =
0, sinon, avec une probabilté 1 − q

Xn la v.a qui indique le nombre de clients dans la file à la fin du nème

intervalle. La valeur de Xn est appelée ètat de la file à l’instant n. Le
processus (Xn )n∈N décrit donc l’évolution de l’état de la file. La figure
suivante:

montre la convention qu’on va utiliser pour l’ordonnancement des in-

stants de dèpart, d’arriv’ée et d’observation de l’état de la file à chaque
intervalle de temps.D’après cette convention, l’état évolue selon l’équation
suivante:
Xn+1 = (Xn − Dn+1 )+ + An+1 où a+ = max(0, a)
On voit que Xn+1 dépend de (Xj )nj=0 uniquement à travers Xn càd (Xn )
vérifie la proprièté de Markov.
On va chercher la loi de Xn .

16
 On a:
∞
X
P(Xn+1 = i) = P(Xn+1 = i, Xn = j)
j=0
∞
X
= P(Xn+1 = i|Xn = j)P(Xn = j), ∀n ≥ 0
j=0

La matrice de transition de cette chaı̂ne pour èlèments (pij ) de la forme:



 0 si i > j + 1
(1 − q)p si i = j + 1, j > 0




 p si i = j, j > 0


P(Xn+1 = i|Xn = j) = pq + (1 − p)(1 − q) si i = j, j > 0
 1−p si i = j = 0



q(1 − p) si i = j − 1, j > 0




0 si i < j − 1.


P(Xn+1 = i) = (p − q)pP(Xn = i − 1) + [pq + (1 − p)(1 − q)]P(Xn = i)

+q(1 − p)P(Xn = i + 1), i > 1
P(Xn+1 = 1) = pP(Xn = 0) + [pq + (1 − p)((1 − q)]P(Xn = 1)
+q(1 − p)P(Xn = 2)
P(Xn = 0) = (1 − p)P(Xn = 0) + q(1 − p)P(Xn = 1)

Si on suppose que limn→∞ P(Xn = i) existe et égale à pi on a:


 pi = (1 − p)ppi−1 + [qp + (1 − p)(1 − q)]pi + q(1 − p)pi+1
(S) = p1 = pp0 + [qp + (1 − p)(1 − q)]p1 + q(1 − p)p2
p0 = (1 − p)p0 + q(1 − p)p1


limn→∞ P(Xn = i) si elle existe, décrira la distribution stationnaire du

nombre de clients dans la file et nous permet de calculer par exemple, le
nombre moyen de clients dans la file. Ce qui est un paramètre très utile au
dimensionnement des tailles des files nècessaires(dans la pratique les files
sont finies...)
Le système (S) précédent admet une solution unique dans le cas où p < q.

17
Cette solution est (pi )∞
i=0 donnée par:

p0 p(1 − q) i
pi = [ ] , sii >
1 − q q(1 − p)
p
p0 = P(X = 0) = 1 − .
q

Dans le cas p ≥ q, il n’y a pas de solution.

En régime stationnaire (càd pi existe) le nombre moyen de clients dans la
file est: P
E(X) = ∞ p(1−p)
i=0 iP(X = i) = q−p

Remarque 2.1.3. On verra plutard qu’à partir du nombre moyen de clients

dans la file, on peut déduire le temps moyen de séjour d’un client dans la file
ainsi que d’autres paramètres de performance.

18
Exemple 2.1.5. Une suite indépendante de v.a identiquement distribuées
et indépendantes est souvent notée i.i.d
Soi (Xn ) une suite de v.a i.i.d à valeurs dans N, telle que P(Xn = k) = ak
∀n ∈ N, alors Xn est une chaı̂ne de Markov de matrice de transition:
 
a0 a1 a2 · · ·
 a0 a1 a2 · · · 
 
 a0 a1 a2 · · · 
P =  
 · · · · · · 

 · · · · · · 
· · · · · ·

19
Exemple 2.1.6. Somme partielle d’une i.i.d Pn
Soit (Xn )n une suite i.i.d à valeurs dans N. Soit Yn = i=0 Xn , alors
Yn+1 = Yn + Xn+1 . (Yn )n est une chaı̂ne de Markov. En effet Xn+1
est indépendant de {Yi , i ≤ n}. De plus la matrice de transition a pour
coefficient:

pij = P(Yn+1 = j|Yn = i) = P(Xn+1 = j − i) = aj−i , sij ≥ i

 
a0 a1 a2 · · ·
 0 a0 a1 · · · 
 
 0 0 a0 a1 · · 
P =  0 0 0 a0 ·


 
 · · · · · · 
· · · · · ·

20
Exemple 2.1.7. Marche aléatoire

Définition 2.1.4. Une marche aléatoire sur Z est une chaı̂ne de Markov à
valeurs dans Z tel que P (Xn+1 = i + 1|Xn = i) = p et P (Xn+1 = i − 1|Xn =
i) = 1 − p.

Xn peut modéliser la richesse d’un joueur à Pile ou Face, gagnant 1Dh

dès que Pile sort avec une probabilité p et perd 1 Dh dans le cas contraire
au bout de n tirages.
On a une définition plus générale d’une marche aléatoire sur Zd , d > 1.
Plus généralement on a:

Proposition 2.1.1. Une suite réccurente de v.a Xn+1 = f (Xn , Un+1 ) avec
(Un ) une suite de v.a i.i.d à valeurs dans F et indépendantes de X0 , et
f : E × F ,→E une fonction mesurable, est une chaı̂ne de Markov homogène
dans E.

Demonstration 2.1.1. A faire T.D

Proposition 2.1.2. Réciproquement, si (Xn ) est une chaı̂ne de Markov ho-

mogène èà valeurs dans E, de matrice de transition P , alors il existe une
suite i.i.d (Un ) à valeurs dans F et indépendantes de X0 telle que:

Xn+1 = f (Xn , Un+1 )

où

f (x, y) = Inf {u, P(x, ] − ∞, u] > y}

Demonstration 2.1.2. A faire T.D

21
Définition 2.1.5. On appelle matrice markovienne(ou stochastique) toute
matrice
 M (aij ) tels que:
aij ≥ O, P ∀ i,j
∀i, j aij = 1

Remarque 2.1.4. La matrice de transition d’une chaı̂ne de Markov ho-

mogène est une matrice markovienne.

Proposition 2.1.3. Soient A, B et C trois évenements quelconque alors on

a:
P(A ∩ B|C) = P(A|B ∩ C)P(B|C)

Proposition 2.1.4. Soit (Xn ) une chaı̂ne de Markov alors on a:

P[Xn+m = in+m , · · · , Xn+1 = in+1 , Xn−1 = in−1 , · · · , X0 = i0 |Xn = in ]

= P[Xn+m = in+m , · · · , Xn+1 = in+1 |Xn = in ]P[Xn−1 = in−1 , · · · , X0 = i0 |Xn = in ]

c’est àdire que conditionnellement au présent, le futur et le passé d’une

chaı̂ne de Markov sont indépendants.

Demonstration 2.1.3. Appliquer la proprosition précédente.

22
Proposition 2.1.5. La loi jointe de (X0 , . . . , Xn ) est déterminée pour tout
n, à partir de la loi initiale de X0 et de la matrice de transition P par la
formule suivante:

P(X0 = i0 , . . . , Xn = in ) = P(X0 = i0 )pi0 i1 . . . , pin−1 in

∀i0 , i1 , . . . , in ∈ E

Demonstration 2.1.4. On a

P(X0 = i0 , . . . , Xn = in ) = P(Xn = in |X0 = i0 , . . . , Xn−1 = in−1 )

×P(Xn−1 = in−1 |X0 = i0 , . . . , Xn−2 = in−2 )
× . . . P(X1 = i1 |X0 = i0 )P(X0 = i0 )

D’où le résultat grâce à la proprièté markovienne de la chaı̂ne.

Définition 2.1.6. La loi de X0 est appelée la loi initiale de la chaı̂ne.

On admet que si µ est une loi de probabilité sur E et P une matrice

markovienne alors il existe une et une seule chaı̂ne de Markov homogène qui
a µ comme loi initiale et P comme matrice de transition.

Remarque 2.1.5. Dans le cas particulier où le point initial de la chaı̂ne

de Markov est p.s connue càd P(X0 = i) = 1 pour tout i ∈ E, on dit que
la loi initiale de la chaı̂ne est δi . On note Pi la probabilité associée à δi :
Pi (A) = P(A|X0 = i)

Notation Pµ sera la loi d’une chaı̂ne de Markov de loi initiale µ

Proposition 2.1.6. ∀n ∈ N, ∀i0 , · · · in ∈ E et ∀i, j ∈ Eon a:

P(Xn = in , · · · , X1 = i1 |X0 = i0 ) = pin−1 ,in pin−2 ,in−1 · · · pi0 ,i1 , (2.2)

n
P(Xn = in |X0 = i0 ) = (P )i0 ,in (2.3)
X
P(Xn+m = j|X0 = i) = P(Xn+m = j|Xm = k)P(Xm = k|X0 (2.4)
= i)
k∈E

P(Xn = in |X0 = i0 ) est la probabilité de passer de l’état initial à l’état in

en n étapes. P n est la puissance nème de P.

23
Demonstration 2.1.5. On a d’après la proptièté precédente:
P(Xn = in , · · · , X1 = i1 , X0 = i0 ) = P(X0 = i0 )pin−1 ,in pin−2 ,in−1 · · · pi0 ,i1 ,
d’où P(Xn = in , · · · , X1 = i1 |X0 = i0 ) = pin−1 ,in pin−2 ,in−1 · · · pi0 ,i1 .
D’où (2.2)
D’apès la formule de probabilité
P totale on a;
P
P(Xn = in |X0 = i0 ) = i1 ∈E · · · in−1 ∈E P(Xn = in , · · · , X1 = i1 |X0 = i0 )
Or d’après (i) on a P P
P(Xn = in |X0 = i0 ) = i1 ∈E · · · in−1 ∈E pin−1 in · · · pi0 i1
(P n )i0 in étant l’élément (iP
0 , in ) de la puissance n
ème
de P.
n
P
Or (P )i0 in == i1 ∈E · · · in−1 ∈E pi0 i1 · · · pin−1 in , d’où (ii) et on obtient (2.3)

D’après (2.3) on a:
m
X
(P n P m )i0 in+m = (P n )k,in+m (P )i0 k ,
k∈E

d’où (2.4).

24
 Equation de Chapman-Kolmogorov:
L’équation (2.4) est appelée l’équation de Chapman-Kolmogorov:
X
P(Xn+m = in+m |X0 = i0 ) = P(Xn+m = in+m |Xm = k)P(Xm = k|X0 = i0 )
k∈E

Pijn = (P n )ij = P(Xn = j|X0 = i)

est la probabilité de passer de l’état i à l’état j en n pas.

25
Remarque 2.1.6. A toute matrice de transition on peut associer un graphe
orienté. Les sommets sont les ètats de la chaı̂ne et l’orientation est donnée
par la probabilité pij > 0

Exemple 2.1.8. 0 < α < 1 et 0 < β < 1 la matrice:

 
1−α α
P =
β 1−β

est markovienne. Elle est représentée par le graphe suivant:

26
Exemple 2.1.9.
1 1
 
2 2
0
2 1
P = 3
0 3

2 1
0 3 3

est une matrice markovienne dont le graphe est:

p22 = 0 n’est pas représenté dans le graphe.

Exercice
Dans chacun des cas suivants, vérifier que la matrice P est markovienne et
représenter son graphe:
1)  1 1 
2 2
0
P =  23 0 13 
0 0 1

2)
1 1 3
 
5 5 5
1 1
P = 0 
2 2
1 0 0
Exemple 2.1.10. Pour
 
1−α α
P =
β 1−β

on a  
2 (1 − α)2 + αβ 1 − [(1 − α)2 + αβ]
P =
1 − [(1 − β)2 + αβ] (1 − β)2 + αβ

Par reccurence on montre que:

(n+1) (n) (n+1) (n) (n+1)
p11 = (1 − α)p11 + βp12 = (1 − α)p11 + β[1 − p11 ]

(n+1) (n+1)
p12 = 1 − p11 .

D’où:
(n+1) (n)
p11 = (1 − α − β)p11 + β

27
 (0)
Cette suite reccurente avec p11 = 1 admet une solution unique:

(n) β β
p11 = + [1 − α − β]n
α+β α+β
Ceci se traduit par le graphe suivant:

28
Séance du 26 Octobre 2020:( Suite du Chapitre2)

29
2.2 La proprièté de Markov forte
SoitX = (Xn ) une chaı̂ne de Markov sur Ω à valeurs E on désigne par Fn =
σ(Xm , m ≤ n) la tribue engendrée par (Xm , m ≤ n). (Fm )m≤n représente
l’histoire de X et Fn représente le passéde X jusqu’à l’instant n.
Définition 2.2.1. Toute v.a T à valeurs dans N telle que {T = n} ∈ Fn est
appelée un temps d’arrêt (t.a)de X
Exemple 2.2.1. Temps d’entrée dans un ensemble
Soit A ⊂ E

Inf {n ≥ 0 tq Xn ∈ A}, si ∃ n tq Xn ∈ A;
τ (A) =
∞, sinon.
τ (A) est un temps d’arrêt de X. En effet,
n−1
\
(τ = n) = (Xk ∈
/ A) ∩ (Xn ∈ A) ∈ Fn .
k=1

Proposition 2.2.1. Soit X une chaı̂ne de Markov et T un t.a alors pour

tout n ≥ 0 il existe une fonction (hn ) telle que:

P(T = n|Xm = im , m ≥ 0) = hn (i0 , . . . , in )

pour tout i0 , . . . , in ∈ E
Demonstration 2.2.1. A admettre
Théorème 2.2.1. Proprièté de Markov Forte
Soit T un temps d’arrêt presque sûrement fini d’une chaı̂ne de Markov X,
alors

P(XT +m = j|XT = i, XT −1 = iT −1 , · · · , X0 = i0 ) = pm
ij

∀i, j, i0 , i1 , · · · , iT −1 ∈ E et ∀m ≥ 1.
Cette proprièté est appelée la proprièté de Markov forte.

Intéprétation Soit TX = {XT +m , m ∈ N}

La proprièté de Markov forte signifie que l’évolution de TX conditionnelle-
ment au passé jusqu’à T ne depend que de XT et TX est une chaı̂ne de
Markov de même matrice de transition que X.
Demonstration 2.2.2. Voir T.D

30
2.3 Classification des états
On va faire une classification des états d’une chaı̂ne de Markov afin de
montrer les évolutions possibles de l’état de cette chaı̂ne et de déterminer
des conditions necessaires et suffisantes de l’existence d’une probabilité
stationnaire.

2.3.1 Etats reccurents et états transcients

Soit le temps d’arrêt suivant:

Inf {n ≥ 1 tqXn = i}, sı∃ i tq Xn = i;
τ (i) =
∞, sinon.
τ (i) est le temps d’atteinte de l’état i

On rappelle que

1 si Xn (ω) = i;
1{Xn =i }(ω) =
0, sinon.
Soit N (i) = ∞
P
n=1 1{Xn =i} est la v.a déterminant le nombre total de visites
de l’état i après le départ.
Il est évident que:
N (i) > 0 ⇐⇒ τ (i) < ∞.

Définition 2.3.1. (1) Un état i est dit transcient si Pi (τ (i) < ∞) < 1
(2) Un état i est dit reccurent si Pi (τ (i) < ∞) = 1, c’est à dire que le temps
de retour en i est fini p.p
Il existe deux types d’états recuurents:
(a) un état reccurent nul si Ei (τ (i)) = ∞
b) un état reccurent positif( ou non nul) si Ei (τ (i)) < ∞
(3) un état i est dit absorbant si pii = 1
Une chaı̂ne de Markov est dite reccurente(resp transciente) si tous ses états
sont reccurents (resp transcients).

Remarque 2.3.1. Pi (τ (i) < ∞) = ∞

P
k=1 Pi (τ (i) = k) est souvent difficile
à calculer pour déterminer la nature d’un état, mais la proposition suivante
donne un moyen plus facile.

31
Proposition 2.3.1. Soit i un état fixé. Alors on a

1) Ei (N (i)) = ∞ n
P
n=1 pii
2) les assertions suivantes sont équivalentes:
(a) i est recurrent
(b) Pi (Ni = ∞) = 1, c’est à dire que la chaı̂ne (Xn ) revient p.s une infinité
de fois à son état initial i,
(c)Ei (N (i)) = ∞
3)les assertions suivantes sont équivalentes:
(a) i est transcient
(b) Pi (N (i) < ∞) = 1
(c) Ei (N (i)) < ∞

P
Remarque 2.3.2. Pi (Ni < ∞) = k=1 Pi (Ni = k) et Pi (Ni < ∞) = 1 pour
un état transient signifie que la chaı̂ne (Xn ) visite l’état i un nombre fini de
fois càd que la chaı̂ne a une probabilité positive de ne pas revenir à cet état.

2.3.2 Relation d’équivalence dans l’ensemble des états

Définition 2.3.2. On dit qu’un état i conduit à un état j et on le note i → j,
s’il existe m ≥ 0 tq pm
ij > 0

Par convention p0ii = 1 ∀i ∈ E donc p0ij = 0 si i 6= j.

Proposition 2.3.2. La relation → est reflexive et transitive.

Demonstration 2.3.1. p0ii = 1 pour tout i donc reflexive

Si (i → j et j → k) ⇐⇒ (∃r, s ≥ 0 tq prij > 0 et psjk >. D’après l’équation
de Chapman-Kolmogorov on a:
pr+s r s
tous les termes sont positifs donc pr+s
P
jk = p p
l∈E il lk > 0 car ik > 0, donc
i → k.

Remarque 2.3.3. La relation → n’est pas symétrique en général.

Proposition 2.3.3. (à admettre) Si i est un état reccurent et i → j alors

F (j, i) = 1 donc j → i, où F (j, i) désigne la probabilité de passer de l’état j
à l’état i en un temps fini.

Définition 2.3.3. On dit que deux états i et j communiquent et on note

i ,→ j si et seulement si i → j et j → i.

La relation ,→ est une relation d’équivalence dans E

32
Définition 2.3.4. Soit i ∈ E, on appelle d période de l’état i le

pgcd(n ≥ 1, pnii > 0)

Si d = 1 on dit que l’état est apériodique.

Théorème 2.3.1. Si i est périodique de période d et si i communique avec

j alors j est périodique et de même période que i. La périodicité est une
propritété de classe.

33
Définition
P 2.3.5. Un sous ensemble F de E est dit férmé ssi: pour tout
i∈F j∈F ij = 1
p
Cela signifie que les états de F ne conduisent pas à des états qui ne sont pas
dans F

Définition 2.3.6. Un sous ensemble F de E est dit fermé et iireductible ssi

il est fermé et ne contient pas strictement un sous ensemble fermé

Définition 2.3.7. Une chaı̂ne de Markov est dite irreductible ssi son espace
d’états est fermé irreductible. (c àd tous ses états communiquent).

Exemple 2.3.1. On considère la chaı̂ne suivante:

sa matrice de transition est

1 1
 
0 0
2 2
1 1
 0 0 
2 2
P =
 1
1

1 1
4
4 4 4
0 0 0 1
Cette chaı̂ne présente trois classes:
{1, 2}, {3} et {4} avec
{4} absorbant (p44 = 1);
{1, 2} et {4} sont reccurents et {3} transient.
{1, 2} est fermé dans E: cette chaı̂ne n’est pas iireductible.

Remarque 2.3.4. 1)une chaı̂ne est irreductible si toutes ses paires d’états
communiquent. On dit que son graphe est fortement connexe.
2) Si une chaı̂ne admet un état absorbant, elle n’est pas iireductible

34
Définition 2.3.8. La forme canonique de la matrice d’une chaı̂ne de Markov
à un 
ensembled’états fini s’écrit:
Q R
P =
0 I
où R représente les états absorbants, Q les états non absorbants , I la
matrice identité et 0 la matrice nulle.

Exemple 2.3.2. Soit la matrice de transition suivante P d’une chaı̂ne de

Markov:
 1 1 
2 2
0 0 0 0
 0 0 0 1 0 1 
 1 1 2 2 

2 2
0 0 0 0 
P =  0 0 1 0 1 0 .

 2 2 
 0 0 0 0 1 O 
0 0 0 0 0 1
L’écriture
 canonique
 de cette matrice est:
Q R
P =
0 I
AvecR=  
0 0
 0 1 
 2 
 0 0 
1
2
0

matrice
 1des1états absorbants

2 2
0 0
 0 0 0 1 
Q= 2 
 1 1 0 0 
2 2
0 0 12 0
matrice
 des  états non absorbants, et
1 0
I=
0 1

35
Proposition 2.3.4. Si E est un espace d’état fini alors toute chaı̂ne de
Markov irreductible est reccurente.

Demonstration 2.3.2. Voir T.D

Proposition 2.3.5. Si une chaı̂ne de Markov a un nombre d’états fini alors

il existe au moins un état reccurent.

Demonstration 2.3.3. Voir T.D

Exemple 2.3.3. Soit (Xn ) une chaı̂ne de Markov dont E = {0, 1, 2} est
l’espace d’états et  
0 1 0
P = p 0 1−p 
1 0 0

Par le graphe orienté on vérifie que cette chaı̂ne est irreductible. Tous ses
états communiquent, de plus les lacets:
0 → 1 → 0 et 0 → 1 → 2 → 0 ont pour longueur 2 et 3 respectivement. Leur
pgcd = 1; 0 est apériodique . D’après le théorème les états 1 et 2 le sont
aussi.

Exercice Soit E = {0, 1, 2, 3} et

0 12 12
 
0
 1 0 0 0 
P =  0
.
1 0 0 
0 1 0 0

1) La chaı̂ne est elle irreductible? Est elle reccurente?

2) Déterminer sa période.

36
Séances du 2, 9 Novembre 2020: chapitre 2 suite

37
Définition 2.3.9. (Graphe réduit d’une chaı̂ne de Markov)
Si C1 , C2 , ·, ·, ·, Cr désigne les classes d’une chaı̂ne de Markov, le graphe réduit
GR de la chaı̂ne est obtenu en associant un sommet u à chaque classe Cu et
en reliant les sommets u et v par un arc (u, v) s’il existe i ∈ Cu et j ∈ Cv
avec pi,j > 0.

Exemple 2.3.4. (sera traité en TD) Soit (Xn )n∈N une chaı̂ne de Markov
d’éspace d’états E = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} et de probabilités de transition:
p1,6 = p1,8 = 21 , p2,5 = 1, p3,3 = 12 , p3,5 = p3,7 = 14 , p4,7 = 1, p5,3 = p5,7 = 14 ,
p5,8 = 12 , p6,1 = p6,8 = 12 , p7,4 = p7,10 = 12 , p8,1 = p8,6 = 12 , p9,2 = 34 ,p9,9 = 14 et
p10,7 = 1
Ecrire la matrice de cette chaı̂ne puis représenter son graphe. Déterminer
les classes de communication , leur nature, leur périodicité.

38
2.4 Lois de probabilité stationnaire- Ergod-
icité
Définition 2.4.1. Soit ν une loi de probabilité sur l’ensemble d’états E,
elle est dite stationnaire ( ou invariante) par rapport à P ( P matrice de
transition) ssi P
ν = νP càd νj = i∈E νi pij P
où ν = (ν1 , · · · , νi , · · · ) 0 ≤ νi ≤ 1 i νi = 1 et P = (pij ).

Proposition 2.4.1. Si ν est une loi de probabilité stationnaire et si i est

un état transient alors νi = 0 En particulier, si une chaı̂ne n’a que des états
transients alors elle n’admet pas de loi stationnaire.

Demonstration 2.4.1. Soit ν une loi stationnaire et i un état

transient.∀n ∈ N, onPa
νP n = ν donc νi = j νj pnij
Or i est un état transitoire donc pnij → 0 |pnij | ≤ 1 et j νj = 1, d’après
P
le théorème de la convergence dominée, on déduit que νi = .0 Donc une
chaı̂ne qui n’a que des états transititoires ne peut avoir de loi de probabilité
stationnaire.

39
2.4.1 Chaı̂ne de Markov à espace d’états fini
Théorème 2.4.1. Soit (Xn ) une chaı̂ne de Markov à ensemble d’états fini.
Alors elle épossède au moins une loi stationnaire.
Si de plus elle est irreductible, alors la loi stationnaire est unique notée ν et
vérifie:
∀i ∈ E, ν(i) = Ei 1(τi ) > 0
où τi est le temps d’atteinte de i ( ou le premier retour en i) et
Ei (τi ) = E(τi |X0 = i). Si de plus, (Xn ) est irrecductible apériodique alors P n
converge vers la matrice dont toutes les lignes sont égales à ν;
par conséquent quelle que soit la loi initiale de X0 , Xn converge en loi vers ν

Exemple 2.4.1. Le modèle à deux états a pour matrice de transition:

 
1−α α
P =
β 1−β

La probabilité invariante (µ1 , µ2 ) vérifie:

(1 − α)µ1 + βµ2 = µ1
αµ1 + (1 − β)µ2 = µ2
µ1 + µ2 = 1
β
On obtient: µ1 = α−β et
α
µ2 = α−β
avec 0 < α < 1 et 0 < β < 1. La chaı̂ne est reccurente et apériodique.
Xn converge en loi vers µ quelque soit la loi initiale et E1 (τ1 ) = α−β
β

40
 Exercice Le modèle de diffusion d’Ehrenfest
Deux urnes A et B contiennent au total m boules numérotées de 1 à m. A
chaque instant, on choisit une boule de façon uniforme et on la change d’urne.
Xn désigne la v.a nombre de boules dans l’urne A à l’instant n. L’ensemble
des états est donc E = {0, 1, · · · , m}. Dans ces conditions, par exemple si à
un instant l’urne A est vide (la chaı̂ne est dans l’état 0), à l’instant suivant
l’urne contiendra 1 boule avec la probabilité 1. Si à un instant A contient i
boules 0 < i < m, à l’instant suivant elle contiendra i − 1 ou i + 1 avec les
probabiltés respectives: mi et m−i
m
1) Écrire la matrice de tansition de cette chaı̂ne puis dessiner son graphe
orienté.
2) La chaı̂ne est-elle irreductible?
3) Quels sont les états périodiques? Déterminer leur période?
4) Déterminer la loi stationnaire de cette chaı̂ne.

41
Théorème 2.4.2. On considère une chaı̂ne de Markov irreductible d’espace
d’états fini E. On note µ son unique loi de probabilité invariante. On a pour
toute fonction f sur E alors on:
n−1
1X X f (i)
limn f (Xk ) = , p.s
n k=0 i∈E
Ei (τi )

De plus
√ f (X1 ) + · · · + f (Xn−1 )
Z
n( − f dµ)
n
converge en loi vers N (0, 1)( Loi normale centrée réduite)

42
Séances du 16 Novembre 2020: chapitre 2 suite et fin

43
2.4.2 Cas général: E dénombrable
Définition 2.4.2. Un état reccurent j d’une chaı̂ne de Markov est dit rec-
curent positif si:
E(τi |X0 = i) = Ei (τi ) < ∞.
Il est dit reccurent nul dans le cas contraire.

Remarque 2.4.1. Si j est transient, alors:

P(τi = +∞|X0 = i) > 0 donc Ei (τi ) = +∞. Donc un état transient est
forcément nul.

Définition 2.4.3. Ei (τi ) = Mii est appelé le temps moyen de retour dans
l’état i.

Remarque 2.4.2. Les états reccurents sont donc entre les états transients
et les états reccurents positifs. Ils sont reccurents mais leur temps moyen de
retour est infini.

Théorème 2.4.3. Un état reccurent j d’une chaı̂ne de Markov est nul si et

seulement si limn→∞ pnjj = 0

Demonstration 2.4.2. A admettre.

Théorème 2.4.4. La positivité, comme la nullité est une proprièté de classe.

Demonstration 2.4.3. T.D.

Proposition 2.4.2. Si l’espace d’états est fini, les états reccurents sont tous
positifs.

Demonstration 2.4.4. T.D.

Corollaire 2.4.1. Une chaı̂ne de Markov irreductible sur un espace d’états

fini est forcément reccurente positive.

Théorème 2.4.5. Une chaı̂ne de Markov irreductible et reccurente avec E

dénombrable et si de plus (Xn ) est reccurente positive alors il existe une
unique loi de probabilité stationnaire µ qui vérifie: ∀i ∈ E, µ(i) = Ei 1(τi )

Si une chaı̂ne est irreductible nulle(Ei (τi ) = +∞)) il n ’existe pas de loi
de probabilitéé stationnaire.
Soit j ∈ EP on note:
n−1
Nn (j) = k=0 1Xn =j le nombre de fois P que la chaı̂ne visite l’état j dans
l’intervalle de temps [0, n − 1]. Fn (j) = n1 n−1k=0 1Xn =j la fréquence de séjour
dans j dans l’intervalle de temps [0, n − 1]

44
Théorème 2.4.6. Si une chaı̂ne de Markov est irreductible de loi initiale
quelconque alors pour tout j ∈ E on a:
1
Fn (j) → p.s
Ej (τj )
Corollaire 2.4.2. Si une chaı̂ne de Markov est irreductible de matrice de
transition P , la suite P n converge au sens de Cesaro vers la matrice π dont
1
toutes les lignes sont égales et vérifie πij = Ei (Tj)
.
Si la chaı̂ne n’est pas positive, la limite π est nulle.
Si la chaı̂ne est irréductible réccurente positive, toutes les lignes de la matrice
limite π sont égales à l’unique loi de probabilité invariante.

Corollaire 2.4.3. Si une chaı̂ne de Markov est irreductible récurrente pos-

itive d’unique loi de probabilité invariante µ, on a pour toute fonction f µ
intégrable:
lim n1 n−1 f (i)
P P R
k=0 f (Xk ) = i∈E Mi,i = f dµ, p.s

45
Séance du 07 Décembre 2020

46
Chapitre 3

Chaı̂nes de Markov à temps

continu

47
3.1 Rappels
3.1.1 Loi exponentielle, loi de Poisson
Définition 3.1.1. Soit λ un réel positif. Une v.a X à valeurs dans R+ a une
loi exponentielle de paramètre λ si et seulement si sa fonction de répartition
est F (x) = 1 − e−λx . On dit que X suit la loi exponentielle de paramètre λ
et on note X ∼ Exp(λ)
Exercice Démontrer que
1) la densité de probabilité d’une loi exponentielle de paramètre λ est:

f (x) = λe−λx 1x≥0

2) la moyenne et la variance d’une loi exponentielle sont respectivement:

1
λ
et λ12
3) si X1 , X2 , . . . , Xn sont des lois v.a indépendantes de lois exponentielles de
paramètres respectifs λ1 , λ2P , . . . , λn alors la v.a M in(X1 , . . . , Xn ) a une loi
exponentielle de paramètre ni=1 λi
4) la somme de k v.a indépendantes de loi exponentielle de même paramètre
λ est une loi dont la fonction de répartition est:
k−1
−λx
X (λx)n
F (x) = 1 − e
n=0
n!
Cette loi est appelée une loi d’Erlang k de paramètre λ.
5) la densité d’une loi d’Erlang k de paramètre λ est:

(λx)k−1
f (x) = λe−λx 1x≥0
(k − 1)!
Proposition 3.1.1. Propriété de non vieillissement d’une loi exponentielle
Soit X une v.a de loi exponentielle alors:
P(X > t + s/X > s) = P(X > t) = e−λt pour tous t, s ≥ 0.
Cette propriété (très facile à prouver et déjà vue en module de Proba-
bilités en première année) signifie que le temps de vie résiduelle d’une v.a
exponentielle de paramètre λ est une loi exponentielle de paramètre λ et
ceci indépendament de l’âge de la v.a.
Les v.a exponentielles sont souvent utilisées pour modéliser le temps de
vie de composants électroniques, des lampes et d’autres matériels qui ne
vieillissent pas. Elles sont aussi utilisées pour modéliser les temps d’attente
entre deux événements successifs.

48
Définition 3.1.2. Une v.a X à valeurs N suit une loi de Poisson de
paramètre λ si et seulement:
k
P(X = k) = e−λ λk! pour tout k ∈ N
Exercice Démontrer que l’espérance et la variance d’une loi de Poisson
de paramètre λ sont égales à λ.

3.1.2 Processus de Poisson

Définition 3.1.3. Soit (Xn )n une suite croissante de v.a positives . La
fonction de comptage associée à cette suite Xn , n ∈ N est définie par
∞
X
Nt = sup{n ≥ 1, Xn ≤ t} = 1Xn ≤t
n=1

Nt est le nombre d’événements qui se sont produits avant l’instant t. Les v.a
τn = Xn − Xn−1 modélisent les intervalles de temps ou temps d’attente entre
deux évenements successifs. Inversement
Xn = inf {t ≥ 0, Nt ≥ n}
est le nème saut de N
Remarque 3.1.1. 1)Les v.a Xn peuvent modéliser les instants d’arrivées
d’un bus, les instants de naissance d’individus, les instants d’arrivée de
client devant un guichet...
2)Il est facile de voir que:

{Nt ≥ n} = {Xn ≤ t}
et
{Nt = n} = {Xn ≤ t < Xn+1 }
D’où la connaissance de la loi du processus X donne la loi de la fonction
aléatoire de comptage.
Définition 3.1.4. Le processus N ou X est un processus de Poisson si et
seulement s’il vérifie les deux conditions suivantres:
(1)pour tous t0 < t1 < . . . < tn dans R+ , les accroissements (Nti − Nti−1 ,
1 ≤ i ≤ n) sont des v.a indépendantes.
(2) pour tous 0 ≤ s < t, la v.a Nt − Ns a la même loi que Nt−s . Elle ne
dépend donc de s et de t que par la différence t − s.
la propiété (2) signifie que les accroissements sont stationnaires. Donc un
processus de Poisson est un processus à accroissement indépendant et sta-
tionnaire que l’on note par PAIS

49
Proposition 3.1.2. ( A admettre) Soit {Nt , t ≥ 0} un processus de Poisson.
Alors il existe λ > 0 tel que pour tous 0 < t, Nt − Ns est une v.a de Poisson
de paramètre λ(t − s). On a donc:

(λ(t − s))k
P(Nt − Ns = k) = e−λ(t−s)
k!
Cette propriété justifie le nom de processus Poisson.

Remarque 3.1.2. D’après la propriété précedente on a donc:

E(Nt+1 − Nt ) = λ

C’est le nombre moyen d’événements réalisés pendant une unité de temps (

ou taux moyen par unité de temps).

Définition 3.1.5. Le paramètre λ est appelé l’intensité du processus de Pois-

son.

Proposition 3.1.3. (autre construction du porcessus de Poisson à l’aide

des temps d’attente)
Soit (τi )i une suite
Pn de v.a i.i.d P de loi exponentielle de paramètre λ. Soit
T0 = 0, Tn = i=1 τi et Nt = ∞ n=1 1Tn ≤t est un processus de Poisson de
paramètre λ. Tn est appelé le nème point, ou le nème saut de N.

50
Séance du 28 Décembre 2020

51
3.1.3 Chaı̂nes de Markov à temps continu
Définition 3.1.6. Une chaı̂ne de Markov à temps continu est un processus
stochastique {Xt , t ≥ 0} à temps continu défini sur un espace de probabilité
et à valeurs dans un ensemble d’états E fini ou dénombrable vérifiant la
propriété de Markov:

P(Xs+t = j|Xt = i et Xu = l pour tout u ≤ t) = P(Xs+t = j|Xt = is )

pour tous 0 ≤ u < s < t et tout état i, j, l

Définition 3.1.7. Une chaı̂ne de Markov à temps continu est un processus

stochastique X = {Xt , t ≥ 0} à temps continu défini sur un espace de
probabilité et à valeurs dans un ensemble d’états E fini ou dénombrable
vérifiant la propriété de Markov:

P(Xs+t = j|Xt = i etXu = l pour tout u ≤ t) = P(Xs+t = j|Xt = i)

pour tous 0 ≤ u < s < t et tous état i, j, l

Notation: Dans toute la suite, on appellera chaı̂ne de Markov les chaı̂nes

à temps discret et Processus de Markov les chaı̂nes à temps continu.

Définition 3.1.8. Un processus de Markov X est homogène si et seulement

si ∀i, j ∈ E et ∀s, t ≥ 0, P(Xs+t = i|Xt = i) ne dépend pas de t.
On notera ps (i, j) = P(Xs+t = j|Xt = i) et Ps = (ps (i, j))(i,j)∈E est la matrice
de transition. On supposera toujours que P0 = Id la matrice identité.

Proposition 3.1.4. Soit X un processus de Markov et (Pt )t≥0 la famille

des matrices de transition décrivant les lois d’évolution de X, alors:
Pt = (pt (i, j))(i,j)∈E
P est une matrice stochastique c. à.d:
pt (i, j) ≥ 0 et j∈E pt (i, j) = 1 ∀i ∈ E et ∀t ≥ 0.

De plus les équations dePChapman-Kolmogorov sont vérifiées:

P (t + s) = P (t)P (s) = k∈E Ps (i, k)Pt (k, j) ∀s, t ≥ 0.
On dit alors que (Pt )t≥0 est un semi groupe de transition au lieu de matrice
de transition.

Remarque 3.1.3. Les propiétés précedentes et l’hypothèse P0 = Id suffisent

à assurer la continuité par rapport à t des probabiltés pt (i, j)

Définition 3.1.9. On dit que l’état i conduit à l’état j s’il existe t ≥ 0 tel
que pt (i, j) > 0. Deux états i, j communiquent s’ils existent s, t > à tels que
pt (i, j) > 0 et ps (j, i) > 0.

52
Un processus de Markov est irrecductible si tous ses états communiquent deux
à deux. Un état i est absorbant si pour tout t > 0 pt (i, i) = 1. Un processus
de Markov n’est jamais périodique.

Supposons que l’état du processus de Markov à l’instant t est i c’est à

dire Xt = i, il va rester dans cet état pendant une durée aléatoire τi :

• dont la loi ne dépend pas de la valeur de t car le processus est homogène

• dont la loi est sans mémoire car le processus est markovien, On a alors
la proposition suivante

Proposition 3.1.5. Les limites suivantes existent:

(
ai,j = limh→0 ph (i,j)
h
;si i 6= j
ph (i,i)−1
ai,i = limh→0 h
ai,j est appelé le taux de transition de l’état i à l’état j et où ph (i, j) =
P(Xt+h = j|Xt = i)

Proposition 3.1.6. ( temps de séjour dans un état)

Le temps de séjour Si dans l’état i d’un processus de Markov est une v.a
exponentielle de paramètre qi = −ai,i ne dépendant que de l’état i

Lorsque le processus quitte l’état i il va se déplacer vers l’état j avec une

−a
probabilté de transition q(i, j) = ai,ii,j ). Cette probabilité est

• indépendante de la valeur de t car le processus est homogène

• indépendante de Si car le processus est markovien. La suite des états

visités par un processus de Markov aux instants sauts forme une chaı̂ne
de Markov à temps discret. Cette chaı̂ne est appelée la chaı̂ne de
Markov incluse de matrice de transition (qi,j ) tel que qi,i = 0

Définition 3.1.10. La matrice A = (ai,j ) est appelé le générateur

infinitésimal du processus de Markov X.

Remarque 3.1.4. La somme des lignes d’un générateur infinitésimal

est nulle.

53
 Exercice Montrer que le générateur infinitésimal d’un processus de
Poisson de paramètre λ est:
ai,i = −λ, ai,i+1 = λ et ai,j = 0 si i 6= j ou j 6= i + 1.

Théorème 3.1.1. (Equations de Kolmogorov)

Soit X un processus de Markov de générateur infinitésimal L, le semi
groupe de transition (Pt )t≥0 vérifie l’équation de Kolmogorov retrograde:

d
Pt = APt
dt
ainsi que l’équation de Kolmogorove progressive:
d
P t = Pt A
dt

Exercice Montrer que tout processus de Markov dont le générateur

infinitésimal est donné par:
ai,i = −λ, ai,i+1 = λ et ai,j = 0 si i 6= j ou j 6= i + 1 est un processus
de Poisson.

Exemple 3.1.1. (Processus à deux états)

E = {1, 2} avec les taux de transition:
 a(1, 
2) = λ et a(2, 1) = µ. Le
−λ λ
générateur infinitésimal est: A =
−µ µ

Déterminer le semi groupe Pt et montrer que

 µ λ 
λ+µ λ+µ
limPt = µ λ
λ+µ λ+µ

3.1.4 Classification des états

Proposition 3.1.7. Les propriétés suivantes sont équivalentes:
1) la chaı̂ne incluse X̂ du processus de Markov X est irrecductible
2) ∀i, j ∈ E pt (i, j) > 0 pour un t > 0
3) ∀i, j ∈ E pt (i, j) > 0 pour tout t > 0

Définition 3.1.11. Un processus de Markov X esr dit irreductible si

sa chaı̂ne incluse l’est.

54
Définition 3.1.12. un état i est reccurent (resp transient) s’il l’est pour
la chaı̂ne incluse X̂ . Un processus de Markov est dit reccurent(resp
transient) si tous ses états le sont.

Soit
τi = Inf {t > 0, Xt = i et Xt− 6= i}
le temps d’atteinte de l’état i.
Définition 3.1.13. Un état reccurent i est recurrent positif (resp re-
current nul) si et seulement s’il est recurrent et Ei (τi ) < ∞ (resp
Ei (τi ) = +∞.

3.1.5 Stationnarité et théorèmes limites

Définition 3.1.14. Une loi de probabilité ν sur E est dite stationnaire
ou invariante pour le semi groupe de transition (Pt )t>0 si et seulement
si:
νPt = ν, pour tout t > 0 C’est à dire:
X
ν(j) = νi Pt (i, j)
i∈E

pour tout j ∈ E et pour tout t > 0

Comme il est souvent difficile de déterminer le semi groupe de tran-
sition, on a un critère de stationnarité en utilisant le générateur in-
finitésimal A = (ai,j )
Théorème 3.1.2. une loi de probabilité ν est stationnaire si et seule-
ment si; P
νA = 0 c’est à dire i∈E ν(i)ai,j = 0 pour tout j ∈ E.
Théorème 3.1.3. Si le processus de Markov X est irreductible et
admet une distribution stationnaire ν alors:
limt→∞ Pt (i, j) = ν(j), pour tous états i, j P
De plus pour toute fonction f : E → R vérifiant i |f (i)|ν(i) < ∞ on a

1 t
Z X
limt→∞ f (Xs )ds = f (i)ν(i) < ∞ = Eν (f )
t 0 i

Définition 3.1.15. Un processus de Markov de taux de transition

(a(i, j))i,j∈E est dit reversible s’il existe une loi de probabilité ν telle
que :
ν(i)a(i, j) = ν(j)a(j, i) pour tous états i, j. Cette derinière égalité est
appelée condition d’équilibre.

55
Théorème 3.1.4. Si la condition d’équilbre est satisfaire pour un pro-
cessus de Markov alors ν est une loi invariante.

56
 Figure 3.1: Processus de vie et de mort

Exemple 3.1.2. Processus de vie et de mort

57