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.
EXEMPLE 3 D’UN PS
Séries temporelles ou chronologiques.
Les séries temporelles sont des processus
stochastiques.
Elles peuvent modéliser le nombre de morts suite
à des accidents de la route durant un intervalle
de temps, le nombre de passagers dans les
transports aériens
7
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
8
9
Mesures du niveau d’eau dans un barrage:
10
• 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. 11
PROCESSUS DE COMPTAGE
12
PROCESSUS DE COMPTAGE
Un processus de comptage N(t)t>0 à temps
continue compte les arrivées d’un certain
événement.
Évènements:
pannes sur un système
Appels à une cellule
Paquets à une file d’attente d’un routeur
N(t) est le nombre d’arrivées qui ont lieu entre 0
et t. Les instants d’arrivée sont notés Ti ; i = 0…∞
Les v.a τn; n≥ 0 sont les interarrivées.
13
PROCESSUS DE POISSON
Un processus de poisson PP(λ) est un processus de
comptage qui dépend d’un seul paramètre λ.
Les interarrivées τn; n ≥ 0 sont indépendantes et de
même loi exponentielle de paramètre λ
La probabilité qu’il y ait k arrivées en s unités de
temps suit une loi de Poisson :
P(N(t + s)-N(t) = k) = e-λs(λs)k/k! (ne dépend que de s)
P(N(h) = 0) = 1 -λ h + o(h)
P(N(h) = 1) = λh + o(h)
P(N(h) =2) = o(h) : probabilité nulle d’avoir deux
arrivées simultanées.
o(h) désigne une fonction petit ordre de h (C’est à dire
qui tend vers 0 infiniment plus rapidement que h) 14
PROCESSUS DE POISSON
λ s’exprime en arrivée/unité de temps
1/λ est la durée moyenne des interarrivées
Le nombre moyen d’arrivée pendant t est λt
Soit (PP(λi ); i = 1….. n) une suite de n processus
de Poisson indépendants. Le processus résultant
de la superposition des PP(λi ) est un PP(Σλi).
15
SIMULATION PP(1): DEUX TRAJECTOIRES
16
PLAN
Processus stochastique
Chaines de Markov à temps discret (DTMC)
Chaines de Markov à temps continue (CTMC)
Processus de naissance et de Mort
Uniformisation
17
DTMC DISCRETE TIME MARKOV CHAIN
18
Références: Rapport de thèse Sana YOUNES
DTMC MATRICE STOCHASTIQUE
19
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
20
EXISTENCE ET UNICITÉ DE LA
DISTRIBUTION STATIONNAIRE
21
EXEMPLE 1
22
EXEMPLE 2
23
EXEMPLE 3
Dessiner les diagrammes correspondant aux
matrices de transition suivantes :
24
EXEMPLE 4
Calculez la distribution stationnaire de la DTMC
de matrice de transition suivante 0<α≤1
25
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. 26
EXEMPLE 5
27
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
28
EXERCICE 1
1)
2)
29
EXERCICE 2
Soit la matrice de transition définie ainsi.
Dessiner la DTMC correspondante
30
EXERCICE 2
31
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:
32
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}.
33
CLASSES DE COMMUNICATION (MATRICE
DE TRANSITION)
34
EXEMPLE: DTMC NON IRRÉDUCTIBLE
35
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.
36
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.
Exemple:
L’état 0 est récurent 37
L’état 1 est transitoire
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 38
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.
39
ETAT PÉRIODIQUE /ÉTAT APÉRIODIQUE
Un état est périodique si les temps de retour en
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.
40
41
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 42
43
44
45
46
47
PLAN
Processus stochastique
Chaines de Markov à temps discret (DTMC)
Chaines de Markov à temps continue (CTMC)
Processus de naissance et de Mort
Uniformisation
48
49
50
51
52
53
EXEMPLE: CHAINE INCLUSE (EMBEDDED)
CTMC: générateur infinitésimal
DTMC incluse:
54
55
56
57
58
59
EXEMPLE
Calculez la distribution stationnaire de la CTMC
suivante
60
EXEMPLE
Dessinez le graphe de la CTMC correspondante
61
EXERCICE
Ecrire le générateur infinitésimal de la CTMC
suivante et calculez la distribution stationnaire
62
EQUATIONS DE BALANCE
63
PLAN
Processus stochastique
Chaines de Markov à temps discret (DTMC)
Chaines de Markov à temps continue (CTMC)
Processus de naissance et de Mort
Uniformisation
64
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)
65
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
66
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.
67
DEUX COMPOSANTS RÉPARABLES
IDENTIQUES
68
DEUX COMPOSANTS RÉPARABLES
IDENTIQUES
Série:
Parallèle:
69
DEUX COMPOSANTS IDENTIQUES 1
RÉPARATEUR
CTMC
Matrice génératrice
70
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
71
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 attente 72
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
73
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) 74
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
75
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
76
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
77
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 78
EXEMPLE DE FA
M/G/m:
m serveurs
Arrivée poisson
Temps service de distribution general
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
79
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
80
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/λ 81
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.
82
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’) 83
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
84
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-ρ)
85
PERFORMANCES DE M/M/1
Ns en fonction de ρ et Ws en fonction de ρ
86