Méthodes nonlinéaires et stochastiques de la recherche ...Marco.Dozzi/RechercheOperationnelle3/... · Méthodes nonlinéaires et stochastiques de la recherche opérationnelle Marco

Méthodes nonlinéaires et stochastiques de la recherche

opérationnelle

Marco Dozzi

2 août 2004

2

Table des matières

II Chaînes de Markov et files d’attente 5II.1 Rappel sur les probabilités conditionnelles et le modèle d’Ising . . . . . . . . 5II.2 Les chaînes de Markov à temps discret . . . . . . . . . . . . . . . . . . . . . 7

II.2.1 Définition, probabilités de transition et loi stationnaire . . . . . . . . 8II.2.2 Exemples en gestion, économie et imagerie . . . . . . . . . . . . . . . 12

II.3 Les chaînes de Markov à temps continu . . . . . . . . . . . . . . . . . . . . . 15II.3.1 Intensités de transition et modèles linéaires . . . . . . . . . . . . . . 16II.3.2 Le processus de Poisson . . . . . . . . . . . . . . . . . . . . . . . . . 17II.3.3 La loi stationnaire dans le cas où l’ensemble des états possibles est fini 19II.3.4 Un exemple en gestion . . . . . . . . . . . . . . . . . . . . . . . . . . 20II.3.5 Les files d’attente M/M/s/R . . . . . . . . . . . . . . . . . . . . . . . 22

II.4 Simulation de files d’attente . . . . . . . . . . . . . . . . . . . . . . . . . . . 24II.4.1 Simulation d’une variable aléatoire de loi donnée . . . . . . . . . . . 25II.4.2 Générateur de nombres pseudo-aléatoires . . . . . . . . . . . . . . . 27II.4.3 Un exemple de gestion . . . . . . . . . . . . . . . . . . . . . . . . . . 31

II.5 Remarques bibliographiques . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

3

4 TABLE DES MATIÈRES

Chapitre II

Chaînes de Markov et files d’attente

Dans ce chapitre des méthodes probabilistes et statistiques de la recherche opération-nelle sont traitées. Il s’agit, par exemple, d’analyser l’évolution temporelle du marché d’unproduit, ou de reconstituer une image ou d’analyser une file d’attente avec des arrivées etdes départs aléatoires. Nous effectuons ces analyses dans le cadre des chaînes de Markov entemps discret (section II.2) ou en temps continu (section II.3). Plus généralement ce cadrepermet d’analyser des systèmes dont l’évolution temporelle comporte des incertitudes duesà des facteurs qui ne sont pas entièrement sous contrôle. L’analyse se fait en termes devariables aléatoires ou de vecteurs aléatoires et de leur lois qui décrivent le comportementfutur du système en fonction des paramètres observés. Il est assez fréquent que de telssystèmes trouvent, après un certain temps, un état d’équilibre, appelé état stationnaire quireste valable jusqu’à ce que des facteurs extérieurs provoquent à nouveau un déséquilibre.En section II.2 et II.3 nous donnons des formules explicites qui permettent de trouver ceslois stationnaires et qui sont applicables à des systèmes peu complexes. Pour des systèmesplus complexes les analyses mathématiquement rigoureuses sont souvent difficiles à effec-tuer et dépassent le cadre de ce cours. Parfois on préfère simuler l’évolution du système surordinateur et obtenir des prévisions sur le comportement futur de cette façon. Pour cetteraison nous traitons en section II.4 la simulation de variables aléatoires.

Comme la notion de probabilité conditionnelle est fondamentale pour les chaînes deMarkov, nous commençons ce chapitre par un rappel de ces notions.

II.1 Rappel sur les probabilités conditionnelles et le modèle

d’Ising

Définition. La probabilité conditionnelle de B donné A, notée P (B|A), est donnée par :

P (B|A) =P (B ∩ A)

P (A)si P (A) 6= 0.

B est indépendant de A si P (B|A) = P (B).

Exemple :A l’ensemble des fumeurs d’une population notée ΩB l’ensemble des personnes souffrant d’un cancer des poumons de ΩP (B|A) est alors le risque de souffrir d’un cancer des poumons si on considère uniquement lapopulation des fumeurs. Une question qui se pose souvent est alors si P (A|B) > P (B|Ac).

5

6 CHAPITRE II. CHAÎNES DE MARKOV ET FILES D’ATTENTE

ABAC

Ω

En pratique il est assez fréquent d’observer les probabilités conditionnelles mais de s’in-téresser en fait aux probabilités non conditionnelles, comme le montre l’exemple suivant :

Exemple : Considérons la fabrication en grande quantité d’une certaine piéce. NotonsAi l’ensemble des pièces fabriquées sur la machine i (i = 1, 2, ..., n),B l’ensemble des pièces défectueuses,P (B|Ai) probabilité conditionnelle qu’une pièce est défectueuse sachant qu’elle a été pro-duite sur la machine i.L’acheteur des pièces s’intéresse à P (B). Nous allons déduire cette probabilité à l’aide dela formule de probabilité totale. Supposons que les valeurs numériques suivantes ont étéobservées sur n = 4 machines :

machine % de la production % de pièces défectueuses P (B|Ai)

1 40 1 0.01

2 30 2 0.02

3 20 4 0.04

4 10 5 0.05

La machine 4 est donc la moins fiable. P (B) se calcule comme suit :

P (B) = P (B ∩ (A1 ∪ A2 ∪ A3 ∪ A4))

= P ((B ∩ A1) ∪ (B ∩ A2) ∪ (B ∩ A3) ∪ (B ∩ A4))

=

n∑

i=1

P (B ∩ Ai) =

n∑

i=1

P (Ai)P (B|Ai)

= 0.4 × 0.01 + 0.3 × 0.02 + 0.2 × 0.04 + 0.1 × 0.05 = 0.023

La probabilité qu’une pièce choisie au hasard soit défectueuse est donc égale à 0.023.

On a utilisé la formule de probabilité totale qui, en forme générale, s’écrit :

P (B) =∑n

i=1 P (Ai)P (B|Ai) avec A1,A2,...,An disjoints, P (n∪

i=1Ai) = 1.

Probabilités conditionnelles pour le modèle d’Ising(E. Ising, physicien allemand, 1925)Considérons la grille G de points donnée ci-contre, repré-sentant des pixels d’un appareil photographique numériquepar exemple. A chacun des points est associée une valeur(représentant un niveau de gris par exemple). On note Sl’ensemble des valeurs possibles. Pour simplifier on supposeS = −1,+1 (-1 pour un point blanc, +1 pour un pointnoir). Une configuration, notée c = (ci)i∈G, est une famillede valeurs ci ∈ S, où i parcourt l’ensemble des points de G.On s’intéresse à diverses mesures qui permettent de décrirela structure de la configuration. Par exemple on considère

• • • • • • • • • •

II.2. LES CHAÎNES DE MARKOV À TEMPS DISCRET 7

H(c) = −∑

i∼j

cicj,

où i ∼ j signifie que i et j sont voisins (horizontalement ou verticalement). H(c) est lesurplus des voisins de coloration différente sur les voisins de coloration égale (contrastes).Souvent on considère H ′(c) = βH(c) où β est une constante donnée. Il s’agit d’un casparticulier d’un modèle que E. Ising avait considéré en magnétisme, où β est la températureinverse, et ci est la charge positive ou négative d’une particule. On va voir que ce modèlesert, parmi d’autres, à la reconstitution d’images.Pour faire le lien avec les probabilités conditionnelles, nous considérons des configurationsaléatoires, notées (Xi)i∈G, où les Xi sont des variables aléatoires. Une loi de probabilitéassociée à H sur l’ensemble des configurations est donnée par :

Π(c) =1

Zexp(−β

∑

i∼j

cicj), c = (ci)i∈G,

où Z =∑

c exp(−β∑

i∼j cicj), la somme∑

c s’étend sur l’ensemble des configurations pos-sibles de G. Cette somme est impraticable parce que le nombre de configurations possiblesest beaucoup trop grand en pratique : de l’ordre de (106)256, si la grille compte 106 points,chacun d’entre eux étant coloré par un des 256 niveaux de gris disponibles. On préfère doncles probabilités conditionnelles qui sont plus simples à calculer comme le montre le calculsuivant. Pour S = −1,+1 et pour i ∈ G fixé on a :

P (Xi = ci|Xj = cj pour tous j 6= i) =P (Xj = cj pour tous j 6= i et Xi = ci)

P (Xj = cj pour tous j 6= i)

=P (Xi = cj pour tous j 6= i et Xi = ci)

P (Xj = cj pour tous j 6= i et Xi = −1) + P (Xj = cj pour tous j 6= i et Xi = +1)

=[exp(−β

∑

j∼i cicj − β

∑

l∼j,l,j 6=i clcj)]/Z

