Faculté des Sciences de Tunis

Département des Sciences de l’Informatique

Section M1 INFO

PROCESSUS STOCHASTIQUE
COURS2: PROCESSUS MARKOVIEN
1

Sana Younes Dridi

younessana@[Link]
PLAN
Processus stochastique

Chaines de Markov à temps discret (DTMC)

Chaines de Markov à temps continue (CTMC)

Processus de naissance et de Mort

Uniformisation

2
DÉFINITION D’UN PS
Un processus stochastique est une suite de v.a
{Xt}t∈T indexé par le temps t.
Processus 🡪aspect d’une fonction
Stochastique 🡪 aspect aléatoire
Une variable aléatoire X associe à chaque ω ∈ Ω
une réalisation X(ω),
Un processus stochastique {Xt}t∈T associe à
chaque ω une fonction (ou trajectoire)
{Xt(ω)}t∈T : T → E
t → Xt(ω)
E est l‘espace d‘arrivée des v.a Xt 3
EXEMPLE
Température d’une pièce
Intensité du trafic routier
Etc..
Trajectoire: une réalisation du processus dans le
temps. C’est une fonction du temps.

4
EXEMPLE 1 D’UN PS
La trajectoire d’une mouche en fonction du temps
peut être modélisée par un PS à valeurs dans
E=R3 .
Lorsque l’ensemble des temps T est au plus
dénombrable (par exemple T = N), on parle de
processus stochastiques a temps discret
Lorsqu’il est continu (i.e. T = [0;t] ou T = R+), on
parle de processus stochastiques à temps continu.

5
EXEMPLE 2 D’UN PS
Une file d’attente (queue en anglais).
Un certain nombre de guichets et des clients qui sont
soit en train d’être servis, soit en attente qu’un
guichet se libère.
Nt : le nombre total de ces clients dans la salle au
temps t.
Le hasard intervient dans les arrivées des clients
ainsi que dans la durée des services.
La suite (Nt)t≥0 est un processus stochastique à
temps continu et à valeurs dans E = N.
Etudier l’évolution de Nt au cours du temps afin
d’optimiser le nombre de guichets nécessaires pour 6
satisfaire en un temps raisonnable les clients.
PROCESSUS STOCHASTIQUE
Evolution d’une variable aléatoire avec le temps
Espace :
⚫ discret (fini ou infini) : une population
⚫ continu : des coordonnées
Temps:
⚫ discret : horloge
⚫ continu : temps physique

7
8
 Mesures du niveau d’eau dans un barrage:
9
• Chaque jour : temps discret
• Niveau d’eau: un réel (espace continu)
CARACTÉRISATION D’UN PS
Soit X(t)t≥0 un processus stochastique.
A chaque t, X(t) est une v.a
Un v.a est caractérisée par sa fonction de
répartition.
La caractérisation du PS X(t)t≥0 nécessite la
connaissance de la fonction de répartition jointe
du processus pour tout t=t1……tn et x=x1, ….xn
X(t1), X(t2),…..X(tn) sont des v.a
FX(x,t)=Prob(X(t1)≤x1, X(t2) ≤x2,…..X(tn) ≤xn)
Le calcul de FX(x,t) est une tache qui n’est pas
évidente. 10
PLAN
Processus stochastique

Chaines de Markov à temps discret (DTMC)

Chaines de Markov à temps continue (CTMC)

Processus de naissance et de Mort

Uniformisation

11
DTMC DISCRETE TIME MARKOV CHAIN

12

Références: Rapport de thèse Sana YOUNES

DTMC MATRICE STOCHASTIQUE

13
DISTRIBUTIONS TRANSITOIRES ET STATIONNAIRE
Pour une DTMC, il y a:
Les distributions transitoires qui décrivent le
comportement de la chaine à un instant
transitoire n

Une distribution stationnaire (si elle existe) qui

décrit le comportement de la chaine à l’infini
14
EXISTENCE ET UNICITÉ DE LA DISTRIBUTION
STATIONNAIRE

15
EXEMPLE 1

16
EXEMPLE 2

17
EXEMPLE 3
Dessiner les diagrammes correspondant aux
matrices de transition suivantes :

