Files d'Attente

8/3/2019 Files d'Attente

http://slidepdf.com/reader/full/files-dattente 1/30

FILES D’ATTENTE

Lionel BANEGE

[email protected]

Octobre 2004





Table des Matieres

Chapitre 2. Modelisation aleatoire 19

1. Introduction 19

2. Modeles d’arrivees et de services 21

3. Loi exponentielle et fiabilite des systemes 27

4. Evolution temporelle des processus : Stationnarite et Ergodicite 32

5. Processus de Poisson 36

6. Chaınes de Markov 40

7. Exercices 40

Bibliographie 43

3



4 TABLE DES MATIERES



18 TABLE DES MATIERES



CHAPITRE 2

Modelisation aleatoire

L’objectif de ce chapitre est de presenter les processus stochastiques intervenants

dans les modeles issus du formalisme des files d’attente. Ces processus sont egalement

tres souvent utilises en modelisation de systeme a evenements discrets, et en fiabilite

des systemes. L’analyse de performance de systemes modelises a l’aide de ces memes

processus fait alors intervenir des techniques de calcul classiques pour ces processus.

Les principaux processus stochastiques que nous etudierons dans ce cours sont les

processus de Poisson et les chaınes de Markov a temps discret et continu. Ceux-ci

sont detailles dans le support de cours intitule Rappels de Probabilites, Processus de

Poisson et Chaınes de Markov .

1. Introduction

De nombreux phenomenes naturels sont regis par de l’imprevisible. Il en est de

meme pour les systemes technologiques modernes, et toute analyse doit pouvoir tenir

compte de ces phenomenes imprevisibles. Dans une modelisation mathematique, l’outil

qui qui permet de quantifier l’imprevisible est le modele probabiliste, c’est-a-dire le

triplet de probabilite.

Considerons une experience aleatoire, par exemple l’observation d’un phenomene

imprevisible. On lui associe un triplet de probabilite (Ω, A, P) ou, rappelons le

• Ω represente l’ensemble de tous les resultats possibles de l’experience,

• A represente les evenements pour lesquels on peut “mesurer” ou quantifier le“degre” d’aleatoire,

• et P represente la mesure de ce degre d’aleatoire, c’est une mesure de proba-

bilite.

En analyse de performance ou en fiabilite, on ne travaille pas toujours sur les

resultats proprement dit de l’experience aleatoire (ou sur l’observation brute du phe-

nomene aleatoire), mais sur des valeurs numeriques associees a ces resultats. L’outil

probabiliste qui permet ces manipulations est la variable aleatoire, c’est a dire une

fonction mesurable de l’ensemble des resultats d’experience Ω dans R.

Dans la pratique, on est quasiment toujours amene a travailler sur les variables

aleatoires, et le triplet de probabilite sous-jacent est alors eclipse. Neanmoins, enmodelisation, la complexite du systeme modelise peut parfois necessiter de revenir au

niveau du triplet de probabilite.

Une variable aleatoire X definie sur un triplet de probabilite (Ω, A, P) est une

application mesurable

X :(Ω, A) → (R, B(R))

ω → X (ω),

19



20 2. MODELISATION ALEATOIRE

ou B(R) est l’ensemble des boreliens de R.

Exemple 1.1 (Systeme informatique). On considere un systeme informatique

constitue d’une unite centrale (UC) et de cinq terminaux connectes a l’UC via une

seule ligne de communication. En consequence, un seul terminal peut etre utilise a la

fois pour envoyer une requete a l’UC via la ligne. A chaque instant, il peut y avoir

de 0 a 5 terminaux prets a emettre; un sondage est effectue sequentiellement pourdeterminer le nombre de terminaux prets.

Pour construire le modele probabiliste, il est necessaire d’identifier l’imprevisible

apparaissant dans le phenomene observe. Ici, il s’agit de l’etat (pret a transmettre une

requete ou non) de chaque terminal au moment du sondage de la ligne. Le resultat

aleatoire observe a l’issu du sondage est donc un quintuple (e1, . . . , e5) ou ei represente

l’etat du terminal i, par exemple ei = 1 pour un terminal pret a emettre ou ei = 0

dans le cas contraire. L’ensemble de tous les resultats possible de l’experience, Ω, est

donc

Ω = (e1, . . . , e5) : ei = 0 ou ei = 1.

L’ensemble des evenements A est P (Ω), l’ensemble de toutes les parties de Ω, et unemesure de probabilite equiprobable est tout simplement

P(A) =card A

cardΩ, A ∈ A.

Ce modele permet de calculer des probabilites portant sur l’etat des 5 terminaux. Par

exemple, la probabilite p que les cinq terminaux soient prets a emettre lors du sondage

vaut

p =card(e1, . . . , e5) : ei = 1, ∀i

cardΩ=

1

25.

On s’interesse maintenant au nombre X de terminaux prets a emettre lors d’un

sondage. Ce nombre est une fonction du resultat de l’experience, que l’on peut ex-primer comme ceci :

X :

Ω → R

(e1, . . . , e5) → X (e1, . . . , e5) =5i=1

ei.

L’application X est continue, donc mesurable, c’est une variable aleatoire, caracterisee

par sa loi (cf Support de cours Rappels de Probabilites, Processus de Poisson et Chaınes

de Markov , Chapitre 1)

PX(X = i) = P

X −1

(i)

= P((e1, . . . , e5) : exactement i e j valent 1)

=card(e1, . . . , e5) : exactement i e j valent 1

cardΩ

=

5i

25

=5!

i!(5 − i)!32=

15

4i!(5 − i)!.



2. MODELES D’ARRIVEES ET DE SERVICES 21

A chaque instant t, le nombre de terminaux X t prets a emettre est une variable

aleatoire. La collection X t, t ≥ 0 de ces variables aleatoires est un processus stochas-

tique qui represente l’evolution dans le temps du nombre de terminaux prets a emettre.

♦

Nous allons maintenant voir comment les processus stochastiques interviennent

dans le formalisme des files d’attente.Le modele de files d’attente que nous avons detaille au chapitre ?? comporte deux

types de phenomenes imprevisibles qui vont devoir etre modelises via un modele pro-

babiliste, les instants d’arrivee des clients, et les durees de service des clients.

Le processus des arrivees an, n = 1, 2, . . . devient un processus stochastique,

caracterise par ses fonctions de repartition finies dimensionnelles

P(a1 ≤ x1, . . . , an ≤ xn), xi ∈ R, i = 1, . . . , n, n = 1, 2, . . . .

Si on suppose les arrivees deux a deux independantes, ces fonctions deviennent

n

i=1

P(ai ≤ xi), xi ∈ R, i = 1, . . . , n, n = 1, 2, . . . .

Dans la pratique, le processus des arrivees est souvent specifie par la donnee du pro-

cessus des inter-arrivees τ n, n = 1, 2, . . . , avec τ n = an+1 − an.

Pour tout n = 1, 2, . . . , l’instant d’arrivee an est une variable aleatoire, donc

une application de Ω dans R qui a ω ∈ Ω associe an(ω). Si l’on fixe un ω dans

Ω, l’ensemble des valeurs an(ω), n = 1, 2, . . . est une trajectoire du processus, et

represente l’evolution dans le temps d’une realisation unique du processus.

De la meme maniere, les durees de service peuvent etre aleatoires et dans ce cas

le processus des services σn, n = 1, 2, . . . est egalement un processus aleatoire.

En general, les hypotheses suivantes sont faites sur les arrivees et les services:

• Inter-arrivees independantes : τ n deux a deux independantes;

• Services independants : σn deux a deux independantes;

• Processus des arrivees et des services mutuellement independants, i.e. les v.a.