[exp(+β∑

j∼i cj − β

∑

l∼j,l,j 6=i clcj) + exp(−β

∑

j∼i cj − β

∑

l∼j,l,j 6=i clcj)]/Z

=exp(−βci

∑

j∼i cj)

exp(β∑

j∼i cj) + exp(−β

∑

j∼i cj)

(II.1)

Pour ci = ±1 on a donc

P (Xi = ±1|Xj = cj pourtous j 6= i) = (1 + exp(±2β∑

j∼i

cj))−1.

La loi conditionnelle de Xi donné Xj pour tous j ∈ G, j 6= i se calcule donc facilementà partir des valeurs des points voisins de i seulement. Nous utiliserons ces probabilitésconditionnelles à la section suivante.

II.2 Les chaînes de Markov à temps discret

Nous allons étudier l’évolution temporelle d’un système, qui possède la proprété deMarkov. Le futur d’un tel système est déterminé par son état présent, et ne tient pascompte de son passé.Notons Xt l’état du système à l’instant t. Nous modélisons Xt par une variable aléatoireou un vecteur aléatoire à valeurs dans S, l’ensemble des états possibles du système quelque soit t.


Dans cette section t varie dans N ou dans un sous-ensemble fini de N. Pour des modèlesen temps continu que l’on étudiera à la section suivante, t varie dans R ou dans un sous-ensemble de R. De façon générale on note (Xt, t ∈ I) une famille de variables aléatoires.La propriété de Markov signifie alors que l’état futur Xt+u est indépendant du passé Xt−s,sachant le présent Xt (t, s, u > 0).

II.2.1 Définition, probabilités de transition et loi stationnaire

Définition. Soit I ⊆ N. (Xt, t ∈ I) est une chaîne de Markov1 (à temps discret) si

P (Xt+1 = xj|Xt = xi,Xt−1 = xt−1, ...,Xt−n = xt−n) = P (Xt+1 = xj |Xt = xi)

pour tous n ∈ N∗ tel que t + 1,t,t − 1,...,t − n ∈ I et tous xj , xi, xt−1,..., xt−n ∈ S.

Exemple 1 : La souris markovienne et les quatre trous.

2

3

1

4

12/

12/

12/

12/

12/1

2/

12/

12/

I = N, S = 1, 2, 3, 4La souris qui se trouve dans le trou i à présent,saute avec une probabilité 1

2 vers l’un des trousi + 1 ou i − 1 (mod 4). Son choix du prochaintrou ne tient donc pas compte du trou par lequelelle est arrivée au trou i. De façon générale onnote

tpij = P (Xt+1 = j|Xt = i)la probabilité de transition de i vers j (i,j ∈ S).Notons qu’il s’agit de probabilités condition-nelles définies en section II.1.

Dans cet exemple les probabilités de transition sont stationnaires au sens que tpij nedépend pas de t. On écrit donc pij à la place de tpij. On pose

P := (pij; i, j ∈ S) =

0 12 0 1

212 0 1

2 00 1

2 0 12

12 0 1

2 0

.P est la matrice de transition de la chaîne de Markov.

On va voir maintenant que la loi initiale (c’est-à-dire le vecteur des probabilités P (X0 =i), i ∈ S) et P déterminent la loi de Xn (c’est-à-dire le vecteur des probabilités P (Xn =i), i ∈ S) pour tous n ∈ N

∗. En effet, par la formule de la probabilité totale (voir sectionII.1), on a :

P (X1 = j) =

4∑

i=1

P (X0 = i)P (X1 = j|X0 = i) =

4∑

i=1

P (X0 = i)pij j = 1, 2, 3, 4,

ce qui signifie qu’on obtient la loi de X1 en multipliant la loi de X0 par P .

On procède à la définition des probabilités de transition d’ordre supérieur :

1A.A. Markov, mathématicien russe, 1856-1922


Définition. Soit I ⊆ N et (Xt; t ∈ I) une chaîne de Markov. Les probabilités de transition d’ordre nsont données par

t

p(m)ij = P (Xt+m = xj|Xt = xi) m ∈ N

∗, t, t + m ∈ I.

Les probabilités de transition d’ordre m sont stationnaires sit

p(m)ij =p

(m)ij pour tous xi, xj ∈

S (c’est-à-dire ne dépendant pas de t).

La prochaine proposition montre que les probabilités de transition d’ordre m pourm > 1 se calculent facilement à partir de P .

Proposition II.1. (Égalités de Chapman-Kolmogorov)Soit (Xt; t ∈ N) une chaîne de Markov dont les probabilités de transition d’ordre m sontstationnaires pour tous m ∈ N

∗. Soit S = x1, x2, ..., xn l’ensemble des états possibles dela chaîne. Alors

p(m)ij = P (Xt+m = xj|Xt = xi) =

∑

k∈S

p(l)ik p

(m−l)kj

pour tous l ∈ 1, ...,m − 1 et xi, xj ∈ S. Notons P (m) = (p(m)ij ; i, j ∈ S). Alors P (m) =

P (l)P (m−l) pour tous l ∈ 1, ...,m − 1. En particulier P (m) = Pm.

Preuve. Elle se fait à l’aide de la propriété de Markov et le calcul des probabilités condi-tionnelles. Nous donnons le calcul explicite pour m = 2 et l = 1.

p(2)ij = P (Xt+2 = xj|Xt = xi) =

∑

k∈S

P (Xt+2 = xj , Xt+1 = xk|Xt = xi)

=∑

xk∈S

P (Xt+2 = xj , Xt+1 = xk, Xt = Xi)

P (Xt = xi)× P (Xt+1 = xk, Xt = xi)

P (Xt+1 = xk, Xt = xi)

=∑

xk∈S

P (Xt+2 = xj |Xt+1 = xk, Xt = xi)P (Xt+1 = xk|Xt = xi)

=∑

xk∈S

pkjpik = (PP )ij = (P 2)ij (i, j ∈ S)

Donc P (2) = (p(2)ij ; i, j ∈ S) = P 2. De même façon on démontre que

p(3)ij = P (Xt+3 = xj|Xt = xi) =

∑

xk∈S

pikp2kj = (PP 2)ij = (P 3)ij .

Donc P (3) = P 3. De façon générale on a

P (m) = P (1)P (m−1) = P (1)P (1)P (m−2) = Pm

.

Exemple 1 (suite). Par la Proposition II.1 et en effectuant le calcul du produit de matriceson obtient :

P (2) = PP =

12 0 1

2 00 1

2 0 12

12 0 1

2 00 1

2 0 12

, P (3) = PP (2) = P, P (4) = PP (3) = P 2


On en déduit que P (2m+1) = P et P (2m) = P 2. Ceci détermine le comportement de P (m)

pour m → ∞. Dans ce cas la suite (P (m))m∈N∗ ne converge donc pas. L’exemple suivantmontre que la suite (P (m))m∈N∗ converge dans certains cas.

Exemple 2. La souris markovienne et les 3 trous.

23

1

12/

12/

12/

12/

12/

12/

I = N, S = 1, 2, 3,

P =

0 12

12

12 0 1

212

12 0

, P (2) = P 2 =

12

14

14

14

12

14

14

14

12

.

On remarque qu’aucun élément de P (2) est éga à zéro, contrairement à l’Exemple 1où il y avait des zéros dans P (m) pour tous m ∈ N

∗. Nous allons maintenant étudier lecomportement de (P (m))m∈N∗ pour l’Exemple 2. Supposons d’abord que la loi de X0 estdonnée par

P (X0 = 1) = P (X0 = 2) = P (X0 = 3) =1

3Par la formule de probabilité totale on obtient pour j=1,2,3 :

P (X1 = j) =

3∑

i=1

P (X0 = i)P (X1 = j|X0 = i) =1

3

3∑

i=1

P (X1 = j|X0 = i) =1

3

3∑

i=1

pij =1

3

En remplaçant X0 par X1 et X1 par X2 on obtient de même façon : P (X2 = j) = 13

(j=1,2,3). On en déduit du calcul ci-dessus que :

a) P (Xn = j) = 13 pour tous n ∈ N

∗, c’est à dire que Xn suit la loi uniforme surS = 1, 2, 3 pour tous n ∈ N

∗.b) Notons π = (π1, π2, π3) = (1

3 , 13 , 1

3). Alors π = πP , c’est à dire que π est invariantpar multiplication à droite par P .

Le Théorème II.2 ci-dessous nous dit que P (∞) = limn→∞ P (n) existe dans ce cas etque les lignes de P (∞) sont égales à π :

P (∞) =

13

13

13

13

13

13

13

13

13

Ceci veut dire que π intervient aussi en tant que limite, quand n → ∞, des probabilités detransition. En plus, cette limite ne dépend pas de la loi initiale. En effet, par la formule dela probabilité totale, P (Xn = j) =