18
EXEMPLE 5
Tant qu'un joueur a de l'argent en main, il joue
en mettant 1D
Il gagne 1D avec une probabilité de p. Il perd sa
mise (1D) avec une probabilité de (1-p) .
Le jeux s'arrête lorsque le joueur n’a plus
d’argents ou lorsqu’il a 3D en main.
Etat de la DTMC: la somme que le joueur
pourrait avoir en main.
Modélisez le comportement stochastique par une
DTMC.
Ecrire la matrice de transition. 19
EXEMPLE 5

20
EXERCICE 1
1) Ecrire la matrice de transition P de la DTMC
suivante:

2) Une DTMC contient deux états 0 et 1 la

probabilité de rester dans 0 est 0.4. Lorsque le
système est dans l’état 1, la probabilité de
revenir vers 0 est de 0.8. Dessiner la DTMC et
la écrire sa matrice de transition
21
EXERCICE 1
1)

2)

22
EXERCICE 2
Soit la matrice de transition définie ainsi.
Dessiner la DTMC correspondante

23
EXERCICE 2

24
CLASSIFICATION DES ÉTATS
Etat atteignable : un état s est dit atteignable
si pour tout état s′ ∈ S, il existe un chemin qui
mène de s′ à s. Par conséquent, si tous les états
sont atteignables les uns aux autres, la chaine
est dite irréductible
Chaine non irréductible:

25
CLASSES DE COMMUNICATION (GRAPHE)
On dira que les états i et j communiquent si j est
accessible à partir de i et i accessible à partir de j.
Dans ce cas on écrira i ↔ j
Considérons le graphe suivant, associé à une
chaîne de Markov homogène dont l’espace des
états est E = {1, 2, 3, 4, 5} :
E = C1 UC2 C1 ∩ C2 = ∅.
C2 = {3, 4, 5} C1 = {1, 2}.

26
CLASSES DE COMMUNICATION (MATRICE DE
TRANSITION)

27
EXEMPLE: DTMC NON IRRÉDUCTIBLE

28
IRRÉDUCTIBILITÉ D’UNE DTMC
Une DTMC est irréductible si elle n’a qu’une
seule classe de communication
Elle a une seule composante fortement connexe
Exemple: DTMC non irreductible.

29
DTMC ABSORBANTE
Etat absorbant: un état s est dit absorbant si
aucun autre état de la chaîne ne peut être atteint
de s. Formellement, s est absorbant si :
P(s, s) = 1
Une chaîne est dite absorbante s’il existe, pour
tout état, un état absorbant atteignable depuis
cet état.
Une DTMC qui contient au moins un état
absorbant n’est pas irréductible.

30
ETAT TRANSITOIRE/ÉTAT RÉCURENT
État transitoire : „Un état est dit transitoire si
le processus ne retourne jamais dans cet état.
Autrement; un état i est transitoire si et
seulement si il existe un état j (j ≠ i) accessible de
l’état i et j n’est pas accessible de l’état i.
État récurent : „Un état est dit récurent si le
processus retourne à cet état définitivement.
Autrement, un état est récurrent s’il n’est pas
transitoire.
En effet, si la durée moyenne de retour à s est
infinie, alors s est dit récurent nul. En
revanche, si la durée moyenne de retour à s est
finie, alors s est dit récurrent non nul ou 31
récurrent positif.
ETAT TRANSITOIRE/ÉTAT RÉCURENT
Nous pouvons constater alors que si la DTMC est
finie, elle ne peut pas avoir d’états récurrents
nuls.
Dans une chaine irréductible finie, tous les états
sont récurrents non nuls.
Un état récurrent est visité un nombre infini de
fois. Un état transitoire n’est visité qu’un nombre
fini de fois.

32
ETAT PÉRIODIQUE /ÉTAT APÉRIODIQUE
Un état est périodique si les temps de retour à cet
état sont nécessairement multiples d’une durée
(période) caractéristique, dans le cas contraire il
sera dit apériodique
Un état apériodique et récurrent non nul est
ergodique.

33
34
Une DTMC qui est irréductible et apériodique est
dite ergodique.
Si une chaîne est ergodique alors elle admet une
distribution stationnaire unique indépendante
de la distribution initiale et l’unique solution de
π=πP 35
36
37
38
PLAN
Processus stochastique