an, n = 1, 2, . . . et σm, m = 1, 2, . . . sont independantes.

Les processus d’arrivees et de service seront egalement souvent stationnaires, c’est-

a-dire de loi independante du temps, soit par exemple pour les arrivees tels que

P(a1+k ≤ x1, . . . , an+k ≤ xn) = P(a1 ≤ x1, . . . , an ≤ xn), xi ∈ R,

i = 1, . . . , n ,

n = 1, 2, . . .

k = 1, 2, . . .

.

Nous allons maintenant aborder au travers de modeles classiques de trafic quelques

lois et processus stochastiques que l’on retrouve tres souvent dans le formalisme des

files d’attente.

2. Modeles d’arrivees et de services

2.1. Loi et processus de Bernouilli — Loi geometrique.




Definition 2.1. Une variable aleatoire de Bernouilli de parametre p dans ]0, 1[

est une variable aleatoire discrete X prenant les valeurs 0 et 1, avec les probabilites

P(X = 1) = p et P(X = 0) = 1 − p.

L’esperance d’une variable aleatoire X de Bernouilli est E[X ] = p, et sa variance

Var(X ) = p(1 − p).

Soit X 1, X 2, . . . une suite infinie de variable aleatoires independantes et de memeloi. On definit la variable aleatoire somme par

S n =ni=1

X i, n = 1, 2, . . . .

Remarquons que les variables aleatoires S n sont dependantes entre elles puisque

S n = S n−1 + X n, n = 2, 3, . . . .

Le processus S n, n = 1, 2, . . . s’appelle une marche aleatoire. Celles-ci sont tres

utilisees pour modeliser des phenomenes naturels varies.

Lorsque les X i suivent toutes une loi de Bernouilli de parametre p, le processus

S n, n = 1, 2, . . . s’appelle un processus de Bernouilli . Ce processus est defini parses lois marginales qui ne se calculent pas facilement a cause de la dependance des

variables aleatoires S n entre elles. Neanmoins, l’une ce ces lois marginales se calcule

simplement, il s’agit de la loi de S n. En effet, S n prend ses valeurs dans 0, 1, . . . , n

avec les probabilites

P(S n = k) = P

k X i = 1 parmi n, (n − k) X i = 0 parmi n

,

soit par independance des X i,

P(S n = k) =

n

k

P(X i = 1)k P(X i = 0)n−k =

n

k

pk (1 − p)(n−k), k = 1, . . . , n .

La variable aleatoire S n suit donc une loi binomiale de parametres n et p. Le processus

de Bernouilli est a la base des modeles naturels d’arrivees en temps discret, commenous le constaterons au paragraphe suivant. Auparavant, interessons nous a une autre

loi discrete, la loi geometrique.

Definition 2.2. Une variable aleatoire entiere et positive ou nulle suit une loi

geometrique de parametre p dans ]0, 1[, si ses probabilites elementaires verifient

P(X = k) = p(1 − p)k, k = 0, 1, 2, . . . .

L’esperance d’une variable aleatoire X de loi geometrique de parametre p se calcule

aisement :

E[X ] =

+∞k=0 k P(X = k) =

+∞k=0 kp(1 − p)

k

= p(1 − p)

+∞k=1(1 − p)

k−1

,

soit finalement

E[X ] = p(1 − p)d

dx

+∞k=0

xk

x=1− p

=p(1 − p)

p2=

1 − p

p.

Un calcul du meme type montre que Var(X ) = 1− p p2

.




La loi geometrique modelise tous les phenomenes d’attente a temps discret “sans

memoire” dans le sens ou le fait d’attendre beaucoup ne change pas la loi du temps

qu’il reste a attendre. Cette propriete caracterise en fait la loi geometrique et se

formalise par la proposition suivante

Proposition 2.3. Soit X une variable aleatoire a valeur dans N. Alors X suit

une loi geometrique de parametre p si et seulement si pour tout m, n ≥ 0

P

X ≥ m + n/X ≥ n) = P

X ≥ m

. (2.1)

Autrement dit, la loi geometrique est la seule loi discrete sans memoire : le temps

qu’il reste a attendre depend uniquement de l’instant ou on observe le phenomene. Le

systeme ne memorise pas l’instant ou le dernier evenement s’est produit.

Preuve. Voyons d’abord la condition necessaire : Si X suit une loi geometrique

de parametre p, alors

P(X ≥ n) =

∞k=n p(1 − p)

k

= p(1 − p)

n 1

1 − (1 − p) = (1 − p)

n

, n = 0, 1, 2, . . . .

En remarquant que l’evenement X ≥ n est necessairement realise des lors que X ≥

m + n est realise, on obtient aisement par la formule des probabilites conditionnelles

P

X ≥ m + n/X ≥ n) =P

X ≥ m + n , X ≥ n

P(X ≥ n)=

P(X ≥ m + n)

P(X ≥ n)=

(1 − p)m+n

(1 − p)n,

et l’egalite (2.1) est alors immediate.

Pour demontrer la condition suffisante, posons λ = P(X ≥ 1). Comme precedem-

ment, on a

P

X ≥ n + 1/X ≥ n) = P(X ≥ n + 1 , X ≥ n)P(X ≥ n)

= P(X ≥ n + 1)P(X ≥ n)

= P(X ≥ 1),

ou la derniere egalite provient de (2.1). On obtient alors

P(X ≥ n + 1) = P(X ≥ 1) P(X ≥ n), d’ou P(X ≥ n) = λn, n = 1, 2, . . . .

Or X est a valeur dans N, donc

λ = P(X ≥ 1 ) = 1 − P(X = 0),

et obtient finalement

P(X ≥ n) = ( 1 − P(X = 0))n, n = 0, 1, 2, . . . ,

ce qui caracterise une loi geometrique.

Nous allons maintenant construire un modele discret d’arrivees a partir du pro-

cessus de Bernouilli.




2.2. Modele discret d’arrivees. On considere un modele discret d’arrivees,

ou une arrivee ne peut se produire que sur un intervalle de temps de type I n =

](n − 1)h,nh], n = 1, 2, . . . , de longueur h > 0 fixe. Autrement dit, sur un intervalle

I n, on observe soit une arrivee, soit aucune arrivee. Il est naturel de supposer que

les arrivees observees sont independantes entre elles, et que la probabilite d’avoir une

arrivee dans un intervalle donne soit la meme pour tous les intervalles I n. Soit p

cette probabilite. Ce modele d’arrivee est un modele discret dans la mesure ou il nepermet pas de connaıtre l’instant precis de l’arrivee, mais simplement l’intervalle de

temps dans lequel elle se produit. Nous verrons ensuite comment passer a un modele

continu.

Le caractere aleatoire du modele tient donc uniquement de la realisation ou non

d’une arrivee dans chacun des intervalles I n. Cela se modelise sans difficulte par une

suite X n, n = 1, 2, . . . de variables aleatoires de Bernouilli de parametre p deux a

deux independantes avec l’interpretation suivante

X n = 1, si une arrivee se produit dans I n =](n − 1)h,nh]

0, si aucune arrivee ne se produit dans I n =](n − 1)h,nh]

,

et

P(X n = 1) = p, P(X n = 0) = 1 − p, n= 1, 2, . . . .

Soit An le nombre d’arrivee se produisant sur l’intervalle ]0, nh]; il est immediat

que

An =ni=1

X i, n = 1, 2, . . . ,

et An, n = 1, 2, . . . est alors un processus de Bernouilli de parametre p.

Nous allons maintenant essayer de caracteriser les durees inter-arrivees, c’est-a-dire le nombre d’intervalles entre deux arrivees successives. Les instants (aleatoires)

d’arrivee se definissent de maniere recursive par