∑3i=1 P (X0 = i)P (Xn = j| X0 = i) pour tous n ∈ N

∗,quelle que soit la loi initiale P (X0 = i) i = 1, 2, 3. Donc

limn→∞P (Xn = j) =

3∑

i=1

P (X0 = i) limn→∞

P (Xn = j| X0 = i) =

3∑

i=1

P (X0 = i)pnij

= πj

3∑

i=1

P (X0 = i) = πj j = 1, 2, 3,


quelle que soit la loi initiale P (X0 = i), i = 1, 2, 3. On dit que π = (π1, π2, π3) est une loistationnaire.Pour la souris de l’Exemple 2 cela veut dire que quelque soit sa position à l’instant zéro,la probabilité qu’elle se trouve dans le trou i après un grand nombre de sauts va convergervers 1

3 pour i = 1, 2, 3. La loi de sa position après un grand nombre de sauts va doncconverger vers la loi uniforme sur S = 1, 2, 3.

Sous quelles conditions la loi stationnaire existe-t-elle en général ?

La définition qui suit donne des conditions suffisantes pour l’existence d’une loi sta-tionnaire.

Définition. Soit (Xn, n ∈ N) une chaîne de Markov dont les probabilités de transitionsont stationnaires. Soit S = x1, x2, ..., xq.

a) xj ∈ S est récurent positif si xj est visité une infinité de fois, c’est-à-dire qu’il existeun nombre infini de valeurs n telles que Xn = xj. On suppose en plus que le tempsmoyen entre deux visites est fini, ce qui est toujours le cas si S est fini, mais pasnécessairement si S est infini.(Xn; n ∈ N) est récurrent positif si tous les éléments de S sont récurrents positifs.

b) (Xn; n ∈ N) est apériodique si p(m)ii > 0 pour tous m ∈ N suffisamment grand, et

pour tous xi ∈ S.

Remarque. Les chaînes de Exemples 1 et 2 sont récurrentes positives. En fait, la proba-bilité qu’un site ne sera plus jamais visité après un certain temps est égal à zéro. Notonsaussi que la probabilité qu’un certain site est visité une infinité de fois est soit zéro soit un(preuve admise).

La chaîne de l’Exemple 1 n’est pas apériodique : en fait p(2m+1)ii = 0 pour tous m ∈ N

∗ ettous i ∈ S = 1, 2, 3, 4 (voir les zéros dans les matrices de transition P et P 2). La chaîne

de l’Exemple 2 est apériodique : p(m)ii > 0 pour tous m ∈ N

∗ et tous i ∈ S = 1, 2, 3.

Théorème II.2. Soit (Xn, n ∈ N) une chaîne de Markov apériodique et récurrente posi-tive, à valeurs dans S=x1, x2, ..., xq. La loi de Xn, ainsi que les probabilités de transitions

p(m)ij (xi, xj ∈ S) convergent alors, quand n → ∞ et m → ∞, vers une loi stationnaire

π = (πj , j = 1, 2, ..., q). Cette loi stationnaire ne dépend pas de la loi initiale (c’est à direde la loi de X0). Elle est déterminée de façon unique par le système d’équations linéaires

π = πP,

q∑

j=1

πj = 1, πj > 0 (j = 1, ..., q)

Remarque. a) Une autre condition suffisante pour l’existence de probabilités station-naires est la suivante :(C) il existe m ∈ N

∗ tel que tous les éléments de P (m) sont positifs, c’est-à-dire que

p(m)ij > 0 pour tous xi, xj ∈ S.

La condition (C) implique en fait que la chaîne est récurrente positive et apériodique.b) On peut aussi démontrer que la moyenne du nombre des visites en xj ∈ S jusqu’au

temps n, donné par1

n

n∑

i=0

1xj(Xi),

converge en probabilité, quand n → ∞, vers πj pour tous xj ∈ S.


Pour une preuve du Théorème I.2 nous référons aux ouvrages suivants :– A.A. Borovkov. Probability theory. Gordon and Breach, 1998– W. Feller. An introduction to probability theory and its applications. Vol. 1. Wiley,

1970– V.G. Kulkarni. Modeling and analysis of stochastic systems. Chapman and Hall, 1995

II.2.2 Exemples en gestion, économie et imagerie

Nous terminons cette section par quelques exemples de lois stationnaires.

1) Considérons un marché où n produits A1, A2, ..., An sont en compétition les uns contreles autres. Supposons que les clients décident de rester fidèles à leur produit ou de changerde produit en tenant compte de la satisfaction ou de l’insatisfaction avec le produit utiliséà présent sans tenir compte des produits utilisés antérieurement (même comportement quela souris markovienne). L’évolution du comportement des clients (d’une semaine à l’autrepar exemple) est alors donné par la matrice de transition P . Notons que dans ce cas leséléments de la diagonale ne sont pas nécessairement 6= 0.P (m) décrit le marché après m semaines, et la loi stationnaire, si elle existe, donne l’étatd’équilibre du marché, duquel il va s’approcher de plus en plus.Nous référons aux exercices en TD pour d’autres exemples d’application en gestion.

2) La marche aléatoire avec réflexion aux bords. Considérons la marche aléatoire symétriquesur S = −N,−N + 1, ...,−1, 0, 1, ..., N − 1, N qui consiste à faire, à chaque instant, unpas en arrière ou en avant avec la probabilité 1

4 ou de rester sur place avec la probabilité 12 .

Aux bords, la marche repart avec probabilité 14 et reste sur place avec probabilité 3

4 . PourN = 5 par exemple, on a le graphe des probabilités ci-dessous.

-5 -4 -3 -2 -1 0 1 2 3 4 5

3/41/4 1/2

1/4 1/4

La matrice de transition est de dimension 2N + 1 et donnée par

P = (pij ; i, j ∈ S) =

34

14 0 ... 0 0 0

14

12

14 ... 0 0 0

... ... ... ... ... ... ...0 0 0 ... 1

412

14

0 0 0 ... 0 14

34

.

Pour toute loi initiale (par exemple départ du point 0), on peut calculer la loi de Xn àl’aide de la formule de probabilité totale

P (Xn = j) =

N∑

i=−N

P (X0 = i)p(n)ij (n ∈ N

∗)

La loi stationnaire est la loi uniforme sur S, πi = 12N+1 pour tous i ∈ S. Elle se calcule

à l’aide du Théorème II.2. La figure ci-dessous (G. Winkler : Image analysis, RandomFields and Markov Chain Monte Carlo Methods, Springer 2003) illustre cette convergence.Le point de départ est 0 (P(X0=0)=1) et N = 20. Le graphique en haut est un suivi de


trajectoires d’un grand nombre de réalisations (Xn ; n=0,1,...,600). Les histogrammes pourles instants n=0, 100 et 600 montrent bien la convergence vers la loi uniforme.

Un cadre concret pour ce type de chaîne de Markov est l’évolution du cours d’échangeentre deux monnaies. Le bord inférieur et le bord supérieur sont les points d’interventionsde l’autorité monétaire pour stabiliser le cours d’échange.

Histogrammes : répartitions des trajectoires de la chaîne aux instants n=0, 100 et 600

3) Le modèle d’Ising. Ici S est l’ensemble des configurations des points d’une grille G. Lesprobabilités de transition d’une configuration vers l’autre sont plus complexes dans cetexemple et se calculent à partir des probabilités conditionnelles calculées en section II.1.Plus précisément notons pi la probabilité de transition de la configuration du i-ème pointde G. Pour deux configurations ct = (cl

t)l∈G et ct+1 = (clt+1)l∈G, pi est donnée par

pi(ct, ct+1) = P (Xit+1 = ci

t+1| Xjt = cj

t pour tous j 6= i).

Cette probabilité se calcule à l’aide de la formule II.1 . La matrice de transition d’uneconfiguration (de tous les points de G) vers une autre est alors donnée par

P = (p(ct, ct+1), ct, ct+1 ∈ S) où p(ct, ct+1) =∏

i∈G

pi(ct, ct+1).

Notons que P est une matrice n×n, s’il y a n configurations possibles de G. Pour obtenir laprobabilité de transition d’une configuration ct vers une configuration ct+1 il faut calculerl’élément de P qui se trouve sur la ligne qui correspond à ct et dans la colonne qui correspondà ct+1. On peut démontrer que la matrice de transition d’ordre m est égale à Pm, et quela loi stationnaire pour le modèle de Ising (π(c), c ∈ S) est donnée par

π(c) =1

Zexp(−β

∑

i∼j

cicj) où Z =∑

c

exp(−β∑

i∼j

cicj),


la somme∑