Chaines de Markov à temps discret (DTMC)

Chaines de Markov à temps continue (CTMC)

Processus de naissance et de Mort

Uniformisation

39
40
41
42
43
44
EXEMPLE: CHAINE INCLUSE (EMBEDDED)
CTMC: générateur infinitésimal

DTMC incluse:

45
46
47
48
49
50
EXEMPLE
Calculez la distribution stationnaire de la CTMC
suivante

51
EXEMPLE
Dessinez le graphe de la CTMC correspondante

52
EXERCICE
Ecrire le générateur infinitésimal de la CTMC
suivante et calculez la distribution stationnaire

53
EQUATIONS DE BALANCE

54
PLAN
Processus stochastique

Chaines de Markov à temps discret (DTMC)

Chaines de Markov à temps continue (CTMC)

Processus de naissance et de Mort

Uniformisation

55
PNM
Appelé birdth and death process
L’espace d’états est discret
Les transitions uniquement entre les voisins i
vers i+1 ou i vers i-1
Les taux de transitions: naissance (λi) et mort (μi)

56
PNM
En écrivant les équations de balance:

Par récursivité on montre que:

En utilisant la condition de normalisation pour

détermine la probabilité stationnaire à l’état 0

57
DEUX COMPOSANTS RÉPARABLES IDENTIQUES
Chaines de Markov CTMC à trois états:
⚫ état 1: deux comp. UP
⚫ état 2: 1 seul UP
⚫ état 3: deux DOWN

Deux composants sont prêts à la défaillance ou à

la réparation mais séparément dans un même
intervalle de temps, deux réparateurs.

58
DEUX COMPOSANTS RÉPARABLES IDENTIQUES

59
DEUX COMPOSANTS RÉPARABLES IDENTIQUES

Série:

Parallèle:

60
DEUX COMPOSANTS IDENTIQUES 1 RÉPARATEUR
CTMC

Matrice génératrice

61
FA
Les files d’attente en relation avec le problème
quotidien d’ ‘attente’
Dans différents domaines: Téléphone, Réseaux ,
supermarché, station de services, trames Ethernet
accèdent au medium, requêtes à une base de données
etc…
Le problème sur la théorie de FA est soulevé
initialement par Erlang. Il a traité le problème de
congestion des appels dans le réseau téléphonique
Inspirés par son travail, les ingénieurs et les
mathématiciens ont utilisés les méthodes
probabilistes pour résoudre les problèmes liés à FA
62
FA: CARACTÉRISATION D’UNE FA
Pour caractériser une FA il faut identifier les
propriétés probabilistes du:
Flux d’arrivée: le processus d’arrivée est
caractérisé par la distribution du temps
d’interarrivée des clients (v.a)
A(t)=Prob ( temps interarrivée <t)
Temps de service : (v.a)
B(x)=Prob ( temps de service <x)
Les interarrivées et les temps de service sont supposés
iid (independant identically distributed)

Discipline de service : nombre de serveurs,

capacité du système (maximum nombre de clients en 63
attente inclus celui qui est en cours de service)
FA: NOMBRE DE SERVEURS
Le client peut subir plusieurs traitement
successifs. On parle de serveur en série ou en
tandem.
Serveurs en tandem: réseau de FA ou réseau de
Jackson
Réseau FA soit fermé ou ouvert
Soit m le nombre de serveurs

64
FA: DISCIPLINE DE SERVICE
Quel client est sélectionné pour passer en premier au
service?
Les lois les plus connues:
⚫ FIFO (First In First Out) Ex: guichet
⚫ LIFO (Last In Fist Out) Ex: appels de fonctions en
programmation
Non préemptive : le client qui arrive n’interrompt pas le client en
cours de service.
Préemptive : le client qui arrive est prioritaire sur le client en
cours de service (il revient à FA) salle d’attente :
préemptive "non resume" : le client interrompu perd le travail
déjà fait et doit reprendre au prochain tour.
préemptive "resume" : le client interrompu reprendra son
service là où il a été arrêté.
⚫ RS (Random Service) le client est sélectionné
aléatoirement
⚫ SJF (Shortest Job First)
65
⚫ Priorité
TAILLE DE LA FILE
K :le nombre de clients pouvant être acceptés
dans la FA.
K appartient à [0, ∞]
Cas 0: système sans possibilité d’attente
⚫ Exemple appels téléphoniques acceptés ou rejetés
Cas K: presque tous les systèmes FA sont à
capacité de stockage limitée.
Cas ∞: cas théorique