T 1 = inf n > 0 : An = 1; T k+1 = inf n > T k : An − AT k = 1, k = 1, 2, . . . ,

(2.2)

et les durees inter-arrivees sont alors les differences T k+1 − T k, pour k = 1, 2, . . . . Ces

durees inter-arrivees ont des proprietes remarquables, resumees dans la proposition

suivante.

Proposition 2.4. Soit An, n = 1, 2, . . . un processus de Bernouilli de parametre

p, et T k, k = 1, 2, . . . les variables aleatoires representants les instants d’arriveesdefinies par ( 2.2 ). Alors les durees inter-arrivees T k+1 − T k − 1, k = 1, 2, . . . sont deux

a deux independantes et de meme loi, une loi geometrique de parametre p.

Preuve. Commencons par determiner la loi de la duree T 1 avant la premiere

arrivee. Fixons j = 2, 3, . . . . La variable aleatoire T 1 vaut j si et seulement si la

premiere arrivee se produit dans l’intervalle I j et aucune arrivee ne se produit dans




les intervalles I 1, . . . , I j−1, et on a donc, par independance des X i

P(T 1 = j) = P

X 1 = · · · = X j−1 = 0, X j = 1

= P(X j = 1)

j−1i=1

P(X i = 0)

= p(1 − p) j−1

, j = 2, 3, . . . .

Remarquons que cette expression reste valable pour j = 1. On en deduit alors la loi

de T 1 − 1,

P(T 1 − 1 = k) = p(1 − p)k, k = 0, 1, 2, . . . ,

c’est-a-dire une loi geometrique de parametre p.

Considerons maintenant la probabilite conditionnelle

P

T 2 − T 1 = j/T 1 = i

,

pour j ≥ 2. Sachant T 1 = i, l’evenement T 2 − T 1 = j est realise si et seulement si

la seconde arrivee se produit a T 2

= i + j, c’est-a-dire dans l’intervalle I i+ j

, et aucune

arrivee ne se produit dans les intervalles I i+1, . . . , I i+ j−1, et on peut alors ecrire

P

T 2 − T 1 = j/T 1 = i

= P

X i+1 = · · · = X i+ j−1 = 0, X i+ j = 1

= p(1 − p) j−1.

Le resultat trouve etant independant de i, on en deduit que T 2 − T 1 et T 1 sont

independants, et on obtient alors

P(T 2 − T 1 = j) = P

T 2 − T 1 = j/T 1 = i

= p(1 − p) j−1, j = 2, 3, . . . .

La encore cette expression reste valable pour j = 1, et on en deduit que T 2 −T 1 −1 suit

une loi geometrique de parametre p. En procedant de maniere iterative avec les durees

inter-arrivees suivantes, on demontre la propriete pour toutes les durees T k+1 − T k,

k = 1, 2, . . . .

Le modele que nous venons de construire est limite car il ne permet pas de

representer un flot continu d’arrivees, ou les clients se presenteraient a un instant quel-

conque. Nous allons neanmoins l’utiliser pour construire un modele continu d’arrivees

par passage a la limite.

2.3. Modele d’arrivees continu. Reprenons le modele discret d’arrivees pre-

cedent. Il est naturel de prendre la probabilite p d’avoir une arrivee ou non dans un

intervalle I n de longueur h proportionnelle a cette longueur, soit p = λh. Nous allons

nous interesser a la limite du modele precedent lorsque la longueur h de l’intervalletend vers 0 de maniere a obtenir un modele d’arrivees continu. Considerons l’ensemble

des arrivees se produisant sur l’intervalle ]0, t], ou t = nh, et soit X le nombre des

arrivees se produisant sur cet intervalle. Alors X s’exprime simplement comme

X =ni=1

X i,




et d’apres ce que nous avons vu precedemment, X suit une loi binomiale, avec

P(X = j) =

n

j

p j(1 − p)n− j ,

soit avec p = λh = λ tn

,

P(X = j) =

n!

j!(n − j)!λt

n j

1 −

λt

nn− j

=n(n − 1) . . . (n − j + 1)

n j(λt) j

j!

1 − λt

n

n1 − λt

n

j .

Pour j et t fixes, la quantite ci-dessus est equivalente lorsque n → ∞ (soit h → 0)

a l’expressionn j

n j(λt) j

j!

1 −

λt

n

n,

dont la limite lorsque n → ∞ est

(λt) j

j!e−λt.

En resume, la variable aleatoire X converge en loi lorsque n → ∞ (ou h → 0) puisque

limn→∞

P(X = j) =(λt) j

j!e−λt, j = 0, 1, 2, . . . ,

et la loi limite est une loi de Poisson de parametre λt, dont nous rappelons la definition

ci-dessous.

Definition 2.5. Une variable aleatoire X a valeurs entieres positives ou nulles

suit une loi de Poisson de parametre α > 0 si sa loi de probabilite est donnee par

P(X = k) =λk

k!e−λ, k = 0, 1, 2, . . . .

Revenons a notre modele d’arrivees et a ses caracteristiques. Dans ce modele

continu, les arrivees se font a des instants quelconques, et la variable aleatoire X (t)

representant le nombre des arrivees se produisant dans l’intervalle ]0, t] suit une loi de

Poisson de parametre λt. De plus les arrivees sur des intervalles de temps disjoints sont

par construction independantes, et le processus X (t), t ≥ 0 est donc un processus a

accroissements independants. En fait le processus est a accroissements stationnaires

puisque la loi des accroissements est stationnaire (le nombre d’arrivees sur un intervalle

quelconque de longueur t suit une loi de Poisson de parametre λt ne dependant que

de la longueur de l’intervalle). Le processus des arrivees est en fait un processus de

Poisson de parametre λ.

Remarquons enfin que dans ce modele limite p = λh, soit λ =

p

h , avec p la prob-abilite d’avoir une arrivee dans un intervalle de temps de longueur h ou encore la

moyenne du nombre d’arrivees sur cet intervalle, puisque p = E[X i]. Autrement dit

λ represente le nombre moyen d’arrivees par unite de temps, c’est-a-dire le taux des

arrivees. Ceci se retrouve d’ailleurs en considerant la loi du nombre X d’arrivees sur

l’intervalle ]0, t] : La loi de X etant une loi de Poisson de parametre λt, on a E[X ] = λt,

d’ou λ = E[X]t

, le nombre moyen d’arrivees sur ]0, t] par unite de temps.



3. LOI EXPONENTIELLE ET FIABILITE DES SYSTEMES 27

Comme dans le cas discret, la loi des durees inter-arrivees se determine aisement.

Soit τ 1 la duree avant la premiere arrivee et τ n la duree entre la (n − 1)-ieme arrivee

et la n-ieme. Les variables aleatoires τ n sont a valeurs dans R+.

Revenons au modele discret sous-jacent avec t = nh, p = λh et n → ∞ ou de

maniere equivalente, h → 0. Alors I n =]t − h, t], et l’evenement τ 1 ∈]t − h, t] est

realise si et seulement si la premiere arrivee se produit dans I n, autrement dit si aucune

arrivee ne se produit dans I 1, . . . , I n−1 et une arrivee se produit dans I n, d’ou

P(τ 1 ∈]t − h, t]) = P(X 1 = · · · = X n−1 = 0, X n = 1) = (1 − p)n−1 p,

soit finalement

P(τ 1 ∈]t − h, t]) = (1 −λt

n)n−1λh.

Si F τ 1 est la fonction de repartition de τ 1, alors

limh→0

F τ 1(t) − F τ 1(t − h)

h= lim

h→0

1

hP(τ 1 ∈]t − h, t]) = lim

n→∞(1 −

λt

n)n−1λ = e−λt λ .