c étant sur toutes les configurations possibles de G. A noter qu’il s’agit de laloi introduite en section II.1.Il se peut que la convergence vers la loi staionnaire est assez lente comme le montre laFigure 1 ci dessous. L’échelle sur l’axe vertical est la fréquence relative de points voisinsayant la même configuration, l’axe horizontal est le temps. A gauche se trouve “l’image”de départ avec un très grand nombre de voisins de configurations différentes. L’applicationrépétitive de P est censé “nettoyer l’image”, c’est-à-dire de s’apercevoir qu’il n’y a pas d’ob-jets réels, mais seulement des bruits (“noise” en anglais) qu’il faut supprimer. Ceci revient àdiminuer le nombre de voisins avec configurations différentes. Au cas où l’ image comportedes objets réels qui sont bruités, il faut choisir un algorithme qui supprime ces bruits sansfaire disparaître l’image de ces objets réels. La suite de la Figure 1 montre l’état de ce“nettoyage” après 150, 300 et 8000 applications (“sweeps” en anglais) de P . L’efficacité dunettoyage dépend fortement de la valeur de β. Pour la Figure 1β=0.8, pour la Figure 2β=0.43 et pour la Figure 3 β=1.0. Les carrés des Figures 2 et 3 montrent l’état du net-toyage après 0, 1, 3,10, 30, 100, 1000 et 3000 applications de P . A noter la différence entreles résultats du “nettoyage”. Les figures sont reproduites de : G. Winkler, Image Analysis,Random Fields and Markov Chain Monte Carlo Methods. Springer 2003. Nous remercionsl’auteur pour la permission de reproduire ces figures dans ce polycopié et référons à sonouvrage pour un traitement détaillé de la reconstitution d’images.

Figure 1. β = 0.8, n = 0, 150, 300, 8000

II.3. LES CHAÎNES DE MARKOV À TEMPS CONTINU 15

(a) (b) (c) (d)

(e) (f) (g) (h)

Figure 2. β = 0.43 n = 0, 1, 3, 10, 30, 100, 1000, 3000

(a) (b) (c) (d)

(e) (f) (g) (h)

Figure 3. β = 1.0 n = 0, 1, 3, 10, 30, 100, 1000, 3000

II.3 Les chaînes de Markov à temps continu

Dans beaucoup des cas on souhaite disposer de manière continue l’évolution temporelled’un système. On préfère alors considérer le temps comme étant une variable continue,prenant ses valeurs dans un intervalle I ⊆ R+ et des chaînes de Markov indexés par lespoints de I : (Xt; t ∈ I). Des exemples typiques sont le nombre d’appels arrivant à unservice de renseignements téléphonique en période [t, t + h], le nombre de tâches arrivant à


la partie centrale d’un ordinateur ou encore le nombre de machines qui tombent en panneet qui doivent être réparées en [t, t + h]. Ces exemples rentrent dans le cadre du schéma“clients/serveur” : les clients sont les personnes qui appellent, les tâches qui arrivent oules machines tombées en panne ; les serveurs sont le service de renseignements, l’ordinateurou le centre de réparation des machines. Du côté pratique on s’intéresse, entre autres, àla longueur de la file d’attente qui se forme devant les “guichets”, aux durées d’attente des“clients” ou au degré d’occupation des “serveurs”.

II.3.1 Intensités de transition et modèles linéaires

Soit I ⊆ R+ la période d’observation, et soit S l’ensemble des états possibles de lachaîne (S = xl; l ∈ J, J ⊆ N, fini ou non). Dans les exemples précédents les états sonttypiquement le nombre de “clients” présents (servis ou non) ou le nombre de “clients” enattente d’être servis. Notons Xt (t ∈ I) l’état de la chaîne à l’instant t, et notons

pij(h) = P (Xt+h = xj| Xt = xi) (xi, xj ∈ S, t, t + h ∈ I, h > 0)

les probabilités de transition, supposées stationnaires dans cette section, c’est-à-dire quepij(h) ne dépend pas de t. Ces probabilités de transition sont des fonctions de h, doncdes expressions plus complexes qu’en section II.2. Nous allons démontrer que les lois desXt (t ∈ I) sont déterminées uniquement par la loi initiale et les dérivées en h = 0 desprobabilités de transition. Ces dérivées remplacent donc les probabilités de transition deschaînes à temps discret dans le calcul des lois de Xt et de la loi stationnaire, si elle existe.Notons que :

ddh

pij(0) = limh→0

1

h(pij(h) − pij(0)) =

limh→01hpij(h) si i 6= j,

limh→01h(pii(h) − 1) si i = j.

(II.2)

De façon équivalente on peut écrire :

pij(h) = pij(0) + hd

dhpij(0) + σ(h) quand h → 0.

Ici σ(h) est une fonction de h, inconnue en général, tel que limh→01hσ(h) = 0. Notons aussi

que∑

j∈S pij(h) = 1, et donc∑

j∈Sddhpij(h) = 0 pour tous i ∈ S. Les dérivées s’inter-

prètent comme les intensités d’un saut de xi vers xj dans une période (infinitésimalement)courte. Nous traitons dans cette section le cas où seules les intensités d’un saut vers un desvoisins dans S sont positives. Dans le cadre du schéma “clients/serveur” ceci signifie qu’ilest peu probable que deux ou plusieurs clients arrivent en même temps : soit que la chaînereste en l’état i, soit qu’elle passe à l’état (i + 1) (un client est arrivé), soit qu’elle passe àl’état (i − 1) (un client est servi et part).

Définition. Une chaîne de Markov (Xt; t ∈ I) à valeur dans S ⊆ N est linéaire (ou unprocessus de naissance et de mort) si, pour tous i, j ∈ S et t, t + h ∈ I

pij(h) = P (Xt+h = j| Xt = i) =

λih + σ(h) si j = i + 1µih + σ(h) si j = i − 11 − (λi + µi)h + σ(h) si i = jσ(h) si |i − j| > 2

quand h → 0. D’après (II.2), λi = ddhpi,i+1(0) et µi = d

dhpi,i−1(0). λi (resp. µi) sont lesintensités (ou taux) de naissance (resp. de mort) à l’état i ∈ S. Leurs valeurs sont sup-posées données ou estimables à partir de l’observation de la chaîne. Pour S = N on a lareprésentation graphique suivante :


0 1 2 3λ0 λ1 λ2

µ1µ2 µ3

λ2 µ2 λ3 µ3

λ0λ1 µ1

λn µn, 0

II.3.2 Le processus de Poisson

(Denis Poisson, mathématicien français, 1781-1840)

Considérons la chaîne de Markov linéaire avec S = N, λi = λ > 0 et µi = 0 pour tousi ∈ N. Supposons que X0 = 0. Les probabilités de transition sont données par :

pii(h) = (1 − λ)h + σ(h), pi,i+1(h) = λh + σ(h) quand h → 0.

Quelle est la loi de Xt, pour t > 0 ? Posons pi(t) = P (Xt = i) (i ∈ S). Nous déterminonsles valeurs de pi(t) récursivement, en commençant par i = 0, et nous allons voir que les Xt

suivent la loi de Poisson avec paramètre λt, c’est-à-dire que pi(t) = (λt)i

i! e−λt (t > 0, i ∈ N).

i = 0 :

p0(t + h) = P (Xt+h = 0) = P (Xt+h = 0| Xt = 0)P (Xt = 0)

= p00(h)p0(t) = (1 − λh + σ(h))p0(t) pour h → 0.

Donc p0(t + h) − p0(t) = −(λh + σ(h))p0(t) pour h → 0.

Donc ddtp0(t) = limh→0

1h(p0(t + h) − p0(t)) = −λp0(t), p0(0) = 1.

D’où ddtp0(t) = −λp0(t), p0(0) = 1.

La solution de cette équation différentielle est donnée par p0(t) = e−λt. Il s’agit bien de laprobabilité en i = 0 de la loi de Poisson de paramètre λt.

Cas général : On procède par induction. On suppose que pi−1(t) = (λt)i−1

(i−1)! e−λt, et onsouhaite démontrer que la formule reste valable si i − 1 est remplacé par i.

pi(t + h) = P (Xt+h = i) = P (Xt+h = i, Xt = i) + P (Xt+h = i, Xt = i − 1)

= P (Xt+h = i| Xt = i)P (Xt = i) + P (Xt+h = i| Xt = i − 1)P (Xt−1 = i − 1)

= pii(h)pi(t) + pi−1,i(h)pi−1(t)

= (1 − λh + σ(h)) pi(t) + (λh + σ(h)) pi−1(t) quand h → 0.

Doncddt

pi(t) = −λpi(t) + λpi−1(t) = −λpi(t) + λ(λi−1

(i − 1)!e−λt), pi(0) = 0.

On vérifie facilement que pi(t) = (λt)i

i! e−λt est solution de cette équation différentielle.