La capacité de tout le système est K+m

66
NOTATION DE KENDALL
A / B / m / K / n/ D
A: distribution du temps d’inter-arrivée
B: distribution du temps de service
m: nombre de serveurs
K: capacité du système
n: taille de la population (finie ou infinie) customers,
D: discipline de service.

Si la population (n), capacité (K) sont infinies et D=FIFO,

nous parlons de M/M/1
M: markovien (interarrivée poissonien, service
exponentiel)
1: un serveur
67
NOTATION DE KENDALL
A / B / m / K / n/ D
A: distribution du temps d’inter-arrivée
B: distribution du temps de service
m: nombre de serveurs
K: capacité du système
n: taille de la population (finie ou infinie) customers,
D: discipline de service.

Si la population (n), capacité (K) sont infinies et D=FIFO,

nous parlons de M/M/1
M: markovien (interarrivée poissonien, service
exponentiel)
1: un serveur
68
FA: MESURES DE PERFORMANCES
L’objectif est de déterminer les propriétés
probabilistes (densité de probabilité, fonction de
répartition, moyenne, variance) de ces v.a:
Nombre de clients dans le système
Nombre de clients en attente (dans la file)
Temps d’attente d’un client dans la file
Temps d’attente d’un client dans le système
Temps de repos du serveur
Temps d’occupation du serveur
Quand un client n’a pas de place dans la file
(blocage) nous évaluons la probabilité de blocage 69
EXEMPLE DE FA
M/G/m:
⚫ m serveurs
⚫ Arrivée poisson
⚫ Temps service de distribution générale
M/M/r/K/n stands for a system where the customers
⚫ r serveurs
⚫ Capacité de la file K
⚫ Population finie n
⚫ Arrivée poisson
⚫ Temps de service: distribution exponentielle
Pour faciliter les notations
⚫ M/M/1 ⬄ M/M/1/∞/∞/FIFO
70
⚫ M/M/1//30// ⬄ M/M/1/∞/30/FIFO
PARAMÈTRES FA
Paramètres aléatoires: les arrivées, le service, et
la discipline du service

Les autres sont fixes

Une FA est décrite par un processus aléatoire:

⚫ Suite de variables aléatoire (évolution dans le temps)
⚫ Deux régimes stationnaire et transitoires

71
MODÉLISATION PAR F.A
Description d’une file d’attente par un processus
aléatoire :
⚫ Système à états évoluant dans le temps.
⚫ L’état du système à un instant t est en général le
nombre de clients
X(t) qui s’y trouvent à cet instant.
En régime transitoire, calculer la distribution du
processus : P(X(t) = n) pour tout n et t.
En régime stationnaire, calcul P(X = n).
Durée moyenne de service= 1/μ
Nombre de client par unité de temps= λ
Moyenne de l’inter-arrivée = 1/λ 72
MODÉLISATION PAR F.A
A partir des distributions calculées déduire en
moyenne et si c’est calculable les distributions:
Temps de séjour dans le système Ws: temps que
passe un client dans le système.
Temps d’attente dans la queue (temps perdu) Wq:
le temps que passe un client dans la file d’attente
avant d’être servi.
Nombre de clients dans le système Ns.
Nombre de clients dans la queue Nq.

73
M/M/1
N(t) nombre de clients dans le système à un
instant t.
N(t) est une CTMC avec espace d’états
S={0,1,2…..}
Pk(t)=Prob(N(t)=k) : la probabilité que k clients
dans le système à t
Processus de naissance et de mort (Birth and
Death Process)
ρ=λ/μ <1 (stabilité)
Matrice des taux R
Matrice générateur infinitésimal Q
Q(s,s’)=R(s,s’) si s≠s’ , Q(s,s)=-ΣR(s,s’) 74
M/M/1
Calcul des distribution stationnaire P et
transitoire P(t)
Résoudre P Q=0, P vecteur et Q matrice
Pk+1= ρPk
Pk=P0 ρk, k≥0
Suite géométrique de raison ρ
P0=1-ρ
Pk=(1- ρ) ρk