Autrement dit, la densite f τ 1 de τ 1 vaut

f τ 1(t) =dF τ 1

dt= λe−λt, t ≥ 0,

et on reconnaıt la densite d’une loi exponentielle de parametre λ.

Il est ensuite aise de montrer de maniere similaire et en raisonnant sur le modele

discret sous-jacent que

P(τ 2 ∈]t − h, t]/τ 1 = s) = e−λt λh,

et on peut alors en deduire de maniere iterative que les variables aleatoires τ n, n =

1, 2, . . . sont deux a deux independantes et de meme loi exponentielle de parametre λ.

Ce resultat est bien sur a rapprocher du resultat obtenu avec le modele discret

(Proposition 2.4) et la loi exponentielle joue ici le role de la loi geometrique. Ce n’est

pas un hasard et cette coıncidence decoule du fait que la loi exponentielle et la loi

geometrique sont les deux seules lois, l’une possedant une densite, l’autre discrete,

possedant la propriete d’absence de memoire, comme nous allons maintenant le voir.

3. Loi exponentielle et fiabilite des systemes

La loi exponentielle est tres presente dans deux domaines : les modeles d’arrivees

et de service des files d’attente, et la fiabilite des systemes. Nous utilisons dans ce

paragraphe le pretexte de l’etude de cette loi pour introduire la notion de fiabilite.

3.1. Loi exponentielle. La loi exponentielle, loi d’une variable aleatoire reelle

positive est tres utilisee comme duree inter-arrivee, et egalement comme duree de ser-

vice. Par exemple la file d’attente la plus simple qu’il soit, la file M/M/1 utilise le

modele d’arrivees continu que nous venons d’etudier, et des durees de service expo-

nentielles.




Definition 3.1. Une variable aleatoire X a valeurs dans R+ suit une loi expo-

nentielle de parametre λ > 0 si elle admet une densite donnee par :

f (x) =

λe−λx, x ≥ 0,

0 x < 0.

La fonction de repartition est

F (x) =

1 − e−λx, x ≥ 0,

0, x < 0,

et l’esperance et la variance valent E[X ] = 1λ

et Var(X ) = 2λ2

.

Proposition 3.2. Soit X une variable aleatoire positive admettant une densite.

Alors X suit une loi exponentielle si et seulement si

P(X > t + s/X > s) = P(X > t). (3.1)

Cette propriete exprime clairement la propriete de l’absence de memoire de la loi

lorsque que l’on interprete la variable aleatoire X comme la duree de vie d’un materiel.

En effet, dans ce cas, l’egalite (3.1) signifie que la probabilite pour que la duree de

fonctionnement du materiel soit au moins de t + s sachant qu’il a deja survecu au

moins s unites de temps est la meme que la probabilite qu’il ait une duree de vie

initiale de s unite de temps. Autrement dit, si le materiel fonctionne a s, sa duree de

vie residuelle, c’est-a-dire a partir de cet instant a meme loi que sa duree de vie

initiale, c’est-a-dire, a partir de l’origine. La variable aleatoire est donc sans memoire,

elle ne garde pas la memoire du passe.

Preuve. Pour une variable aleatoire X positive et s, t > 0

P X > t + s/X > s =P(X > s + t, X > s)

P(X > s)=

P(X > s + t)

P(X > s),

de telle sorte que si F (t) = P(X > t), la propriete (3.1) s’ecrit de maniere equivalente

F (s + t) = F (s)F (t), t, s ≥ 0. (3.2)

Considerons maintenant une variable aleatoire X de loi exponentielle de parametre

µ. Alors la fonction F est donnee par

F (t) = 1 − P(X ≤ t) = e−µt, t ≥ 0,

et il est aise de voir que F verifie (3.2).

Reciproquement, soit X une variable aleatoire telle que F (t) = P(X > t) verifie

(3.2). Alors en prenant les logarithmes, on obtient

ln F (t + s) = l n F (t) + ln F (s).

Or il s’avere que les seules fonctions continues solution de l’equation fonctionnelle

g(s + t) = g(s) + g(t)

sont les fonctions lineaires

g(y) = Ky .




Ce resultat plutot intuitif n’est pas evident a montrer mais se trouve etre bien docu-

mente dans la litterature, et sa demonstration depasse l’ob jet de ce cours. Le lecteur

interesse pourra consulter [7].

En admettant ce resultat, il est immediat que

P(X > t) = F (t) = eKt ,

et la croissance de la fonction de repartition F impose alors que la constante K soit

negative, et on reconnaıt alors la fonction de repartition d’une loi exponentielle.

Cette propriete d’absence de memoire de la loi exponentielle est la justification

de l’utilisation de celle loi dans de nombreuses applications en modelisation. Cette

caracterisation nous permettra de retrouver la loi exponentielle lors de l’etude de

processus possedant certaines proprietes d’absence de memoire comme les processus

de Poisson ou les chaınes de Markov que nous etudierons dans les chapitres suivants.

C’est egalement cette propriete qui rend la loi exponentielle tres utile en fiabilite,

comme nous allons maintenant le voir.

3.2. Fiabilite des systemes. La fiabilite est l’etude de la capacite d’un materiel

a rester en mode de fonctionnement. C’est donc l’etude des periodes de (bon) fonc-

tionnement d’un materiel, ou plus exactement de l’evolution de ses periodes de bon

fonctionnement au cours du temps.

Pour analyser la fiabilite d’un systeme ou d’un materiel, on distingue les etats de

marche (ensemble M) des etats de panne (ensemble P ) du-dit systeme. L’etat du

systeme evolue de maniere aleatoire au cours du temps, et son evolution se represente

naturellement par un processus stochastique a temps continu X t, t ≥ 0, ou X test l’etat du systeme a l’instant t. Pour chaque t, X t appartient a M (systeme en

fonctionnement) ou a P (systeme en panne).

Definition 3.3. La fiabilite d’un systeme a un instant t R(t) est la probabilite

que le systeme ait ete en fonctionnement sur ]0, t], soit

R(t) = P(X s ∈ M, ∀s ∈ [0, t]).

La fiabilite s’exprime egalement en fonction de la duree T de fonctionnement ou

duree de vie du systeme,

R(t) = P(T > t).

Revenons maintenant a des definitions generales. Soit T une variable aleatoire

positive, de fonction de repartition F (t) = P [ T ≤ t ], t ∈ R. On definit la notation F par

F (t) = 1 − F (t) = P [ T > t ] , t ∈ R.

La variable aleatoire T representera souvent la duree de bon fonctionnement, la duree

de reparation ou la duree de vie d’un materiel donne. On suppose que la variable

aleatoire T admet une densite f .




Definition 3.4. On appelle taux de hasard de la variable aleatoire T , la fonction :

h(t) =

f (t)

F (t)si F (t) = 0

0 si F (t) = 0.

Remarque 3.5. La densite f n’est definie qu’a une equivalence pres (relativement

a la mesure de Lebesgue), et il en est donc de meme pour h. Dans la plupart des cas,il existe une densite f continue sur R∗+; on prendra alors celle-ci pour la definition de

h.

Si T represente la duree de fonctionnement sans defaillance d’un materiel, h

s’appelle le taux de defaillance du materiel et se note λ.

Si T represente la duree de reparation d’un materiel, h s’appelle le taux de repa-

ration et se note µ.

La propriete suivante permet d’interpreter la definition du taux de hasard h lorsque

T represente une duree de vie d’un materiel.

Proposition 3.6. Si la variable aleatoire T admet une densite f continue sur R∗

+

,

alors pour tout t > 0 tel que P [ T > t ] > 0, on a

h(t) = limδ→0

P [ t < T ≤ t + δ / T > t ]

δ.