Les trajectoires (temporelles) de ce processus sont donc des fonctions en escalier, avec desmarches (arrivée de clients) à des instants aléatoires, notés T1, T2,... On pose T0 = 0. Ona donc

Xt > n ⇔ Tn 6 t pour n ∈ N∗, t > 0.

0

1

2

3

4

5

Xt

T1 T2 T3 T4

t

Le théorème suivant résume le résultat obtenu ci-dessus, et donne les propriétés les plusimportantes du processus de Poisson.

Théorème II.3. Les caractérisations suivantes sont équivalentes pour le processus de Pois-son (Xt; t > 0) d’intensité λ > 0 issu de zéro.

a) (Xt; t > 0) est une chaîne de Markov linéaire à valeur dans N et d’intensité λi =λ > 0 et µi = 0 (i ∈ N).

b) pour tous s, t > 0, s < t et tous i ∈ N on a :

P (Xt − Xs = i) = P (Xt−s = i) =[λ(t − s)]i

i!e−λ(t−s), (II.3)

et les accroissements sur des intervalles disjoints sont indépendants, c’est-à-dire que,pour tous n ∈ N

∗ et tous 0 6 t0 < t1 < t2 < ... < tn,

Xt1 − Xt0 ,Xt2 − Xt1 , ...,Xtn − Xtn−1, (II.4)

sont des variables aléatoires indépendantes.

Remarque. La première égalité en (II.3) dit que la loi des accroissements Xt − Xs nedépend que de la longueur t − s de l’intervalle [s, t], mais pas de sa position. On ditque les accroissements sont stationnaires et par (II.4), indépendants. Une autre propriétéimportante du processus de Poisson est le fait que les temps d’attente entre deux sautsUi = Ti − Ti−1 (i ∈ N

∗) sont des variables aléatoires indépendantes et que Ui suit la loiexponentielle de paramètre λ ; c’est-à-dire que la fonction de répartition des Ui est donnéepar P (Ui 6 x) = 1 − exp(−λx)1R+

(x).

La propriété de Markov du processus de Poisson se traduit donc par l’absence d’unemémoire pour les temps d’attente entre deux sauts. On a en fait

P (Un > x + y| Un > x) =P (Un > x + y)

P (Un > x)=

e−λ(x+y)

e−λx= e−λy = P (Un > y).


C’est-à-dire que la probabilité d’attendre au moins x+y unités de temps jusqu’au prochainsaut ne dépend pas du fait que cette attente dure déjà x unités de temps. Elle est simplementégale la probabilité (inconditionnelle) que l’attente dure au moins y unités du temps aprèsx.Notons que EUn = 1

λ , et que V ar Un = 1λ2 , tandis que EXt = V ar Xt = λt.

Remarque. La démonstration complète de l’équivalence de a) et b) du Théorème précé-dent et de la loi exponentielle de Ui exige une analyse plus fine du processus de Poissonqui n’est pas le but de ce cours.

II.3.3 La loi stationnaire dans le cas où l’ensemble des états possibles

est fini

Nous étudions maintenant le cas où S = 1, 2, .., n. Soit (Xt; t > 0) une chaîne deMarkov linéaire et à valeurs dans S. Sa fonction de transition (à valeur matrices) est donnéepar P (t) = (pij(t), i, j ∈ S), où pij(t) = P (Xs+t = j| Xs = i) et t varie dans R+. Leségalités de Chapman-Kolmogorov (Proposition II.1) restent valables en temps continu etse lisent de façon suivante :

P (t + s) = P (t)P (s) pour tous t, s > 0.

Elles n’ont cependant pas la même importance qu’en temps discret, où l’égalité P (n) = Pn

permet le calcul direct de la loi de Xn. En temps continu, le calcul de P (t), de la loi Xt

et de la loi stationnaire est plus compliqué en général. Il faut procéder de même façon quepour le processus de Poisson et résoudre des systèmes d’équations différentielles pas trèssimples en général. Nous nous contentons ici de poser ce système d’équations différentielleset d’en déduire une formule explicite pour la loi stationnaire qui sera la formule de basepour les files d’attente. Le graphe des intensités de transition facilite la compréhension deces équations différentielles.

0 1 2 nλ0 λ1

µ1µ2

λ2 µ2

λ0λ1 µ1

n-1

λn-1

µn-1

µn

λn-1

µn

En appliquant l’inégalité de Chapman-Kolmogorov on déduit du graphe ci-dessus :

pj(t + h) = P (Xt+h = j) =∑

i∈S

P (Xt = i)P (Xt+h = j| Xt = i) =∑

i∈S

pij(h)pi(t)

= pj(t)(1 − λjh − µjh + σ(h)) + pj−1(t)(λj−1h + σ(h))

+ pj+1(t)(µj+1h + σ(h)) + σ(h) quand h → 0

Donc

d

dtpj(t) = lim

h→0

1

h(pj(t + h) − pj(t))

= −(λj + µj)pj(t) + λj−1pj−1(t) + µj+1pj+1(t) 1 6 j 6 n − 1

En tenant compte des particularités aux états 0 et n on obtient le système d’équationsdifférentielles suivant :


Proposition II.4. Soit (Xt; t > 0) une chaîne de Markov linéaire à valeurs dans S =0, 1, .., n. La loi de Xt pour tous t > 0 est alors donnée par la loi X0 (pj(0) = P (X0 =j), j ∈ S) et la solution du système suivant d’équations différentielles :

ddtpj(t) = −(λj + µj)pj(t) + λj−1pj−1(t) + µj+1pj+1(t) 1 6 j 6 n − 1,ddtp0(t) = −λ0p0(t) + µ1p1(t),ddtpn(t) = −µnpn(t) + λn−1pn−1(t).

(II.5)

La loi stationnaire de (Xt, t > 0) se déduit facilement de la proposition précédente.

Théorème II.5. Soit (Xt; t > 0) une chaîne de Markov linéaire à valeurs dans S =0, 1, 2, .., n. Supposons que λi > 0 pour i = 0, 1, 2, ..., n − 1 et µi > 0 pour i = 1, 2, ..., n.La loi stationnaire (c’est-à-dire la loi associée aux valeurs supposées données de λi et µi

et valable pour tous t > 0) est donnée par

pl = P (Xt = l) =Πl

j=1λj−1

µj

∑ni=0 Πi

j=1λj−1

µj

(l ∈ S, t ∈ I). (II.6)

Remarque. a) Dans le dénominateur de la formule ci-dessus on obtient pour i = 0 leproduit Π0

j=1... Il faut le poser égal à 1.b) L’exemple du processus de Poisson montre que la loi stationnaire n’existe pas toujourssi S est infini. Les files d’attente que l’on va traiter ci-dessous montrent cependant qu’elleexiste sous certaines conditions même si S est infini.

Preuve du Théorème II.5 : Sous le régime stationnaire les probabilités pij(t) (j ∈S, t ∈ I) ne dépendent pas de t. Le système d’équations différentielles de la PropositionII.4 devient donc un système d’équations pour les inconnues pj, j ∈ S. Il se lit :

λ0p0 = µ1p1

(λj + µj)pj = λj−1pj−1 + µj+1pj+1 (1 6 j 6 n − 1)

λn−1pn−1 = µnpn

Comme ce système est linéaire, on peut le résoudre facilement de la façon suivante :

p1 =λ0

µ1p0, p2 =

1

µ2[(λ1 + µ1)p1 − λ0p0] =

λ0λ1

µ1µ2p0, ...

pn = Πnj=1

λj

µjp0.

Comme∑n

j=0 pj = 1, on obtient p0(∑n

i=0 Πij=1

λj−1

µj) = 1, et donc p0 = (

∑ni=0 Πi

j=1λj−1

µj)−1.

Il s’ensuit que p1,..pn se calculent d’après la formule du Théorème.

II.3.4 Un exemple en gestion

Considérons n machines de même type. PosonsXi la durée aléatoire de fonctionnement de la machine i entre deux tombées en pannesuccessives,Y la durée aléatoire de réparation d’une machine.Comme les machines sont du même type, on peut supposer que les variables aléatoiresXi suivent la même loi. Supposons aussi que les variables aléatoires Xi et Y sont indépen-dantes, que Xi suit la loi exponentielle de paramètre λ > 0 et que Y suit la loi exponentielle


de paramètre µ > 02. Les machines qui tombent en panne sont réparées l’une après l’autre.Notons Zt le nombre de machines en panne à l’instant t. On s’intéresse à la loi stationnairede Zt, c’est-à-dire aux probabilités pl = P (Zt = l) pour l = 1, ..., n. Pour calculer cette loion modélise (Zt, t > 0) comme une chaîne de Markov linéaire, les “naissances” étant lesmachines qui tombent en panne, les “morts” étant les machines qui sont remises en serviceaprès réparation. Sous les hypothèses faites sur Xi et Y on voit facilement que (Zt; t ≥ 0)est effectivement une chaîne de Markov. Il faut calculer les taux de “naissances” et les tauxde “morts”, et appliquer le Théorème II.5. Posons S = 0, 1, 2, .., n. Pour calculer µj onpose