75
M/M/1
Le nombre moyen de clients dans le système Ns :
Ns = Σ kPk= ρ/(1-ρ)
Le nombre moyen de clients en attente dans la
File Nq
Nq=Σ (k-1)Pk= ρ2/(1-ρ)
Temps de séjour moyen dans le système Ws (Loi
de Little) Ws= Ns /λ=ρ/λ(1-ρ)

Temps d’attente moyen d’attente dans la file Wq

(Loi de Little)
Wq=Nq/λ=ρ2/λ(1-ρ)
76
PERFORMANCES DE M/M/1
Ns en fonction de ρ et Ws en fonction de ρ

77
FORMULE DE LITTLE: EXERCICE
un serveur informatique à 5 processeurs,
recevant en moyenne 1000 requêtes/s. Le serveur
est occupé à 100%, et qu’en moyenne 8 requêtes
sont en attente.
Quel est le temps moyen d’attente d’une requête ?
Quel est le temps moyen de traitement d’une
requête ?

78
SOLUTION

D’après la formule de Little (variante) :

Wq = Nq/λ=8/1000 sec:
Quel est le temps moyen de traitement d’une
requête ?
Avec les « deux » lois de Little :
Ns/ λ-Nq/ λ=(13-8)/ 1000=5/1000

79
80
RÉSEAUX DES FILES D’ATTENTES
Un Réseau de Files d’Attente (RFA) est un
ensemble de files simples interconnectées. Il est
caractérisé par :
le processus d’arrivée des clients dans le système
(ex. Poisson de taux λ)
Pour chaque file d’attente individuelle :
⚫ la distribution du temps de service (ex. Exponentielle
de taux µi)
⚫ le nombre de serveurs
⚫ la capacité de la file Ki (éventuellement infinie)
⚫ la discipline de service (FIFO, LIFO, etc, . . . ,
éventuellement avec priorité . . .) 81
ROUTAGE DANS RFA
Le routage des clients dans le système. On
distingue plusieurs types de routage dont :
Le routage dynamique : fonction de l’état courant
du système (par ex. vers la file la moins chargée)
Le routage déterministe: chaque type de client
suit une route prédéterminée
Le routage probabiliste (le plus souvent
considéré). Il est caractérisé par les probabilités
⚫ p0i : la probabilité qu’un client arrivant de l’extérieur
(output) se dirige vers la file i
⚫ pij : la probabilité de se diriger vers la file j à la fin
d’un service dans la file i
⚫ pi0 : la probabilité de se diriger vers l’extérieur à la 82
fin d’un service dans la file i
RÉSEAU DE FA
Les flux entrant dans le réseau sont Poissoniens
Les temps de service de tous les serveurs sont
exponentiellement distribués
Discipline de service : FIFO

83
Chaîne de Markov pour deux files d’attente en
série avec les états (n1,n2)
n1≤4
n2≤4

84
RESEAUX MONOCLASSES/ RESEAUX
MULTICLASSES

On distingue :
Les réseaux monoclasses : parcourus par un seul
type de clients
Les réseaux multiclasses : où circulent plusieurs
classes de clients avec des niveaux de priorité
différents. Ces classes seront caractérisées par :
⚫ des processus d’arrivées différents
⚫ des routages différents
⚫ des temps de service différents dans chaque file

85
RÉSEAUX OUVERTS/ RÉSEAUX FERMES
Dans un réseau ouvert :
on peut avoir des arrivées de l’extérieur
on peut avoir des départs vers l’extérieur
le nombre de clients dans le réseau est variable

86
RÉSEAU FERMÉ
Dans un réseau fermé :
Pas d’arrivées de l’extérieur (p0i = 0)
Pas de départs vers l’extérieur (pi0 = 0)
Le nombre de clients dans le réseau est constant

87
88
EXEMPLE
RFA fermé avec le nombre de clients est égale à 2

89
90