Preuve. Soit F la fonction de repartition de T . Alors

P [ t < T ≤ t + δ / T > t ]

δ=

1

δ

P [ t < T ≤ t + δ, T > t ]

P [ T > t ]

=1

δ

P [ T ≤ t + δ ] − P [ T ≤ t ]

1 − F (t)

=

1

δ

F (t + δ) − F (t)

F (t) −−−→δ→0

f (t)

F (t) = h(t)

Pour comprendre l’interpretation de h, supposons que le materiel ait survecu au

moins t unite de temps (evenement T > t realise). Alors la probabilite que le

materiel ne survivra pas a une duree de vie δ supplementaire, P(t < T ≤ t + δ/T > t),

vaut d’apres la preuve ci-dessus,

P(t < T ≤ t + δ/T > t) h(t)δ,

soith(t)

P(t < T ≤ t + δ/T > t)

δ.

Autrement dit, h(t) represente le taux de probabilite qu’un materiel age de t unites de

temps ait une defaillance , c’est donc un taux de defaillance.

En fait, le taux de hasard caracterise completement une distribution, puisqu’il

definit de maniere unique sa fonction de repartition :




Proposition 3.7. La variable aleatoire T a pour taux de hasard h si et seulement

si

∀t > 0, F (t) = P [ T > t ] = e−R t

0h(s)ds. (3.3)

Preuve. La demonstration est simple lorsque la densite et donc la fonction de

hasard est continue. Lorsque ce n’est pas le cas, une demonstration plus generale

est donnee dans le support de cours Rappels de Probabilites, Processus de Poisson et Chaınes de Markov , Chapitre 2, Proposition 4.5.

Pour prouver la condition necessaire, supposons que h soit le taux de hasard de la

variable aleatoire T . Alors

h(t) =f (t)

F (t)=

− ddt

F (t)

F (t),

d’ou, par integration

ln F (t) = −

t0

h(s) ds + K, soit F (t) = F (0)e−R t

0h(s)ds.

Or F (0) = P(T > 0) = 1, et on en deduit l’expression (3.3) pour F (t).Reciproquement si F (t) est donnee par (3.3), alors on en deduit immediatement

f (t) = −dF (t)

dt= h(t) e−

R t

0h(s)ds, puis le taux de hasard

f (t)

F (t)= h(t).

Lorsque T represente la duree de bon fonctionnement d’un materiel, cette derniere

proposition se reecrit en termes de fiabilite :

Corollaire 3.8. Pour un materiel de taux de defaillance λ(t), la fiabilite s’exprime

par

R(t) = e−R t

0λ(s)ds.

Preuve. Il suffit de remarquer que R(t) = P [ ∀s ∈ [0, t], X s ∈ M ] = P [ T > t ]

si T represente la duree de bon fonctionnement du materiel.

La proposition 3.7 permet aussi de caracteriser les variables aleatoires possedant

un taux de hasard constant :

Corollaire 3.9. La variable aleatoire T a un taux de hasard constant egal a c si

et seulement si T est de loi exponentiel le de parametre c.

Preuve. Si h(t) = c pour tout t > 0, alors

F (t) = 1 − P [ T > t ] = 1 − e−R t

0cds = 1 − e−ct, t > 0,

et la reciproque est immediate.




Si la variable aleatoire T designe la duree de fonctionnement d’un materiel, un

taux de defaillance constant signifie que le materiel ne vieillit pas. Dans la pratique,

bien que des materiels simples puissent avoir des taux de defaillance constants, les

systemes plus complexes ont des taux de defaillance qui ne sont plus constants, par

exemple a cause de redondances. Il est tres souvent admis que la courbe du taux de

defaillance d’un materiel t → λ(t) est une courbe de la forme representee Figure 1,

dite courbe en baignoire, qui comporte trois phases :

• La premiere phase (decroissance de λ(t)) est la periode de deverminage ou

rodage;

• La seconde phase ou λ(t) est a peu pres constant est la vie utile du materiel;

• La troisieme phase, ou λ(t) croıt, est la periode de vieillissement ou d’usure du

materiel.

t

λ(t)

vie utile viellissementrodage

Figure 1. Taux de defaillance en fonction du temps (courbe en baignoire)

4. Evolution temporelle des processus : Stationnarite et Ergodicite

Nous avons deja rapidement aborde la notion de stationnarite au chapitre ??. Nous

revenons plus en detail sur cette notion dans le contexte des processus stochastiques.

Definition 4.1. Un processus stochastique X t, t ≥ 0 est (strictement) station-

naire si ses distributions finies dimensionnelles sont invariantes par une translation de

temps, c’est-a-dire si pour tout n = 1, 2, . . . , pour tout t1, . . . , tn et tout x1, . . . , xndans R, et pour tout τ reel,

P

X t1+τ ≤ x1, . . . , X tn+τ ≤ xn

= P

X t1 ≤ x1, . . . , X tn ≤ xn

.

Pour un processus a temps discret, cette propriete s’ecrit

P

X i1+k ≤ x1, . . . , X in+k ≤ xn

= P

X i1 ≤ x1, . . . , X in ≤ xn

,

pour tout i1, . . . , in dans N et tout k = 1, 2, . . . .

En analyse de performance, on s’interesse en general d’avantage au regime per-

manent du systeme, c’est-a-dire apres un temps tres long, qu’au regime transitoire de

mise en route par exemple. En langage mathematique, le regime permanent signifie



4. EVOLUTION TEMPORELLE DES PROCESSUS : STATIONNARITE ET ERGODICITE 33

regime asymptotique, autrement dit passage a la limite pour les variables aleatoires

du modele.

Par exemple, considerons le nombre de clients N (t) presents a l’instant t dans une

file d’attente. Si les arrivees et/ou les durees de service sont aleatoires N (t) est une

variable aleatoire, et on dira qu’un regime permanent existe pour ce systeme si N (t)

converge (en loi, en probabilite, ou avec probabilite 1) lorsque t → ∞. Dans la plupart

des cas, une convergence (faible) en loi suffira pour pouvoir calculer des mesures deperformances du systeme en regime permanent.

Nous avons vu au chapitre ?? lors de la presentation de la loi de Little, differentes

limites temporelles de processus deterministes. La demonstration de la Loi de Little

se generalise aisement dans le contexte probabiliste, en considerant tout simplement

une trajectoire, par exemple N (t, ω), t ≥ 0 des processus. Ceci n’est pas forcement

tres interessant pour estimer des performances de systemes aleatoires, ou une seule

trajectoire des processus n’est pas toujours tres representative. On cherche plutot des

mesures sur des moyennes ensemblistes, plutot que temporelles.

Soit N (t), t ≥ 0 un processus a temps continu et a espace d’etat discret defini

sur l’espace de probabilite (Ω, A, P). Par exemple, N (t) peut representer le nombre

de clients dans un systeme a l’instant t. Soit ω dans Ω fixe.

Definition 4.2. On appelle moyenne temporelle (en regime permanent) du pro-

cessus N (t), t ≥ 0, la quantite

N MoyTemp

= limt→∞

t0 N (s, ω) ds

t. (4.1)

La moyenne temporelle est donc definie sur une trajectoire unique du proces-

sus. Neanmoins, elle est souvent abusivement definie dans la litterature sans que

la dependance avec la trajectoire soit explicitee, en ecrivant,

N MoyTemp

= limt→∞

t0 N (s) ds

t.

Une moyenne temporelle s’obtient en observant une trajectoire du processus sur

un temps tres long. Elle se calcule donc aisement en simulation, ou il suffit de lancer

une simulation sur un temps suffisamment long. La figure 2 reproduit une trajectoire

d’un processus N (t), t ≥ 0 a temps continu et a espace d’etat continu.