µj =d

dhpj,j−1(0) = lim

h→0

1

hpj,j−1(h) = lim

h→0

1

hP (Zt+h = j − 1| Zt = j).

Pour h très petit il faut donc calculer la probabilité qu’une machine sort de réparation en]t,t + h]. Supposons qu’à l’instant t la réparation dure déjà t′ unités de temps. On a alors

P (Zt+h = j − 1| Zt = j) = P (Y 6 t′ + h| Y > t′) =P (t′ < Y 6 t′ + h)

P (Y > t′)

=e−µt′ − e−µ(t′+h)

e−µt′= 1 − e−µh.

Donc µj = limh→01h(1 − e−µh) = µ pour j = 1, 2, .., n. Remarquons que, d’après le Théo-

rème II.3, le nombre de machines réparées est un processus de Poisson avec intensité égaleà µ.Calcul de λj (j = 0, 1, ..., n − 1) :

λj =d

dhpj,j+1(0) = lim

h→0

1

hP (Zt+h = j + 1| Zt = j)

Pour h très petit il faut donc calculer la probabilité qu’une machine tombe en panne en]t,t + h]. Numérotons de 1 à n − j les machines en service à l’instant t.

P (Zt+h = j + 1|Zt = j) = P (∃ l ∈ 1, ..., n − j tel que Xl ∈]t − t′l, t + h − t′l]| Xl > t − t′l)

(t′l est l’instant de la remise en service actuelle de la machine l)

= 1 − P (Xl > t + h − t′l pour tous l ∈ 1, .., n − j| Xl > t − t′l)

= 1 − Πn−jl=1 P (Xl > t + h − t′l| Xl > t − t′l) = 1 − Πn−j

l=1 P (Xl > h)

d’après la remarque qui suit le Théorème II.3. Donc

λj = limh→0

1

h(1 − Πn−j

l=1 P (Xl > h)) = limh→0

1

h(1 − e−(n−j)λh) = (n − j)λ.

Le graphe des taux de naissances et de morts pour (Zt; t > 0) est donc le suivant :

0 1 2

µ µ µ

j n

µ−λn −λ (n-1)−µ −λ(n-2)−µ −λ(n-j) −µ

λn λ(n-1) λ(n-2) λ (n-j)

µ

2Ces dernières hypothèses peuvent bien sûr ne pas être satisfaites dans un cas concret. Elles figurent icipour que les calculs qui suivent restent simples.


En appliquant le Théorème II.5, on obtient la loi stationnaire de Z :

pl = P (Zt = l) = Πlj=1

λ(n − j + 1)

µ/(

n∑

i=0

Πij=1

λ(n − j + 1)

µ)

= (λ

µ)l

1

(n − l)!/(

n∑

i=0

(λ

µ)i

1

(n − j)!) l ∈ 0, 1, ..., n.

II.3.5 Les files d’attente M/M/s/R

Les files d’attente sont des cas particuliers des chaînes de Markov linéaires. On les noted’habitude par M/M/s/R, où

M/M signifie que les arrivées se font selon un processus de Poisson d’intensité donnée(notée λ > 0). Par la remarque qui suit le Théorème II.3 les temps d’attente entredeux arrivées successives sont indépendants et suivent la loi exponentielle de para-mètre λ.Le deuxième M signifie que les durées de services suivent la loi exponentielle d’unparamètre donné (noté µ > 0), et que ces durées de services sont indépendantes. Lenombre de services effectués au cours de la période ]t, t+h] suit donc la loi de Poissond’intensité sµ, où

s est le nombre de serveurs,R est le nombre maximal de clients dans le système (en train d’être servi ou en attente

d’un service). Remarquons que R 6 ∞.

Exemple : Une banque avec s guichets, où la porte d’entrée ne s’ouvre plus dès qu’il y aR clients à l’intérieur de la banque. Remarquons que le nombre de guichets ouverts peutvarier selon l’intensité des arrivées des clients.

On s’intéresse en général aux nombres de clients en file d’attente en fonction du taux desarrivées, du nombre de serveurs et de la durée de service. On s’intéresse aussi à la duréed’attente et à la durée totale de présence d’un client dans le système. Nous allons répondreaux questions à l’aide d’une chaîne de Markov linéaire de taux constant, noté λ, des arri-vées des clients et de taux de départ des clients servis, noté µ, dépendant uniquement de s.Remarquons que d’autres modèles sans la restriction que les taux d’arrivées et de départssont constants peuvent être déduits du Théorème II.5, mais les formules répondant auxquestions ci-dessus sont alors plus compliquées ou inconnues. Dans certains cas, il faut secontenter d’approximations.

Notations :S = 0, 1, ..., RXt ∈ S (t > 0) nombre de clients présents dans le système à l’instant t en file d’attente ouen train d’ètre servispl = P (Xt = l), l ∈ S loi stationnaire de (Xt; t > 0) si elle existe

NS = EXt =∑

l∈S

pll

NW = E(Xt − s)+ =∑

l∈S

pl(l − s)+

Nombre moyen de clients pré-sents dans le système (NS) oudans la file d’attente (NW )

TS (resp. TW ) durée moyenne qu’un client passe dans le système (resp. dans la file d’attente)


Les quantités NS , NW , TS et TW sont calculées sous la loi stationnaire.

a) La file d’attente M/M/1/R (R 6 ∞)

Le graphe des taux des arrivées et des départs est le suivant :

0 1 2

µ µ µ

R

µ−λ

λ λ λ λ

µ

R-1

−λ−µ−λ−µ−λ−µ

Si R = +∞ la loi stationnaire existe si et seulement si λ < µ.Les formules ci-dessous pour pl sont une conséquence du Théorème II.5, appliqué à n = Ret λj = λ, µj = µ.Si R = +∞ les formules suivantes sont valables :

pl = ρl(1 − ρ) , l ∈ N, ρ = λ/µ < 1

NS =ρ

1 − ρ=

λ

µ − λ, NW = NS − ρ =

λ2

(µ − λ)µ

TS =1

λNS =

1

µ − λ, TW =

1

λNW =

λ

(µ − λ)µ

Si R < +∞ les formules suivantes sont valables :

pl = ρl(1−ρ)1−ρR+1 , l ∈ 0, 1, ..., R, ρ = λ/µ, λ 6= µ

NS = ρ[1−(R+1)ρR+RρR+1](1−ρR+1)(1−ρ)

, λ 6= µ, NW = NS − (1 − p0)

TS = NS

λ(1−pR) , TW = NW

λ(1−pR)

Remarquons que pl = 1R+1 (l = 0, 1, .., R) si λ = µ et R < ∞. Il s’agit donc de la

loi uniforme sur S. Les formules pour TS et TW sont connues sous le nom de formules deLittle. Pour une démonstration de ces formules, nous référons au livre de K. Borovkov :Elements of stochastic modelling. World Scientific 2003.

b) La file d’attente M/M/s/R (R 6 ∞)

Iciλj = λ (j = 0, 1, ..., R − 1)

µj =

jµ si 1 6 j 6 ssµ si j > s (j = 1, 2, ..., R)

Le graphe des taux des arrivées et des départs est le suivant :


0 1 2 R

−λ

λ λ λ λ

R-1

−λ−µ

µsµsµs

−λ−2µ

S-1 S

λ

µ

−λ-(s-1) µ

µ(s-1)

−λ-sµ −λ-sµ -sµ

µ2

Si R = +∞ la loi stationnaire existe si et seulement si λ < sµ. P (Xt > s) est laprobabilité que tous les serveurs sont occupés. Les formules ci-dessous pour pl sont uneconséquence du Théorème II.5. Pour s = 1 on retrouve les formules de la partie a).

Si R = +∞ les formules suivantes sont valables :

pl =

ρlp0

l! si l 6 s − 1, l ∈ N, ρ = λ/µ < s

ρlp0

sl−ss!si l > s

p0 = [s−1∑

i=0

ρi

i!+

ρs

(1 − ρ/s)s!]−1, P (Xt > s) =

ρsp0

(1 − ρ/s)s!

NW =ρ

s(1 − ρ/s)P (Xt > s), Ns = NW + ρ, TW =

NW

λ, TS =

NS

λ

Si R < +∞ les formules suivantes sont valables :

pl =

ρlp0

l! si l 6 s − 1ρlp0

sl−ss!si s 6 l 6 R

p0 = [

s−1∑

i=0

ρi

i!+

ρs

s!

R−s∑

i=0

ρi

si]−1

NW =ρsp0

(1 − ρ/s)2s!

ρ

