Faculté des Sciences de Tunis
Département des Sciences de l’Informatique
PROCESSUS STOCHASTIQUE ET
FILE D’ATTENTE
COURS1: INTRODUCTION
1
Sana Younes Dridi
younessana@[Link]
OBJECTIF GÉNÉRAL DU COURS
Comprendre c’est quoi un processus stochastique
Introduire le processus markovien
Introduire le formalisme des files d’attentes
Présentation des exemples de Modèles
analytiques
2
EVALUATION
Cours + TD: Sana Younes
Evaluation par deux notes: DS et Examen
3
PLAN GÉNÉRAL DU COURS
Rappels sur les variables aléatoires
Processus de Poisson
Processus stochastique
Chaine de Markov à temps discret (CMTD) ou DTMC
(Discrete Time Markov Chain)
Chaine de Markov à temps continu (CMTD) ou
Continuous Time Markov Chain (CTMC)
4
Files d’attente
EXEMPLE INTRODUCTIF
Une urne contient 20 billets: 4 billet de 10d, 4
billets de 20d et 12 billets perdants.
Pour jouer au jeu le joueur doit dépenser 5d.
Soit X la v.a associant le gain du joueur après un
tir.
Quelles sont les valeurs prises par X, xi?
Quelle est la loi de probabilité de X?
Calculez l’espérance mathématique, la variance et
l’écart type de X?
Ω= l’ensemble univers=l’ensemble des 20 billets
Le cardinal de Ω = 20
5
Les valeurs prises par X : X(Ω)={-5, 5, 15}
EXEMPLE INTRODUCTIF
La loi de probabilité de X est la probabilité
associée à chacune des valeurs prises par X
P(X=-5)=12/20 = 0.6
P(X=5)=4/20=0.2
P(X=15)=4/20=0.2
E(X)=-5 (0.6) + 5 (0.2) + 15 (0.2)= 1d
lorsque le joueur joue un nombre de fois répété, son
gain se rapproche à 1d (jeu favorable pour le joueur
car le gain est positif)
L’espérance est un paramètre de position
6
VARIABLES ALÉATOIRES
Une variable aléatoire (v.a) est une variable
pouvant prendre n’importe quelle valeur d’un
ensemble déterminé de valeurs numériques, et à
laquelle est associée une loi de probabilité.
Une variable aléatoire peut être continue ou
discontinue (discrète).
7
Variables aléatoires continues
Fonction de répartition
La fonction de répartition d’une variable aléatoire X définie
de - ∞ à + ∞ est la fonction F(x) définie par : F(x) = P[X ≤ x]
Propriétés :
lim F(x) = 0 lim F(x) = 1 0 ≤ F(x) ≤ 1 F(x) est non décroissante
x→–∞ x→+∞
Densité de probabilité
Lorsque la fonction de répartition F(x) est dérivable, sa dérivée f(x) est la densité de
probabilité :
dF (x)
f(x) =
dx
Propriétés :
x +∞
F(x) = f(x) dx f(x) dx = 1 8
–∞ –∞
T3.6
EXEMPLE: V.A CONTINUE
9
EXEMPLE: V.A DISCRETE
10
d
S F
Variables aléatoires
E[x] est l’espérance mathématique ou moyenne
+∞
E X =
–∞
x f(x) dx E ( X ) = xi P[ X = xi ]
Moment d’ordre k de la V.A X :
+∞
k k
E X = x f(x) dx
–∞
Variance de la V.A. X :
+∞
V ( X ) = ( xi − E ( X ) ) P [ X = xi ]
2 2
V[x] = x – E[x] f(x) dx
–∞
Ecart-Type :
σ = V[x]
11
T3.7
EXEMPLE V.A: TEMPS BON FONCTIONNEMENT
Soit T: v.a associe le temps de bon fonctionnement
d’un système S
Fonction de répartition de T: F(t) = Prob(T ≤ t)
= ∫0t f(x)dx
F '(t) = f(t) 0 ≤ F(t) ≤ 1
F(t) est la probabilité que le système ait une
défaillance avant l'instant t.
La probabilité de défaillance dans l’intervalle (t1,t2]
est F(t2)-F(t1)
12
EXEMPLES: DENSITÉ DE PROBABILITÉ
Question:
Dites si cette fonction f est une densité de probabilité:
f( x) =3/x4si x∈ [1, +∞ [ ;f ( x) = 0 sinon
Réponse:
f est continue positive
Sa fonction de répartition: F(x)= − 1/x3+1
Les limites de F: lim x->+∞ F(x)=1 et F(1)=0
Donc f est une densité de probabilité
Même question pour f (x) =xe−x si x∈ [0; +∞ [; 0
sinon.
13
F(x)= -xe−x -e−x +1
EXEMPLES: DENSITÉ DE PROBABILITÉ
Soit I l’intervalle [1 ;10] et fλ la fonction continue
définie sur I par : fλ(t)= λt −2
1) Déterminer le réel λ pour lequel fλ est une
densité de probabilité
2) Même question avec I = [1, +∞ [
14
15
d
S F
Loi Exponentielle
Lois Continues La variable aléatoire prend des valeurs continues
Densité de Probabilité : – λt
f ( t) = λ e ; λ > 0; t > 0
Où λ est une constante positive et t le temps
Fonction de répartition : – λt
F ( t) = 1 – e
1
Moyenne : E (x ) =
λ
1
Variance : σ 2
=
x 16
λ 2
d
S F
Loi exponentielle
Représentation graphique :
f(t)
C’est une loi, qui ne dépend que d’un paramètre λ (ou θ = 1/ λ )
17
La v.a exponentielle est sans mémoire
18
SPN: SITUATION DE CONFLIT
19
Pr{X>x}=1-Pr{X<x}=1-FX(x)=1-(1-e-λx)=e-λx
d
S F
Loi de Poisson
La v.a. représente le nombre d’événements (par exemple des
pannes) qui se produisent dans l’intervalle [0, t[.
Un seul paramètre : le taux des arrivées λ
k
–
λ λ
P (x = k ) = e .
k!
Σ
i
– λ . λ
Fonction de répartition : P ( x ≤ k ) = e
i!
i= 0
Espérance mathématique : E[x] = λ
20
Variance : σ 2[x ] = λ
PROPRIÉTÉS DE PP
X est une PP(λ)
PP est une loi de probabilité:
Espérance: E(X)= λ :
On utilise la formule de développement limité suivante
Variance: V(X)= λ (calcul)
Ecart type σ(X)= (λ)1/2 (déduction triviale de la formule de la variance)
Lors des études statistiques lorsque la moyenne d’une v.a quelconque
est relativement proche à la variance on peut faire l’hypothèse que X
suit une loi de poisson. 21
PROCESSUS DE POISSON PP
Loi des évènements rares de paramètre λ.
Soit une période de temps T, un évènement ou
occurrence se produit λ fois en moyenne.
Soit X la variable aléatoire qui associe k=0,1,2….
le nombre de fois que cet événement arrive
On dit que la v.a X suit une loi de poisson de
paramètre λ: PP(λ).
X v.a discrète 22
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. 23
EXEMPLE
Standard d’appel
Arrivée des appels: 2 appels toutes les 30 min
(en moyenne): X suit PP(2)
Quelle est la probabilité que dans une demie
heure donnée il n’y a aucun appel
P(X=0) ?
On peut s’intéresser:
Au nombre d’arrivée de voitures dans une station de
lavage toute les 15 min
Au nombre d’arrivée des taxis dans une station de
taxi
Pas valable pour les bus (qui sont programmés) il n’y
a pas d’indépendances entre les plage horaires. 24
CONDITIONS D’APPLICATION DE PP
1) Le nombre moyen d’occurrence de l’événement est
constant = λ pour chaque période T.
o λ s’exprime en arrivée/unité de temps T
o 1/λ est la durée moyenne des interarrivées
o Le nombre moyen d’arrivée pendant t est λt
Exemple: arrivées des appels suit une PP(5), 5 appels en une
minute. Donc le temps d’interarrivée entre deux appels
successifs est 1/5 min c’est-à-dire 1 appel tous les 12
secondes , le nombre moyen d’appels pendant 3 min est
égal à 15 appels.
2) La probabilité d’occurrence de plusieurs (plus que 2)
événements dans un petit intervalle ∆t est nulle.
3) Le nombre d’occurrence des évènements dans une
période T est totalement indépendant du nombre
d’occurrence dans des périodes différentes
(précédentes). 25
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(t) = 0) = 1 -λ t + o(t)
P(N(t) = 1) = λt + o(t)
P(N(t) =2) = o(t) : probabilité nulle d’avoir
deux arrivées simultanées.
o(t) désigne une fonction petit ordre de t (C’est à dire 26
qui tend vers 0 infiniment plus rapidement que t)
SIMULATION PP(1): DEUX TRAJECTOIRES
27
SOMME DE DEUX PP
X est une PP(λ1)
Y est une PP(λ2)
X et Y sont indépendantes
X+Y est PP(λ1+ λ2) (Dem au tableau)
Exemple: Un système peut présenter deux types de
défauts électrique et mécanique
X: le nbre de défaut elec. PP(1.5)
Y:le nbre de défaut mec. PP(0.5)
Z: le nombre de défaut PP(2)
P(Z=4) = P(X=0 et Y=4) +P(X=1 et Y=3)+….P(X=4
28
et Y=0)
SOMME DE DEUX PP
Nous utilisons la formule de binôme
Généralisation: 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).
29