t

N (t, ω)

Figure 2. Une trajectoire N (t, ω), t ≥ 0




La moyenne temporelle ne sera a priori pas tres fidele pour representer des quan-

tites telles que l’esperance ou une probabilite, qui elles sont des moyennes sur des

ensembles de trajectoires. Pour ce type de mesures, on dispose d’une autre moyenne.

Definition 4.3. On appelle moyenne ensembliste (en regime permanent) du pro-

cessus N (t), t ≥ 0, la quantite

N MoyEns

= limt→∞

E[N (t)] =∞n=0

npn, (4.2)

ou pn = limt→∞

P(N (t) = n) est la loi limite de N (t) lorsque t → +∞ de N (t).

La moyenne ensembliste est donc tout simplement l’esperance mathematique de

la variable aleatoire limite de N (t). Pour pouvoir la calculer, il suffit que les variables

aleatoires N (t) convergent en loi lorsque t → +∞, autrement dit, il suffit que les

limites limt→∞P(N (t) = n) existent pour tout n = 0, 1, 2, . . . .

La moyenne ensembliste prend en compte toutes les trajectoires des processus en

regime permanent. Elle est donc beaucoup plus couteuse a evaluer a partir d’observa-

tions ou de simulations, car il faut obtenir un grand nombre de realisations independan-tes (des trajectoires) des processus, et chacune sur un temps suffisamment long pour

atteindre le regime permanent. La figure 3 permet de se representer la maniere dont

on peut evaluer une moyenne ensembliste. Pour un grand nombre de trajectoires, il

faut representer N (t, ωi) pour un t suffisamment grand, et ensuite calculer la moyenne

des N (t, ωi).

t

N (t, ω3)

N (t, ω2)

N (t, ω1)

Figure 3. Plusieurs trajectoires N (t, ωi), t ≥ 0

La moyenne ensembliste est tributaire de l’existence d’un regime permanent, c’est-

a-dire l’existence d’une limite (au moins en loi) des variables aleatoires N (t) lorsque

t → +∞. Comme nous le verrons plus tard, le regime permanent correspond au regime

ou l’etat initial du systeme n’a plus d’importance sur le comportement du systeme.De maniere generale, un processus est dit ergodique lorsque une moyenne tem-

porelle converge presque surement vers une moyenne ensembliste. Un exemple de

theoreme ergodique pour un processus a temps discret X n, n = 1, 2, . . . est la loi

forte des grands nombres, qui assure pour un processus independant et identiquement

distribue la convergence presque sure de la moyenne temporelle 1n

ni=1 X i vers la

moyenne ensembliste E[X 1].



4. EVOLUTION TEMPORELLE DES PROCESSUS : STATIONNARITE ET ERGODICITE 35

Nous reviendrons plus en detail sur cette notion d’ergodicite lorsque nous etudierons

les chaınes de Markov, mais retenons maintenant que grossierement, pour un systeme

ergodique, les moyennes temporelles convergent vers les moyennes ensemblistes.

Pour un systeme ergodique, on pourra donc utiliser la loi de Little telle que nous

l’avons demontree au Paragraphe ?? du Chapitre ?? pour relier les moyennes ensem-

blistes entre elles.

Soit T i le temps de reponse de la i-eme arrivee dans le systeme, et A(t) le nombretotal d’arrivees dans l’intervalle [0, t]. Alors la quantite

limt→∞

A(t)i=1 T iA(t)

intervenant dans la loi de Little n’est rien d’autre que la moyenne temporelle T MoyTemp

du temps de reponse T n, n = 1, 2, . . . . La demonstration de la loi de Little presentee

precedemment s’applique bien sur a un systeme stochastique, en considerant une tra-

jectoire, c’est-a-dire un ω fixe dans Ω. On obtient alors

N MoyTemp

= λ T MoyTemp

,

avec N MoyTemp la moyenne temporelle sur la tra jectoire, telle que definie par (4.1).

Pour un systeme ergodique, les moyennes temporelles et ensemblistes coıncident.

De plus on a dans ce cas (admis)

limt→∞

A(t)

t=

D(t)

t,

ou D(t) represente le nombre de departs du systeme pendant [0, t], ce qui assure la

validite de la loi de Little qui devient alors

N MoyEns

= λ T MoyEns

.

Dans la pratique, l’analyse stochastique des systemes d’attente permet souvent de

calculer la loi du nombre de clients dans le systeme en regime permanent, et la loi deLittle, en version moyenne ensembliste, permet alors d’evaluer les temps de reponse

moyens.

Nous terminons ce paragraphe avec un exemple d’application de la loi de Little

pour evaluer le taux d’utilisation d’un systeme. La regle qui en decoule s’appelle la

loi d’utilisation .

Exemple 4.1 (Taux d’utilisation d’un systeme). La loi d’utilisation s’enonce comme

suit :

Soit un systeme ergodique avec un seul serveur, de taux moyen d’arrivee λ et

de taux moyen de service µ. Alors le taux d’utilisation ρ du systeme, c’est-a-dire le

pourcentage de temps ou le serveur est occupe, vaut ρ =λ

µ .

λ

S

µ




Cette loi se demontre aisement en appliquant la loi de Little, version ensembliste, au

sous-systeme S constitue uniquement du serveur. Le nombre de client en service en

regime permanent (RP) N vaut soit 0 soit 1, et le nombre moyen, c’est-a-dire E[N ]

vaut donc

E[N ] = 1 × P(1 client en service en RP) = 1 × ρ.

En effet, ρ est le pourcentage du temps ou le serveur est occupe, c’est-a-dire une

moyenne temporelle, et le systeme etant ergodique, cette moyenne temporelle coıncide

avec la moyenne ensembliste, autrement dit la probabilite que le serveur ait un client

en service en RP.

Il suffit maintenant d’appliquer la loi de Little ensembliste pour obtenir

E[N ] = λ T MoyEns

= λ1

µ,

puisque T MoyEns

represente le temps de service moyen d’un client en RP, soit 1µ , et on

en deduit aisement la relation cherchee. ♦

5. Processus de Poisson

Le processus de Poisson apparaıt souvent en modelisation car ses proprietes en

font un modele naturel. Il est utilise pour representer des instants d’occurrence, par

exemple les instants d’arrivees des clients dans un systeme d’attente, ou en fiabilite,

les instants de defaillance d’un materiel.

Pour la definition et les principales proprietes du processus de Poisson, le lecteur

est renvoye au Chapitre 2 du support de cours Rappels de Probabilites, Processus de

Poisson et Chaınes de Markov .

Nous nous contentons ici d’illustrer par un exemple classique, le paradoxe du

temps d’attente, la rigueur mathematique qu’impose la manipulation des processus

stochastiques.

Exemple 5.1 (Paradoxe du temps d’attente [4] (Voir aussi Exercice 2.2)). On

s’interesse a un arret de bus ou les durees entre deux passages successifs d’un bus sont

des variables aleatoires independantes et identiquement distribuees de loi exponentielle

de parametre α. Les bus se presentent donc a l’arret suivant un processus de Poisson.

Un usager arrive a l’arret de bus a un instant t quelconque. La duree V t entre

l’instant d’arrivee de l’usager et l’instant de passage du prochain bus est aleatoire, et

on cherche a evaluer la duree moyenne E[V t] d’attente de l’usager avant le prochain

passage d’un bus.

T K T K+1

W t

t

L’intuition (raisonnee) permet d’arriver rapidement a deux reponses, malheureusement

non coherentes :

1. La duree moyenne entre deux passages successifs est de 1α

(loi exponentielle de

parametre α); l’usager se presente a un instant quelconque entre deux passages,



5. PROCESSUS DE POISSON 37