s[1 − (

ρ

s)R−s+1 − (R − s + 1)(

ρ

s)R−s(1 − ρ

s)]

NS = NW +

s−1∑

i=0

ipi + s(1 −s−1∑

i=0

pi), TW =NW

λ(1 − pR), TS =

NS

λ(1 − pR)

II.4 Simulation de files d’attente

Souvent les systèmes à étudier sont trop complexes pour une analyse à l’aide des for-mules proposées en section II.2 et II.3. Il existe des formules plus ou moins explicites pourcertains cas plus généraux, et des travaux de recherche motivés par les applications ré-centes, par exemple en réseaux de télécommunication, ont été effectués. Dans d’autres cason est amené à effectuer des simulations sur ordinateur pour apprendre d’avantage surl’évolution temporelle d’un système.

Exemple : Bilan économique d’une compagnie d’aviation.Considérons une compagnie aérienne qui dispose de 10 avions. Supposons qu’il en faut 8pour assurer l’ensemble des vols quotidiens sous sa responsabilité. Les avions sont soit en

II.4. SIMULATION DE FILES D’ATTENTE 25

état de service (noté N), soit en attente d’être réparés (A), soit en réparation (R), soit enétat d’attente pour mise en service (S). Supposons aussi qu’il y a trois postes de réparationà disposition. On peut alors décrire le flux des avions d’un état vers le suivant par le schémasuivant :

S

N

A

R

Les surfaces hachurées correspondent à l’état initial du système : 6 avions en service, 1avion en attente, 3 en réparation.Supposons que les durées entre 2 instants successifs qu’un avion tombe en panne sont desvariables aléatoires indépendantes qui suivent une loi exponentielle de paramètre λ > 0(hypothèse à vérifier statistiquement à partir d’observations, avec l’estimation de λ). Sup-posons aussi que les durées entre deux instants successifs qu’un avion sort de réparationsont, elles aussi, indépendantes et de loi exponentielle de paramètre µ > 0 (hypothèse àvérifier également, avec estimation de µ).Il y a donc deux files d’attente, une pour les postes de réparation (il s’agit d’une M/M/3/10),et l’autre les mises en service (il s’agit d’une M/M/8/10). Les arrivées aux deux files d’at-tente se font selon des processus de Poisson de paramètres λ resp. µ. Mais les deux processusne sont pas indépendants, parce que les départs de l’une des files d’attente sont les arrivéesà l’autre file d’attente. Les formules de la section II.3.5 ne sont donc pas applicables.Le but dans cet exemple est de faire des prévisions sur le bilan économique de la sociétéd’aviation. Il faut donc des informations sur l’évolution probable des états des avions pen-dant une certaine période. Dans cet exemple, il convient de simuler la loi de (St, Nt, At, Rt)quand le temps t parcourt la durée [0,T]. Il faut donc simuler des réalisations de variablesaléatoires exponentielles de paramètres λ et µ qui interviennent dans les deux files d’at-tente. Ce sera fait dans les deux sous-sections qui suivent et on poursuivra l’étude de lacompagnie d’aviation dans le dernier paragraphe.

II.4.1 Simulation d’une variable aléatoire de loi donnée

Théorème II.6. Soit X une variable aléatoire de fonction de répartition F continue don-née. Alors Y = F (X) suit la loi uniforme sur [0,1].

Preuve. Notons FY la fonction de répartition de Y . Alors, pour y ∈ [0, 1],FY (y) = P (Y 6 y) = P (F (X) 6 y) = P (X 6 F−1(y)) = F (F−1(y)) = y,et FY = 0 si y < 0 et FY = 1 si y > 1. Remarquons que F−1 est définie telle queF−1(y) = infx : F (x) = y.


1

0

y

x

F(x)

x=F (y)-1

Remarque. L’exemple suivant montre comment le Théorème permet de simuler de va-riables aléatoires de loi F à partir de réalisations indépendantes de loi uniforme sur [0,1].On verra dans la sous-section suivante comment on peut obtenir ces derniers en simulantdes chiffres pseudo-aléatoires.

Exemple : Simulation de réalisations de variables aléatoires de loi exponentielle de para-mètre λ donné.Choisissons λ = 3/heure la fréquence des arrivées dans une file d’attente.La fonction de répartition de cette loi est donnée par

y = F (x) = (1 − e−λx) 1R+(x)

Donc

x = − 1

λln(1 − y) = −1

3ln(1 − y) [heures] = −20 ln(1 − y) [minutes].

Comme Y et 1 − Y ont même loi, on peut remplacer x par x′ = −20ln(y) [minutes]. Parle Théorème I.6 x est une réalisation de la loi F donnée si y est une réalisation de la loiuniforme sur [0, 1].Supposons donnés les chiffres aléatoires suivants :

57494 72484 22676Ils donnent lieu aux réalisations suivantes de la loi uniforme sur [0,1] :

y1 = 0,57494 y2 = 0,72484 y3 = 0,22676On en déduit les valeurs suivantes de x′ :

x′1 = 11,0698 x′

2 = 6,4361 x′3 = 29,6773

Les valeurs x1, x′2 et x′

3 sont donc des réalisations de la loi exponentielle de paramètreλ = 3/heure = 20/minute. Avec ces simulations on peut effectuer des évaluations statis-tiques comme s’il s’agissait d’observations réelles.

La simulation de réalisations de variables aléatoires de loi discrète est différente et illustréepar l’exemple suivant. Considérons la loi F donnée ci-dessous : elle réalise 4 valeurs avecles probabilités p1,p2,p3,p4 (

∑4i=1 pi = 1). Supposons données les réalisations y1,y2 de loi

uniforme sur [0,1]. On en déduit les réalisations x1 = F−1(y1) et x2 = F−1(y2) de F suivantle graphique ci-dessous :


F(x)

x = F (y ) 1 1-1 x = F (y ) 2 2

-1

y1

O

P1

P2

P3

P4

1

y2

Remarquons que l’on a F (F−1(y)) 6= y en général au cas où F est discrète.

II.4.2 Générateur de nombres pseudo-aléatoires

Si on a besoin d’un grand nombre de réalisations de variables aléatoires de la loi uniformesur [0,1] il faut les générer à l’aide d’un algorithme convenable. Ceci est précisé dans ladéfinition suivante.

Définition. Un générateur de nombres pseudo-aléatoire (GNPA) est un algorithme quigénère des suites de chiffres y1, y2,...,yn, quel que soit n ∈ N

∗, tel que le comportement sta-tistique de ces suites est celui d’une suite Y1, Y2,...,Yn de variables aléatoires indépendantesde loi uniforme sur [0,1].

Définition. Soient a, b, n ∈ N et n premier. Un GNPA congruentiel linéaire est donné parla valeur initiale, notée y0, et par la formule récursive pour yi

yi = (ayi−1 + b) (mod n) i = 1, 2, ...

Remarque. On a évidemment yi ∈ 0, 1, 2, ..., n − 1. Pour obtenir des réalisations indé-pendantes d’une variable de loi uniforme sur [0,1], il suffit de fixer la précision r souhaitée,de choisir r chiffres consécutives de yi et de les identifier aux r premières décimales d’unnombre de [0,1].

Le choix de a, b et n est crucial pour la qualité d’un GNPA, comme le montrent les exemplessuivants :

Exemple 1 : a=13, n=7, b=0. Soit y0=29. On obtienty1= 377 (mod 7) = 6, y2 = 78 (mod 7) = 1, y3 = 13 (mod 7) = 6.On obtient donc y2i−1=6, y2i=1, i=1,2,... On a donc généré la suite 296161616 qui n’estcertainement pas une bonne suite de chiffres pseudo-aléatoires.

Exemple 2 : a=3, n=100, b=0. Soit y0=13.La suite de nombres générés par ce GNPA est périodique de période 20, c’est-à-dire queyi = yi(mod 20). Les 20 premiers nombres générés par cet algorithme sont les suivants :39 17 51 53 59 77 31 93 79 37 11 33 99 97 91 73 19 57 71 13En répétant cette suite de nombres on obtient une suite qui n’est évidemment pas utilisablepour créer des réalisations indépendantes de loi uniforme sur [0,1] parce que la période estbeaucoup trop courte. Ceci est illustré par le fait que l’ensemble des couples (y2i−1/100,y2i/100) (n ∈ N) représentent 10 points seulement situés sur 3 droites dans [0,1]2.


0

1

1

Exemple 3 : Un bon choix de a, b et n est :a = 216 + 3 = 65539 ou a = 2100005341 et n = 231 − 1 = 2147483647, b = 0.La justification de ce choix estd’une part algébrique : il faut que la période des nombres générés soit extrêmement longue,etd’autre par statistique : les tests pour l’indépendance et de la loi uniforme sur [0,1] nedoivent pas indiquer des différences significatives.La qualité du GNPA avec a = 216 +3 et n = 231−1 est illustré ci-dessous par la trajectoirequi trace l’ordre de succession des cents premiers points (y2i−1/(231 − 1),y2i/(231 − 1))générés ; ils sont répartis de façon très irrégulière dans [0,1]2.