donc on peut representer le phenomene comme une arrivee (l’usager) uniforme

(instant d’arrivee quelconque) sur un intervalle de longueur 1α (duree moyenne

entre deux passages), d’ou une duree moyenne d’attente de 12α .

2. Par la propriete d’absence de memoire de la loi exponentielle, a l’instant t la

duree residuelle avant l’arrivee du prochain bus suit egalement une loi expo-

nentielle de parametre α, donc de moyenne 1α ; la duree moyenne d’attente de

l’usager est donc de 1α .

Les deux raisonnements intuitifs exposes ci-dessus semblent a priori corrects, alors

pourquoi cette difference de valeur? En fait les deux raisonnements sont corrects, et

l’erreur survient la ou on ne l’attendait pas.

La solution correcte est la seconde, E[V t] =1α

. Ce qui met la premiere solution en

defaut, c’est l’hypothese que la duree moyenne entre les deux arrivees de bus “encad-

rant” l’instant t d’arrivee de l’usager est 1α

. La duree moyenne entre deux passages

successifs quelconques des bus vaut bien 1α

, mais celle de l’intervalle, qui n’est plus quel-

conque, encadrant l’instant t fixe vaut en fait 2α

, et le raisonnement de notre premiere

solution permet bien de retomber sur la meme valeur moyenne d’attente de l’usager!

Intuitivement, ce resultat peu s’interpreter en disant qu’un intervalle de tempsplus long a plus de chance de “couvrir” l’instant t qu’un intervalle court.

Ce paradoxe apparaıt de maniere generale dans la theorie du renouvellement, et a

cause beaucoup de gene aux theoriciens avant d’etre compris. Nous allons maintenant

demontrer de maniere rigoureuse que la longueur moyenne de l’intervalle “encadrant”

t vaut bien 2α

. Pour cela, nous allons calculer sa loi.

Proposition 5.1. Soit τ 1, τ 2, . . . une suite de variables aleatoires independantes

et identiquement distribuees selon une loi exponentiel le de parametre α. Soit T 0 = 0 et

T k =k

i=1 τ i les bornes des intervalles τ k. Alors, pour t > 0 fixe la variable aleatoire

τ K = T K −1 − T K satisfaisant la condition T K −1 ≤ t < T K admet comme densite la

fonction

gt(x) =

α2 x e−αx, 0 < x ≤ t,

α(1 + αt) e−αx, x > t.(5.1)

La loi de la duree de l’intervalle τ K “encadrant” t n’est donc pas la meme que celle

d’une duree quelconque τ k.

Preuve. Soit donc K l’indice tel que T K −1 ≤ t < T K , et soit Lt = T K − T K −1

la longueur de l’intervalle associe. La loi de Lt s’obtient en calculant sa fonction de

repartition, c’est-a-dire les probabilites P(Lt ≤ x), pour x ≥ 0. Nous distinguons deux

cas.

Si x ≤ t, l’evenement Lt ≤ x est realise si et seulement si il existe n ≥ 1 tels que

T n < t ≤ T n+1 et T n+1 − T n ≤ x.

Remarquons, que n est necessairement superieur ou egal a 2, puisque pour x ≤ t, T 1ne peut pas se realiser apres t lorsque l’evenement Lt ≤ x est realise. Le schema

ci-dessous permet de visualiser ces evenements.




T n+1

x t

Lt

T n

En termes de probabilite l’equivalence ci-dessus s’exprime comme

P(Lt ≤ x) = P

Lt ≤ x, ∪∞n=1T n < t ≤ T n+1

(5.2)

=∞n=1

P

Lt ≤ x, T n < t ≤ T n+1

=∞n=1

P

T n+1 − T n ≤ x, T n < t ≤ tn+1

,

soit en conditionnant sur T n,

P(Lt ≤ x) =∞n=1

∞

0P

T n+1 − T n ≤ x, T n < t ≤ tn+1/T n = y

f n(y) dy

=∞n=1

∞

0P

τ n+1 ≤ x,y < t ≤ y + τ n+1/T n = y

f n(y) dy

=∞n=1

∞

0P

y < t, t − y ≤ τ n+1 ≤ x/T n = y

f n(y) dy

ou f n est la densite de T n. Or τ n+1 et T n sont independantes et τ n+1 suit une loi

exponentielle de parametre α, de telle sorte que

P(Lt ≤ x) =∞n=1

t

t−x

P(t − y ≤ τ n+1 ≤ x) f n(y) dy,

=∞n=1

tt−x

e−α(t−y) − e−αx

f n(y) dy

=

tt−x


∞n=1

f n(y) dy. (5.3)

Le processus T n, n = 1, 2, . . . etant un processus de Poisson, nous savons que T nsuit une loi Gamma de parametres λ et n (cf Poly I, Chapitre 2, Paragraphe 2.1), soit

f n(y) = α(αy)n−1

(n − 1)!e−αy, y ≥ 0,

d’ou∞n=1

f n(y) =∞n=1

α(αy)n−1

(n − 1)!e−αy = αe−αy

∞n=0

(αx)n

n!= α,



5. PROCESSUS DE POISSON 39

et l’egalite (5.3) permet alors d’obtenir

P(Lt ≤ x) =

tt−x

α


dy

= αe−αt(eαt − eα(t−x)) − αxe−αx

= 1 − e−αx(1 − αx).

Pour x > t, contrairement au cas x ≤ t, l’instant t peut etre recouvert par

l’intervalle ]0, T 1], comme illustre ci-apres. Dans ce cas Lt = T 1 et suit donc une

loi exponentielle de parametre α.

Lt = T 1

T 1 T 2

x

t

L’egalite (5.2) s’ecrit maintenant, en adaptant les calculs faits precedemment au

cas x > t, ce qui rajoute un terme et modifie le domaine d’integration de l’integrale

dans (5.3). Il vient

P(Lt ≤ x) = P(Lt ≤ x, 0 < t ≤ T 1) + P

Lt ≤ x, ∪∞n=1T n < t ≤ T n+1

= P(t ≤ T 1 ≤ x) + ∞

0

P(t − y ≤ τ n+1 ≤ x, y < t)α dy

= e−αt − e−αx + α

t0

(e−α(t−y) − e−αx) dy

= 1 − e−αx − αte−αx. (5.4)

En derivant par rapport a x les probabilites (5.3) et (5.4), on obtient alors l’expression

recherchee (5.1) de la densite gt de Lt.

Le lecteur s’assurera en effectuant le calcul

E[Lt] =

∞

0xgt(x) dx =

t0

x α2 x e−αx dx +

∞

t

x α(1 + αt) eαx dx

que l’esperance de Lt vaut bien 2α

.




Pour terminer, calculons directement la loi du temps d’attente de l’usager V t =

T K − t. En procedant de maniere similaire au calcul (5.4), on obtient

P(V t ≤ x) = P(t ≤ T 1, T 1 − t ≤ x) +∞n=1

P

T n < t ≤ T n+1, T n+1 − t ≤ x

= P(t ≤ T 1 ≤ x + t) +

∞n=1

∞0 P

T n < t ≤ T n+1, T n+1 − t ≤ x/T n = y

f n(y) dy

= e−αt − e−α(t+x) +

∞

0P(y < t, t ≤ y + τ n+1, y + τ n+1 ≤ t + x)α dy

= e−αt − e−α(t+x) + α

t0

(e−α(t−y) − e−α(t+x−y)) dy

= 1 − e−αx.

On retrouve ainsi ce que la propriete d’absence de memoire de la loi exponentielle

nous donnait immediatement, c’est-a-dire que la duree d’attente de l’usager suit une

loi exponentielle de parametre α. La duree moyenne d’attente de notre usager est

donc bien de1

α ! ♦

6. Chaınes de Markov

Les chaınes de Markov sont utilisees pour la determination du regime permanent

des files d’attente dont le processus du nombre de clients dans le systeme a l’instant

t, N (t), t ≥ 0 est une chaıne de Markov. Cela comprend notamment toutes les files

d’attente dont les arrivees se font selon un processus de Poisson et les durees de service

sont exponentielles.

Nous utilisons au chapitre suivant en particulier les resultats sur les processus de

naissance et de mort qui sont un exemple de Chaıne de Markov a temps continu.

Le lecteur est donc renvoye au Chapitre 3 du support de cours Rappels de Proba-

bilites, Processus de Poisson et Chaınes de Markov pour les definitions et principalesproprietes des Chaınes de Markov.

7. Exercices

Voir les exercices sur les processus de Poisson et les chaınes de Markov proposes

dans le Poly I, en particulier les exercices 2.3, 2.4, 3.5 et 3.6.

Exercice 2.1 (Duree de bon fonctionnement). On considere un systeme in-

formatique constitue de n sous-systemes independants les uns des autres. La duree de

bon fonctionnement, c’est-a-dire le temps entre deux instants de defaillance consecutifs

du sous-systeme no i suit une loi exponentielle de parametre µi. Le systeme global est

defaillant lorsque l’un des sous-systemes est defaillant.

1. Trouver la loi de la duree de bon fonctionnement du systeme global et le MTTF

(Mean Time To Failure), c’est-a-dire la duree moyenne de bon fonctionnement.

2. Application numerique : Le MTTF de chaque sous-systeme est 2000 h, et n = 4.

Calculer le MTTF du systeme global et la probabilite que la duree de bon

fonctionnement du systeme soit superieure a 100 heures.



7. EXERCICES 41

Exercice 2.2 (Retour sur le paradoxe du temps d’attente). Des bus se

presentent a un arret selon un processus de Poisson homogene T n, n = 1, 2, . . .

(T 0 = 0) de parametre λ. Un passager arrive a l’arret a un instant t ≥ 0 (deterministe).

On note V t et U t les variables aleatoires representant respectivement le temps d’attente

du passager avant l’arrivee du prochain bus a l’arret, et le temps ecoule depuis le

passage du dernier bus avant l’arrivee du passager, soit V t = T K +1 − t et U t = t − T K ,

pour l’indice (aleatoire) K tel que T K ≤ t < T K +1, ou encore, si N (t) represente lenombre d’instants de Poisson entre 0 et t, U t = t − T N (t) et V (t) = T N (t)+1 − t.

1. Trouvez intuitivement le temps d’attente moyen du passager :

(a) en considerant que le passager arrive “au hasard” sur un intervalle de

temps de longueur la duree inter-arrivee du processus de Poisson;

(b) en utilisant la propriete d’absence de memoire de la loi exponentielle.

Conclusions?

2. En remarquant que l’evenement U t > x est realise si et seulement si il existe

n ≥ 0 tel que t − T n > x et T n ≤ t < T n+1, calculer P(U t > x). En deduire

la loi de U t puis P(U t = t). La v.a. U t admet-elle une densite? (Indication :

Utilisez le processus de comptage associe au processus de Poisson.)3. De la meme maniere, calculer P(V t > y) et en deduire la loi de V t.

4. Pour t ≥ 0, soit Lt la longueur (aleatoire) de l’intervalle ]T K , T K +1] contenant

l’instant (deterministe) t. Calculer E[U t], puis en deduire la longueur moyenne

E[Lt] de l’intervalle Lt. Expliquer alors le paradoxe precedent.

5. Determiner la probabilite P(U t > x, V t > y), pour x, y ≥ 0 (Distinguez les cas

x ≥ t de x < t. En deduire P(U t ≤ x, V t > y) puis P(U t ≤ x, V t ≤ y). En

deduire enfin la densite jointe du couple (U t, V t). Les v.a. U t et V t sont-elles

independantes?

6. Determiner la loi de Lt.

Exercice 2.3 (File d’attente discrete, voir aussi Exercice 3.6, Poly Processus).Le fonctionnement d’une unite centrale (UC) d’un ordinateur se fait en temps discretise

dans le sens ou tous les evenements se produisent sur une duree multiple d’une unite

de temps de reference. On modelise le traitement des programmes par l’UC comme

suit. L’axe des temps est decoupe en intervalles ∆k =](k − 1)h,kh], k = 1, 2, . . .

de longueur h > 0, et pour chaque intervalle, avec une probabilite a un programme

se presentent a l’UC, et avec une probabilite 1 − a aucun programme ne se presente

(0 < a < 1). Les programmes se presentent donc a l’UC suivant un processus de

Bernouilli de parametre a.

Les programmes sont traites un par un par l’UC, chacun pendant un nombre entier

aleatoire σ d’intervalles de temps ∆k, ou σ − 1 suit une loi geometrique de parametre

d, 0 < d < 1 soit

P(σ = k) = d(1 − d)k−1, k = 1, 2, . . . .

On suppose que les durees de service sont deux a deux independantes et independan-

tes des arrivees. Les programmes se presentant lorsque l’UC est occupee sont mis en

attente dans une memoire tampon de taille infinie, et sont traites au fur et a mesure

que l’UC se libere selon leur ordre d’arrivee. Soit X k le nombre de clients dans le




systeme au debut de l’intervalle ∆k, donc avant l’arrivee eventuelle d’un programme

dans ∆k.

1. Expliquer pourquoi le processus X k, k = 1, 2, . . . est une chaıne de Markov a

temps discret et preciser ses etats.

2. Determiner les probabilites de transition pij de la chaıne X k, k = 1, 2, . . . et

tracer son diagramme des transitions. La chaıne est-elle irreductible? aperiodi-

que?

3. Ecrire les equations satisfaites par les probabilites stationnaires lorsqu’elles ex-

istent, et les resoudre.

4. En deduire la condition de stabilite du systeme et montrer que la probabilite

π j d’avoir en regime permanent j programmes dans le systeme constitue de

l’UC et de la memoire tampon est de la forme π j = (1 − ρ)ρ j, avec ρ que l’on

precisera.

5. Quel est en regime permanent le nombre moyen de programmes dans la memoire

tampon, et le temps total passe par un programme dans le systeme?

6. Comparer les resultats obtenus avec ceux de la file M/M/1 classique (Voir

Chapitre ??). Interpretation.



Bibliographie

[1] D. Anick, D. Mitra, and M. M. Sondhi. Stochastic theory of a data-handling system with multiple

sources. The Bell System Technical Journal , 61(8):1871–1894, October 1982.

[2] Anwar I. Elwalid and Debasis Mitra. Analysis and design of rate-based congestion control of high

speed networks, I: stochastic fluid models, access regulation. Queuing Systems, 9:29–64, 1991.

[3] Anwar I. Elwalid and Debasis Mitra. Fluid models for the analysis and design of statistical multi-

plexing with loss priorities on multiple classes of bursty traffic. pages 3C.4.1–3C.4.11. IEEE Global

Telecommunications Conference, December 1991.

[4] W. Feller. An Introduction to Probability Theory and Its Applications , volume 2. John Wiley and

Sons, New York, NY, 2nd edition, 1991.

[5] Donald Gross and Carl M. Harris. Fundamentals of Queueing Theory, Third Edition . John Wiley

and Sons, New York, NY, 1998.[6] Leonard Kleinrock. Queueing Systems Volume II: Computer Applications. John Wiley and Sons,

New York, NY, 1976.

[7] Emanuel Parzen. Stochastic Processes. Holden-Day, San Francisco, CA, 1962.

43

Documents

Files d'Attente