Y

X

0.0000

0.1000

0.2000

0.3000

0.4000

0.5000

0.6000

0.7000

0.8000

0.9000

1.0000

0.0000 0.2000 0.4000 0.6000 0.8000 1.0000

Voici un exemple de code Scilab3 pour générer les 100 premiers points par cette méthode.3http ://scilabsoft.inria.fr/


format(20,20) ;fd1=mopen("fichier.data","w") ;a=2∧16+3 ;n=2∧31-1 ;b0=a ;for i = 1 :100b1=pmodulo(b0*a,n) ;mfprintf (fd1,’%5.3f %5.3f \n’,b0/n,b1/n) ;b0=b1 ;

endmclose(fd1) ;

Pour visualiser ces résultats, une possibilité : xgraphxgraph -x Y2-1 -y Y2 -bb -nl -M fichier.dataxgraph -x Y2-1 -y Y2 -bb fichier.data

Il faut cependant dire que, quelle que soit la valeur de a, n et b, les points (y2i−1/n,y2i/n)sont toujours situés sur un nombre fini de droites dans [0,1]2. Plus généralement les points(Yi/n,Yi+1/n,...,Yi+p−1/n), i ∈ N

∗ seront toujours situés sur un nombre fini d’hyperplansde dimension p − 1 dans [0,1]p. Cependant ce nombre est très élevé pour les bons GNPA.Mais il est majoré par (p!n)1/p. Pour l’exemple 3 et p = 2 on obtient

√2n = 65535 droites.

Nous terminons cette sous-section par des tests statistiques pour la loi uniforme sur [0,1]et pour l’indépendance des nombres pseudo-aléatoires.

a)Test de validité d’ajustementIl permet de tester la répartition uniforme des nombres pseudo-aléatoires sur [0,1]. Onaligne les chiffres cj ∈ 0, 1, ..., 9 générés par les yi, i = 1, ..., nSoit Xl le nombre de chiffres égaux à l (l=0,1,...,9)Hypothèse H0 : X = (X0,X1, ...,X9) suit la loi multinomiale de paramètres (n, 1

10 , 110 , ..., 1

10 )

Variable de test : χ2 =

9∑

l=0

(Xl −n

10)2/

n

10=

10

n

9∑

l=0

(Xl −n

10)2

Notons que n =

9∑

l=0

Xl.

Il faut rejeter H0 si χ2 > χ2(9)1−α, où χ2(9) est la loi de Khi-deux avec 9 degrés de liberté,α est la probabilité d’une erreur de 1ère espèce et χ2(9) est l’extrémité gauche de l’intervallequi porte la probabilité α (hachurée dans la figure ci-dessous).

χ2

(9)χ21−α

(9)χ2Fonction de densite de

0


b) Test d’indépendance des observationsSoit c1, c2, ..., cn, la suite définie en partie a).Hypothèse H0 : C1, C2, ..., Cn, sont des variables aléatoires indépendantes uniformémentréparties sur 0,1,...,9Variable de test : On calcule le nombre rn de soussuites croissantes ou décroissantes dec1, c2, ..., cn.Exemple numérique :

39786 47879 45786 97125 83237n = 25 r25 = 15

0.0000

1.0000

2.0000

3.0000

4.0000

5.0000

6.0000

7.0000

8.0000

9.0000

5.0000 10.0000 15.0000 20.0000 25.0000

Sous H0 on a ERn = 13(2n − 1) et V ar Rn = 1

90(16n − 29). En plusZn := (Rn − ERn)/

√V ar Rn suit, asymptotiquement, quand n → ∞, la loi normale

centrée réduite, notée N (0, 1).Il faut rejeter H0, si |zn| > z1−α/2, où α est la probabilité d’une erreur de 1re espèce etz1−α/2 est l’extrémité gauche de l’intervalle qui porte la probabilité α/2 (hachurée dans lafigure ci-dessous).

Fonction densité de N (0, 1)

α/2 α/2

-z1−α/2 z 1−α/2

z


II.4.3 Un exemple de gestion

On retourne a l’exemple du bilan de la compagnie d’aviation. Supposons que λ=0.4et µ=0.7. On peut simuler des réalisations de variables aléatoires de loi uniforme sur [0,1]suivant la sous-section II.4.2 et en déduire des réalisations indépendantes des variablesaléatoires de loi exponentielle de paramètres λ et µ suivant la sous-section II.4.1.Supposons qu’on arrive de cette façon aux réalisations suivantes :Loi exponentielle de paramètre λ=0.4 :

5.86 0.06 2.16 1.18 3.09 1.94 3.88 6.17 11.56Loi exponentielle de paramètre µ=0.7 :

0.69 3.02 1.80 3.96 6.14 0.89 0.89 8.61 0.31A l’aide de ces valeurs on peut simuler l’évolution temporelle de la compagnie d’aviationsuivant le schéma donné à la page 25. Le tableau ci-dessous retrace les événements qui seproduisent durant les 20 premières unités temporelles. Ces événements débutent par desmises en service d’un avion aux instants 0.69, 3.71 (=0.69+3.02), 5.51 (3.71+1.80), quisont suivies par des pannes aux instants 5.86, 5.92 (=5.86+0.06) etc. Aux instants de cesévènements on observe les valeurs de S,N ,A et R, notées S(t), N(t), A(t) et R(t).

t S(t) N(t) A(t) R(t)

0 0 6 1 30.69 0 7 0 33.71 0 8 0 25.51 1 8 0 15.86 0 8 0 25.92 0 7 0 38.08 0 6 1 39.26 0 5 2 39.47 0 6 1 3

t S(t) N(t) A(t) R(t)

12.35 0 5 2 314.29 0 4 3 315.61 0 5 2 316.50 0 6 1 317.39 0 7 0 318.17 0 6 1 324.34

Afin de ne pas alourdir les calculs, on considère uniquement les quantités suivantes (pourune unité temporelle) :

m le coût fixe d’un avion, quel que soit son état,b le bénéfice d’un avion en service,c le coût de réparation d’un avion.

Le bénéfice de la compagnie d’aviation pour une durée de T unités temporelles, noté B(T ),est alors égal à :

B(T ) = b

∫ T

0N(t)dt − c

∫ T

0R(t)dt − 10mT.

Les graphes des fonctions N(t) et R(t) (0 6 t 6 20), donnés ci-dessous permettent de cal-culer facilement B(T ) pour T = 20. On obtient

∫ 200 N(t)dt = 124.7 et

∫ 200 R(t)dt = 57.23

et donc B(20) = −88.5, c’est-à-dire un déficit de 88.5. En partant avec d’autres valeurssimulées des lois exponentielles on arrive évidemment à valeurs différentes de B(20). B(20)a donc le caractère d’une variable aléatoire, et des simulations répétitives mènent à desréalisations indépendantes de B(20), auxquelles on peut appliquer une analyse statistique,comme s’il s’agissait d’un échantillon d’observations réelles (calculer sa moyenne, la va-riance, estimer la loi par l’histogramme de l’échantillon etc.).


t1.0000

2.0000

3.0000

4.0000

5.0000

6.0000

7.0000

8.0000

0.0000 5.0000 10.0000 15.0000 20.0000 25.0000

Nt

Rt

II.5 Remarques bibliographiques

Dans la plupart les livres de probabilités et processus stochastiques on trouve des cha-pitres sur les chaînes de Markov. Parmi les livres qui s’adressent plus particulièrement auxinformaticiens et aux ingénieurs, on peut citer :

– K. Borovkov. Elements of stochastic modelling. World Scientiofic 2003.– P. Brémaud. Markov chains. Springer Verlag 1998.– N. Bouleau. Processus stochastiques et applications. Hermann 2000.– S. M. Ross. Probability models for computer science. Academic Press 2002.

Pour un traité plus avancé des files d’attente on peut citer :P. Robert. Réseaux et files d’attente : méthodes probabilistes. Springer Verlag 2000.

Nombreux sont les ouvrages récents sur l’analyse des images et sur les réseaux stochastiques.Nous citons :

– G. Winkler. Image analysis, random fields and Markov chains Monte Carlo methods.Springer Verlag 2003.

– H. Chen, D.D. Yao. Fundamentals of queuing networks. Springer Verlag 2001.– R. Serfozo. Introduction to stochastic networks. Springer Verlag 1999.

Documents

Méthodes nonlinéaires et stochastiques de la recherche ...Marco.Dozzi/RechercheOperationnelle3/... · Méthodes nonlinéaires et stochastiques de la recherche opérationnelle Marco