Embed Size (px)
Citation preview
Version 2002
B.A. Ferrif
24/07/01
2
Je remercie chaleureusement
Nathalie Baumann,
Sabrina Durcos,
Céline Le Faucheux,
pour leur participation à la mise en ligne de cet enseignement
B.A. Ferrif
24/07/01
3
«�...La Mathématique est un devenir nécessaire,
imprévisible et inépuisable...�»
J. Cavailles, Thèse de Doctorat
«�...tous les moyens de l’esprit sont enfermés
dans le langage, et qui n’a pas réfléchi
sur le langage n’a pas réfléchi du tout...�»
Alain, Propos sur l’éducation, LXVI
B.A. Ferrif
24/07/01
4
Table des matières
Table des matières...........................................................................4
INTRODUCTION .............................................................................14
Eléments d'histoire et approche du domaine............................................15
1- Le prélude. ......................................................................................................................16
2- La naissance du calcul des probabilités.............................................................................17
3- La période analytique. ......................................................................................................18
4- La période moderne.........................................................................................................19
Philosophie du cours ............................................................................22
Pré-requis............................................................................................23
Objectifs..............................................................................................25
Mise en oeuvre .....................................................................................25
Pédagogie ...........................................................................................25
1-INTRODUCTION A LA NOTION DE PROCESSUS
STOCHASTIQUE ............................................................................27
I-Introduction .......................................................................................28
II-Prérequis et Objectifs .........................................................................28
1-Exemples de processus stochastiques, premières définitions et premières
questions.............................................................................................30
1 - 1 - Les systèmes "Flip-Flop" ............................................................................................30
1- 2 - Processus arborescents ..............................................................................................31
1- 3 - Files d'attente .............................................................................................................32
1 - 4 - Optimisation de la gestion d'un barrage .......................................................................33
1 - 5 – Optimisation d’un chiffre d’affaires ..............................................................................33
1 - 6 – Observation ..............................................................................................................34
B.A. Ferrif
2
5
2 - Définitions générales .......................................................................34
2 - 1 - Définition d’un processus stochastique ........................................................................34
2 - 2 – Processus à temps continu. .......................................................................................35
2 - 3 - Trajectoire ou réalisation du processus........................................................................36
2 - 4 - Remarque .................................................................................................................36
2 - 5 - Définition de la probabilité de transition........................................................................36
3- Processus de Bernoulli......................................................................36
3 - I- Définition d’un processus Nn n N( ) Œ de Bernoulli. ............................................................36
4
5-
6
3 – 2 - Loi PNnde Nn , et caractéristiques de PNn
..................................................................37
4/07/01
3 – 3 - Loi et caractéristiques de T1 .......................................................................................38
3 - 4 - Loi PT Tn n- -1 du temps d’attente T Tn n- -1 entre les (n-1)-ème et n-ème succès . ............39
3 – 5 - Indépendance des variables T T T T Tn n n n nk k1 2 1 1, ,..,- -
- (0 1 2< < < <n n nk.. ) ..........39
3 – 6 - Loi de N Nm n- et caractéristiques de la loi................................................................39
3 – 7 - Indépendance des variables aléatoires N N N N Nn n n n nk k1 2 1 1, ,..,- -
-.......................40
3 - 8 - P T k m T m= + ≥( ) ...............................................................................................40
– Optimisation d’un chiffre d’affaires (Retour sur l’exemple 1 - 5).............41
Résolution du problème réduit ..............................................................................................43
Simulation ...........................................................................................................................44
Processus gaussien. .........................................................................44
1- Définition d’un processus gaussien. ..................................................................................44
2- Bruit blanc échantillonné gaussien. ...................................................................................45
3- Simulation .......................................................................................................................45
– Etude du Processus de Wiener..........................................................45
Moyenne et variance de Xn . ...............................................................................................46
Loi de P X k rn =( ). . ...........................................................................................................46
Etude de la forme limite de la loi PX nde Xn .........................................................................47
B.A. Ferrif
24/07/01
6
Fonction d’autocorrélation. ...................................................................................................47
7 - Etude de modélisation – simulation – estimation. ................................47
2-Appendice ...................................................................................49
Compléments.......................................................................................49
Cet appendice regroupe un certain nombre de définitions ; il doit être ignoré en première lecture.
Il y sera fait référence en cas de nécessité. ...........................................................................49
A - 1 - Moments ..................................................................................................................49
A - 2 - Processus de deuxième ordre ....................................................................................49
A - 3 - Densité spectrale de puissance .................................................................................50
A - 4 - Stationnarité .............................................................................................................50
A - 5 - Bruit blanc.................................................................................................................50
A - 6 - Ergodicité..................................................................................................................51
2-Chaînes de Markov .....................................................................52
I-Introduction .......................................................................................53
II-Prérequis et Objectifs .........................................................................54
1-Processus et Chaînes de Markov .........................................................56
1-1-Définition des Processus de Markov................................................................................56
Chaîne et processus de Markov............................................................................................56
1-2-Analogie déterministe.....................................................................................................57
1- 3 – Exemple de chaîne de Markov : Marche aléatoire entre deux bornes.............................57
1 – 4 – Simulation................................................................................................................57
1 – 5 – Exemple de chaîne de Markov : Marche aléatoire avec absorption ..............................57
1 – 6 – Simulation................................................................................................................58
1- 7 - Homogénéité d'un processus de Markov ......................................................................58
1- 8 - Probabilité de transition de l'état x à l'état y pour un processus homogène......................58
1- 9 - Matrice de transition d'une chaîne de Markov homogène...............................................59
1- 10 - Exemples de matrice de transition : ...........................................................................59
B.A. Ferrif
24/07/01
7
1 - 11 - Exercice :.................................................................................................................60
1 - 12 - Préparation des simulations ......................................................................................60
1- 13- Graphe d'une chaîne de Markov homogène.................................................................61
1- 14 - Exercice ...................................................................................................................62
1- 15 - Simulation.................................................................................................................62
1- 16 - Exercice ...................................................................................................................62
2- Transition d'ordre supérieur ...............................................................63
2-1 – Notations et définitions ................................................................................................63
2-2-Equations de Chapman-Kolmogorov ...............................................................................63
2-3- Exercice .......................................................................................................................64
2-4- Simulation ....................................................................................................................65
2-5- Loi initiale de la chaîne de Markov..................................................................................65
2-6 - Loi de probabilité de Xn . ..............................................................................................65
2-7- Une caractérisation d'une chaîne de Markov homogène ..................................................66
3- Relations de communication entre états dans l'espace des états d'une
chaîne de Markov homogène..................................................................66
3-1 - Relation de communication sur l'espace d'états E. .........................................................66
3-2 - La relation de communication est une relation d'équivalence...........................................67
3-3- Test .............................................................................................................................67
3-4- Simulation ....................................................................................................................68
3-5- Remarque ....................................................................................................................68
3-6- Parties fermées et parties absorbantes...........................................................................68
3-7- Temps d'atteinte et probabilités d'atteinte .......................................................................71
3-7-3- Test ..........................................................................................................................72
4- Périodicité des états d'une chaîne de Markov à temps et états discrets....72
4-1- Notations et définitions ..................................................................................................72
4-2 – Définition de la Périodicité d'un état ..............................................................................73
4-3- Remarque ....................................................................................................................74
B.A. Ferrif
24/07/01
8
4-4 –Périodicité et atteignabilité ............................................................................................74
4-5- Périodicité et irréductibilité.............................................................................................74
4-6- Exercice .......................................................................................................................75
4-7- Exercice .......................................................................................................................75
4-8- Partition de l’espace des états en classes cycliques ........................................................76
5- Etat persistant et état transitoire. ........................................................76
5-1 - Définitions : .................................................................................................................76
5-2- Equivalences des définitions..........................................................................................76
5-3- Remarques...................................................................................................................77
5-4- Exercices :....................................................................................................................77
5-5- Remarque ....................................................................................................................78
5-6- Martingale ....................................................................................................................78
5-7- Exercice .......................................................................................................................78
5-8- Une caractéristique des états d'une même classe ...........................................................79
5-9- Exercice : .....................................................................................................................79
5-10 – Durées et probabilités de séjour dans l’ensemble des états transitoires.........................79
5-11- Matrice fondamentale : ................................................................................................83
5-12 - Problème :.................................................................................................................83
6-Ergodicité .........................................................................................84
6-1- Définition : ....................................................................................................................84
6-2- Remarques...................................................................................................................85
6-3- Théorème et définition...................................................................................................85
6-4- Remarque ....................................................................................................................86
7- Chaîne irréductible, décomposition des chaînes. ..................................86
7-1 – Partie irréductible fermée.............................................................................................86
7-2 – Décomposition d'une chaîne de Markov........................................................................86
7-3- Probabilité d'absorption par une classe récurrente ..........................................................87
7-4 – Caractérisation de la nature des états (1)......................................................................88
B.A. Ferrif
24/07/01
9
7-5 - Caractérisation de la nature des états (2).......................................................................88
7-6 - Caractérisation de la nature des états (3).......................................................................89
7-7- Caractérisation de la nature des états (4) .......................................................................89
7-8- Caractérisation de la nature des états (5) .......................................................................89
7-9- Exercice .......................................................................................................................89
7-10-Test ............................................................................................................................90
8- Distributions stationnaires et lois limites. ............................................90
8-1- Distribution stationnaire. ................................................................................................90
8-2- Lois limites ...................................................................................................................91
8-3- Lois limites et lois stationnaires des chaînes de Markov homogènes irréductibles et
apériodiques........................................................................................................................91
8-4- Loi stationnaire pour une chaîne arbitraire ......................................................................91
8-5- Remarques :.................................................................................................................92
8-6- Ergodicité des chaînes à espace d’états fini....................................................................93
8-7- Exercice : .....................................................................................................................93
8-8- Test .............................................................................................................................93
9- Extension:........................................................................................94
9-1- Matrices de transition d'une chaîne de Markov non-homogène. .......................................94
9-2-Processus de Markov d'ordre supérieur...........................................................................94
9-3-Modèles de Markov cachés. ...........................................................................................96
APPENDICE A : ..............................................................................99
Formule de Bayes..........................................................................99
A-1-Formule de Bayes : rappel et compléments........................................99
A-2 Formule de Bayes généralisée. .......................................................101
Appendice B :............................................................................... 102
Graphes........................................................................................ 102
B-1-Définitions ...................................................................................102
B.A. Ferrif
24/07/01
10
B-2-Connexité ....................................................................................107
B-2-1-Graphe connexe.......................................................................................................107
B-2-2-Composante connexe d’un graphe ............................................................................108
B-2-3-Graphe fortement connexe........................................................................................108
B-3-Matrice d’adjacence associée à un graphe .......................................108
B-4-Fermeture transitive d’un sommet du graphe. ..................................110
Calcul de la fermeture transitive..........................................................................................110
B-5-Valeurs propres des matrices stochastiques....................................111
B-5-1-Valeurs propres et classes récurrentes ......................................................................111
B-5-2-Valeurs propres et classes périodiques......................................................................112
Problèmes de synthèse............................................................... 113
Thème d'étude 1 : Etude du cursus d’un élève dans une grande école ......113
Thème d'étude 2 : Un problème de reconnaissance des formes................115
3-Processus de Poisson et.......................................................... 116
Processus de renouvellement..................................................... 116
Prérequis et Objectifs..........................................................................117
Introduction .......................................................................................119
1- Processus de comptage...................................................................119
1-1 - Exemples : ................................................................................................................119
1-2 - Définition des processus de comptage ........................................................................120
2 - Processus de Poisson. ...................................................................120
2-1 – Processus stochastique à accroissements indépendants .............................................120
2-2 - Processus stochastique à accroissement stationnaire ..................................................120
2-3 – Définition d’un processus de Poisson..........................................................................121
2-4- Simulation : ................................................................................................................121
2-5 – Loi de probabilité du nombre d’événements dans un intervalle de temps donné. ...........121
B.A. Ferrif
24/07/01
11
2-6- Equations d'Erlang......................................................................................................123
2-7- Exercice : Un problème de qualité : ..............................................................................124
2-8- Test : .........................................................................................................................124
2-9 – Loi des temps d’attentes inter-évènements .................................................................126
2-10- Loi du temps d'attente du nème événement Sn n= + + +t t t1 2 ... . ................................127
2-11 – Processus de comptage et processus de Poisson .....................................................127
2-12 – Equivalence d'évènements.......................................................................................128
2-13 – Temps d'occurrence d'un évènement........................................................................128
2-14 - Graphes associés à un processus de Poisson ...........................................................128
3 - Processus de naissance et de disparition..........................................131
3-1- Définition....................................................................................................................131
3-2- Graphe d'un processus de naissance et de disparition ..................................................132
3-3- Remarques :...............................................................................................................132
3-4- Probabilité d'un état pour un processus de naissance et de disparition ...........................133
3-5- Remarques.................................................................................................................135
3-6- Equation des flux et loi de Khirchhoff............................................................................136
3-7- Test ...........................................................................................................................136
3-8- Test : .........................................................................................................................137
4- Processus de renouvellement...........................................................138
4-1 - Définition d’un processus de renouvellement ...............................................................138
4-2- Test ...........................................................................................................................138
4-3 - Remarques :..............................................................................................................139
4-4 – Loi de Wn ................................................................................................................139
4-5 – Fonction de renouvellement .......................................................................................140
4-6- Test ...........................................................................................................................140
4-7 – Equivalence de Nt et de Wt .....................................................................................140
4-8 – Relation entre la fonction de renouvellement Mt et la fonction de répartition Fn ...........141
4-9 – Quelques variables aléatoires de la théorie du renouvellement.....................................141
B.A. Ferrif
24/07/01
12
4-10- Processus de Poisson vu comme un processus de renouvellement..............................142
4-11 - Théorème du renouvellement élémentaire .................................................................144
4-12- Test .........................................................................................................................144
5- Etude d’un processus "Flip-Flop" .....................................................145
5-1- Simulation ..................................................................................................................145
5-2- Etude du processus Flip-Flop.......................................................................................146
Appendice .................................................................................... 149
Processus de Poisson non homogène....................................... 149
Introduction .......................................................................................150
4-Réseaux de files d’attente ........................................................ 152
Prérequis et Objectifs..........................................................................153
1-Système à files d'attente ...................................................................155
1-1- Schéma général..........................................................................................................155
1-2- Description des caractéristiques d'un système à files d'attente (SAFA). ..........................155
1-3- Notation de Kendall.....................................................................................................158
1-4- Notations et définitions de base pour les systèmes à files d'attente. ...............................159
1-5- Loi de Little.................................................................................................................161
2- Processus de naissance et de disparition considérés comme systèmes à
files d'attente......................................................................................162
3- Etude d’une file d’attente de type M/M/1 .............................................163
3-1- Rappel de quelques notations et définitions de base pour les systèmes à files d'attente. .163
3-2- Caractéristiques des systèmes à files d'attente de type M/M/1 .......................................164
4 - Réseaux de files d’attente ...............................................................168
4-1- Réseaux à commutation de paquets ............................................................................168
4-2- Systèmes informatiques ..............................................................................................169
4-3- Les Réseaux de Jackson.............................................................................................170
Théorème de Jackson :......................................................................................................170
B.A. Ferrif
24/07/01
13
4-4- Test ...........................................................................................................................171
4-5- Modèle du serveur central ...........................................................................................173
Algorithme 1. .....................................................................................................................174
Algorithme 2. .....................................................................................................................175
4-6- Schéma d’un modèle du serveur central.......................................................................175
4-7- Test ...........................................................................................................................176
4-8- Etude et simulation .....................................................................................................177
4-9- Exercice : Un système à file d'attente ...........................................................................178
5- ETUDE ASSISTEE PAR ORDINATEUR ...............................................180
Index............................................................................................. 182
B.A. Ferrif
24/07/01
14
INTRODUCTION
B.A. Ferrif
24/07/01
15
Eléments d'histoire et approche du domaine
Le terme probabilité fait aujourd'hui partie du langage courant. Véhiculé par les
médias et employé par chacun, souvent à bon escient, il est en général nanti d'une
signification naïve. Cette signification n'est pas sans rapport avec le double sens dont
il était porteur, liant philosophie et sciences, qui accompagna son développement
jusqu'à l'apparition du concept mathématique de probabilité (Kolmogorov 1932). Ce
n'est qu'à partir de cette date que la discipline s'est mise à progresser
indépendamment de ses interprétations. Le premier de ces deux sens, les propriétés
des choses, s'est mathématisé (Leibnitz 1678) en : rapport du nombre des cas
favorables au nombre des cas possibles lorsque tous les cas sont équipossibles,
l'équipossibilité étant justifiée par l'apparente stabilité des fréquences. Le second
sens, les propriétés des propositions, a évolué en : degré de crédibilité et motifs de
croire, l'équipossibilité étant alors justifiée par le manque de raisons suffisantes.
On peut raisonnablement distinguer quatre grandes époques dans l'histoire de la
théorie des probabilités :
∑ Le prélude, qui s'étend du Moyen-âge à la première moitié du XVIIème
siècle: énoncé de problèmes liés à la pratique de certains jeux de hasard.
∑ La naissance du calcul des probabilités, deuxième moitié du XVIIème et
XVIIIème siècle : calculs combinatoires, dégagement des concepts de base.
∑ La période analytique, fin du XVIIIème et XIXème siècle : utilisation des
progrès de l'analyse mathématique.
∑ La période moderne, le XXème siècle : axiomatisation de la théorie des
probabilités (utilisant la théorie de la mesure) et processus stochastiques.
B.A. Ferrif
24/07/01
16
1- Le prélude.
C'est au Moyen-âge et pendant la Renaissance qu'apparaissent les premières
considérations qui relèvent du calcul des probabilités. Les problèmes posés sont
essentiellement des questions liées à la pratique des jeux de hasard. Ainsi voit-on
apparaître dans un livre de Paciuolo sur "l'art du calcul" publié en Italie en 1494 le
difficile problème des partis dont voici l'énoncé :
"Le prix d'un tournoi est gagné par le premier des deux participants qui obtient 6
points; la partie est interrompue alors que l'un d'eux a 5 points et l'autre 2. Comment
partager le prix entre les deux joueurs ? Serait-il équitable de le faire
proportionnellement aux points obtenus ?"
Cardano (1501-1570) écrit en 1525 un traité intitulé "De Ludo Aleae" (il sera publié
en 1663) et montre que la solution de Paciuolo est fausse. La solution qu'il donne à
son tour sera réfutée par Tartaglia (1499-1557), qui en donne une, lui aussi, qui est
fausse. Il faudra attendre le milieu du XVIIème siècle pour voir ce problème résolu.
Képler (1561-1630) travaille également sur les jeux de hasard, ainsi que Galilée
(1564-1642) qui résout, en particulier, le problème suivant : pourquoi constate-t-on
au jeu de passe-dix , en lançant trois dés, qu'un total de points égal à 10 ou 11 est
plus probable qu'un total de 9 ou de 12, ceci bien que chacun de ces totaux puisse
s'obtenir par exactement 6 combinaisons de points à savoir : 631, 622, 541, 532,
442, 433 pour un total de 10 points et par 621, 531, 522, 441, 432, 333 pour un total
de 9. Mais les idées de base insuffisamment mises en évidence font que les calculs,
même justes, ouvrent des controverses.
B.A. Ferrif
24/07/01
17
2- La naissance du calcul des probabilités.
Les mathématiques du hasard naissent des travaux respectifs de Pascal (1623-
1662) et Fermat (1601-1665) et de leur correspondance de l'année 1654. Le
chevalier de Méré, joueur de grand renom, pose à Pascal, Roberval, Fermat et
d'autres deux problèmes :
le premier, relativement simple, fut rapidement résolu par ces trois protagonistes, en
voici une forme issue d'une lettre de Pascal à Fermat : le chevalier de Méré "… avait
trouvé fausseté dans les nombres pour cette raison : si l'on entreprend de faire six
avec un dé, il y a avantage de l'entreprendre par 4 coups; si l'on entreprend de faire
sonnez (double six) avec deux dés, il y a désavantage de l'entreprendre en 24 coups;
et néanmoins 24 est à 36 qui est le nombre des faces des deux dés comme 4 est à 6
qui est le nombre de faces d'un dé. Voilà quel était son grand scandale ...."
Le second n'est autre que le problème des partis. Enonçons-le à nouveau : le prix
d'un tournoi (64 pistoles) est gagné par le premier des deux participants qui obtient 3
points. Comment partager l'enjeu si la partie est interrompue alors que l'un des deux
a 2 points et l'autre 1. Ce problème a été résolu par Pascal d'une part et Fermat
d'autre part, chacun forgeant une méthode différente. Comme avatar de la vie
scientifique il faut souligner que Roberval, qui n'est pas parvenu à la solution, a
vivement attaqué celle, correcte, de Pascal que l'on trouvera dans [Pascal, œuvre
complète], par exemple (on remarquera l'utilisation des équations aux différences).
Soulignons que la méthode de Fermat s'étend à un nombre de joueurs supérieur à 2.
Le mathématicien Hollandais Huyghens (1629-1695) reconnaît l'importance du calcul
des probabilités et écrit qu'il s'agit "… des fondements d'une théorie nouvelle, à la
fois profonde et intéressante" ; il rédige en 1656 un texte (communiqué à Pascal et
Fermat) qui élargit les connaissances antérieures en dégageant quelques concepts
fondamentaux, en particulier celui d'espérance mathématique, pour des variables
aléatoires à un nombre fini de valeurs. Dans le texte de Huyghens qui comporte 14
propositions, figurent cinq problèmes non résolus, dont trois fournis par Pascal et
B.A. Ferrif
24/07/01
18
Fermat. Parmi ces 3 problèmes figure celui de la ruine des joueurs (ancêtre des
promenades aléatoires), dont voici un énoncé : dans un jeu à deux joueurs A et B, la
probabilité que A gagne est p, celle que B gagne est q. Supposons le capital de A
égal à z et celui de B égal à a-z (de sorte que le capital total soit a). Le jeu se
poursuit jusqu'à ce que l'un des deux joueurs soit ruiné. Quelle est la probabilité de
ruine des joueurs? Quelle est la loi de probabilité de la durée du jeu ?
C'est à Jacques Bernoulli (1654-1705) qu'allait revenir l'honneur de l'avancée
suivante. Dans son livre "Ars conjectandi" publié par son frère Nicolas en 1713, il
reprend, dépasse et approfondit les résultats de Huyghens, développe une théorie
des séries, met en évidence le rôle de la formule du binôme, établit que la fréquence
d'un événement tend vers sa loi de probabilité, résultat qui représente la forme la
plus simple de la loi des grands nombres (à laquelle il aurait consacré 20 ans de
réflexions).
Nicolas Bernoulli pose à cette époque le problème connu sous le nom de paradoxe
de Saint Petersbourg (il fut adressé à l'académie de cette ville): on joue à pile ou
face; sachant qu'un joueur doit payer un droit de jouer et reçoit 2n francs lorsqu'il
obtient pile pour la première fois à la n-ième épreuve, que doit-il payer pour être
gagnant à ce jeu? Cette question a été définitivement éclaircie par W. Feller en 1937
alors qu'il étudiait la notion de jeu équitable en relation avec la loi des grands
nombres.
3- La période analytique.
Abraham de Moivre (1667-1754) publie dans son exil Londonien, en 1718, la
"Doctrine des chances" où il améliore le théorème de Bernoulli et donne sa première
forme à ce que nous appelons aujourd'hui le théorème de la limite centrale. On
trouve dans ce livre, en particulier, les notions de fonction génératrice,
d'indépendance et de probabilité conditionnelle. De Moivre résout également le
problème des partis dans le cas de deux joueurs ayant des probabilités quelconques
B.A. Ferrif
24/07/01
19
de gagner à chaque coup. (Lagrange (1736-1813) résoudra le problème pour un
nombre arbitraire de joueurs).
Laplace (1749-1827) écrit en 1812 le "Traité analytique des probabilités" qui allait
influencer tout le XIXème siècle. Cet ouvrage s'appuie sur les développements
récents de l'analyse en faisant un usage important des fonctions génératrices et
caractéristiques. Le théorème de la limite centrale de de Moivre est généralisé (sinon
démontré) d'où son autre nom de théorème de de Moivre-Laplace. Tchebichev
donnera de ce théorème un énoncé et une démonstration plus clairs mais erronés
(les variables aléatoires n'y sont pas supposées indépendantes), Markov (1856-
1922) les corrigera.
4- La période moderne
Elle trouve ses racines pendant tout le XIXème siècle et la première moitié du
XXème , période durant laquelle les développements des probabilités sont rythmés
par ceux de l'analyse. En particulier les espaces de Hilbert [Hilbert (1862-1943)] et la
Théorie de la mesure et de l'intégration [Borel (1871-1956) et Lebesgue (1875-1941)]
joueront, dès leur découverte, un rôle déterminant dans cette évolution.
Des problèmes nouveaux voient le jour et conduisent à la théorie des processus
aléatoires. La notion de processus aléatoire est déjà présente dans les études de
Bernoulli (J) (1654-1705) et de Laplace (1749-1827) sur les suites aléatoires (où
l'indice figure le temps : le moment de réalisation de l'épreuve). La notion de
processus aléatoire figure également dans les travaux de Poisson (1781-1840) et
dans ceux de Tchebychev (1821-1894). Dans le cadre d'une étude sur l'évolution des
familles, Galton (1882-1911) et Watson posent en 1874 les bases de ce que l'on
nomme aujourd'hui les processus de branchement : le problème est de décrire
comment le nombre des individus N n +( )1 d'une population aléatoire à l'instant n + 1
dépend du nombre des individus N n( ) de cette population aléatoire considérée à
l'instant n . Ainsi la famille des modèles probabilistes qui reposaient jusqu'alors
B.A. Ferrif
24/07/01
20
essentiellement sur des variables indépendantes est enrichie de modèles dans
lesquels les variables sont dépendantes. Certaines dépendances remarquables
émergent des travaux que Markov (1856-1922) mène entre 1907 et 1912 et qui
conduisent à ce que nous connaissons aujourd'hui sous le nom de Théorie des
chaînes de Markov. Elle décrit des processus pour lesquels l'évolution aléatoire à
partir d'un instant t ne dépend que de l'état du processus à cet instant et non de la
manière dont le processus a atteint cet état (ce qui n'est pas sans rappeler certains
phénomènes de propagation des ondes).
Entre 1925 et 1940 la théorie des probabilités est axiomatisée (Kolmogorov : 1932),
les résultats des siècles précédents sont approfondis et généralisés, les structures
stochastiques font leur apparition et la théorie des processus aléatoires se développe
; deux familles de modèles probabilistes coexistent :
∑ Les modèles à temps fixe : où le temps n'intervient pas directement ;
∑ Les modèles à temps variables : dans lesquels le temps est l'un des
arguments des variables aléatoires.
La pensée de P. Lévy (1886-1971) domine l'école française, alors que Kolmogorov
(1903-1987) et Kintchine (1894-1959) créent l'école russe, Feller (1906-1970) et
Doob (1910--) l'école américaine. C'est de ce vaste élan que va émerger le corpus
actuel.
Une fois encore, pendant cette période, les phénomènes naturels vont jouer un rôle
déterminant dans l'évolution de la théorie: depuis son observation par Brown (1773-
1858), le mouvement brownien n'a pas fait l'objet d'une modélisation satisfaisante;
pire, l'observation de la trajectoire d'une particule fait douter que la vitesse de cette
dernière puisse être calculée (absence de tangente à la trajectoire à cause de
l'irrégularité), de sorte que la théorie cinétique des gaz ne peut s'appliquer. Deux
modèles vont alors faire leur apparition :
Le premier, dû à Einstein (1879-1955), met en évidence la description des processus
de Markov par leur probabilité de transition; il permet une description globale du
B.A. Ferrif
24/07/01
21
mouvement brownien (il postule que la position d'une particule est fonction d'une
densité de probabilité vérifiant une équation de la chaleur).
Le second, indépendant du premier, dû à Smoluchowski , permet de mieux saisir les
propriétés des trajectoires en les considérant comme limites de promenades
aléatoires.
Un autre point de vue va être fécond sur ce même problème. Suivant les idées de
Langevin (1872-1946), deux mathématiciens, Ornstein et Uhlenbeck, supposent que
la vitesse de la particule est une variable aléatoire; ils sont alors conduits à une
équation différentielle d'un genre nouveau, qui exprime que la force appliquée à la
particule à un instant donné est la somme d'une force de frottement proportionnelle à
la vitesse et d'une force aléatoire. Cette idée a ouvert une voie féconde, celle des
équations différentielles stochastiques.
Une autre voie d'étude sera ouverte par N. Wiener (1894-1964) qui construit, en
1923, un modèle mathématique, qui conduit à la mesure qui porte son nom. Les
méthodes aléatoires dégagées par Wiener auront un vaste champ d'application
parmi lesquels, entres autres, la théorie de la communication et la théorie du signal.
De nombreuses questions nouvelles apparaissent au XXème siècle dans des
domaines aussi variés que
∑ les mathématiques elles-mêmes ,
∑ la physique théorique et appliquée (comme nous venons de le voir),
∑ l'organisation des entreprises (évolution de la demande d'un bien, variation du
nombre de clients désireux de recevoir un service, gestion de sur-réservation,….),
∑ la santé publique (étude de la propagation des épidémies, évolution de
l'effectif d'une population,….),
∑ la conception et le dimensionnement des réseaux informatiques ou de leurs
composants (dimensionnement des mémoires, structure de l'ordinateur, réseaux à
commutation de paquets…)
B.A. Ferrif
24/07/01
22
∑ l'économie (anticipations rationnelles, valeur actualisée corrigée du risque,
évaluation des primes de terme,…),
∑ la commande de processus (commande optimale,….)
∑ l'analyse et le traitement du signal (filtrages,…)
∑ la biologie (séquençage du génome,…)
∑ ………..
qui féconde la recherche fondamentale et appliquée et en retour s'enrichissent de
modèles efficaces et pertinents.
Philosophie du cours
En écho à ces quelques éléments d'histoire, cet enseignement fait apparaître quatre
axes dépendants :
∑ l'axe mathématique,
∑ l'axe des applications,
∑ l'axe de la modélisation,
∑ l'axe de la simulation.
Sur celui des mathématiques, nous éviterons toute technicité excessive et nous
nous limiterons à celles des démonstrations qui présentent un intérêt particulier pour
acquérir des méthodes de résolution de problèmes, appréhender les différentes
problématiques stochastiques et se familiariser avec les raisonnements qu'elles
induisent .
Sur le plan des applications, la mathématique fera office de langage pour
modéliser et d'outil pour comprendre et pour prédire. Cette mise en situation, dans
B.A. Ferrif
24/07/01
23
des études de cas concrets, suivra l'indispensable étape de modélisation, étape
essentielle qui mérite des soins attentifs avec lesquels nous nous familiariserons.
La modélisation occupe une place capitale : elle permet de passer du problème
empirique, c'est-à-dire du problème tel qu'il se présente en situation dans une
application, à son expression dans le langage mathématique et la perspective
théorique retenue et permet de procéder à son traitement par les voies les plus
appropriées. Les objets mathématiques se chargent alors du sens relatif au contexte
et les résultats théoriques, ainsi que les différents critères abstraits, fournissent
automatiquement des résultats qu'il reste à interpréter. Comme plusieurs modèles
peuvent généralement décrire la même situation empirique, la phase de modélisation
sera abordée sans préjugé; les techniques que nous préfèrerons dépendront et
évolueront au gré de la nature des applications. Toutefois il faudra toujours évaluer
l'adéquation à la réalité des modèles destinés à en rendre compte.
La simulation nous permettra de reproduire et d'étudier expérimentalement
certaines situations. Cette étape sollicite particulièrement la créativité et l'imagination.
Pour la mener à bien nous utiliserons abondamment le logiciel de Mathematica.
L'utilisation du Calcul Formel d'une part, le mariage des méthodes symboliques et
numériques d'autre part nous permettront, par l'intermédiaire de l'informatique,
d'aborder des études de cas plus proches de la réalité et en plus grand nombre, nous
déchargeant de calculs parfois long, répétitifs et fastidieux. Les activités de résolution
de problèmes s'en trouveront ainsi singulièrement enrichies.
Ceci résume la philosophie qui anime , à chaque étape, cet enseignement.
Pré-requis
Cet enseignement nécessite certains pré-requis parmi lesquels figurent en particulier
:
B.A. Ferrif
24/07/01
24
∑ Théorie des ensembles : Opérations sur les parties d'un ensemble et
relations entre ensembles en particulier : U I, , complémentaire, partition, image
directe et image réciproque par une application.
∑ Analyse combinatoire : arrangements, combinaisons, permutations.
∑ Analyse de base : Intégration et dérivation des fonctions classiques, séries
numériques et séries entières. Notions d’optimisation. Résolution des systèmes
différentiels du premier ordre à coefficients constants. Distribution de Dirac.
Transformations intégrales (Fourier et en Z).
∑ Probabilités : Concepts d’espace probabilisable et d’espace probabilisé, de
variable aléatoire, de moments d’une variable aléatoire, de dépendance et
d’indépendance (en théorie des probabilités); la formule de Bayes. Les lois de
Bernoulli, Géométrique, Gauss, Exponentielle, Poisson ainsi que leurs principales
caractéristiques. Le théorème de la limite centrale. Les fonctions génératrices.
∑ Algèbre : Algèbre matricielle; Notions de base en théorie des graphes (les
éléments de base de la théorie des graphes sont rappelés en appendice du chapitre
2).
∑ Informatique: des éléments d'algorithmique et des éléments de
programmation sous Mathematica ou sous un autre langage pour réaliser les
simulations.
∑ Certains exercices font appel à:
o Quelques éléments de théorie du signal : Filtrage.
o Quelques éléments de théorie des systèmes : Bouclage.
B.A. Ferrif
24/07/01
25
Objectifs
Ce que vous devez savoir faire à la fin de cet enseignement:
∑ Savoir déterminer si un processus est de nature stochastique,
∑ Savoir reconnaître, utiliser et simuler : les processus de Bernoulli , de Markov,
de comptage, de Poisson, de naissance et de disparition, de renouvellement.
∑ Savoir reconnaître et utiliser les concepts de files d'attente ou de réseaux de
files d'attente dans des cas simples.
∑ Savoir en déterminer les principales caractéristiques,
∑ Savoir modéliser, simuler et résoudre des problèmes qui relèvent de ces
concepts.
Mise en oeuvre
Ce qui vous est proposé dans cet enseignement :
∑ Aborder les concepts généraux,
∑ Se familiariser avec la modélisation et la simulation des processus cités, et
apprendre à en simuler d'autres.
∑ S’exercer sur des applications immédiates,
∑ Réfléchir sur des problèmes concrets et de synthèse,
∑ S’auto évaluer par tests de connaissance et de savoir-faire.
Pédagogie
Une pédagogie fortement participative qui repose sur la complémentarité entre :
∑ Les "amphis" constitués de :
B.A. Ferrif
24/07/01
26
∑ Brèves synthèses présentant la philosophie, les concepts et les résultats
fondamentaux,
∑ Dialogues : questions réponses soulevées lors de la préparation et de l'étude
des différentes parties du cours.
∑ Le travail demandé en e-learning sur le campus électronique du Groupe
ESIEA, avec un mode de fonctionnement qui sera exposé au premier amphi.
∑ Un "micro projet".
Paris, Août 2001
B.A. Ferrif
24/07/01
27
1-INTRODUCTION A LA NOTION
DE PROCESSUS STOCHASTIQUE
B.A. Ferrif
24/07/01
28
I-Introduction
L'objet de la théorie des processus stochastiques (aléatoires) est de représenter
et d'étudier les phénomènes aléatoires dépendant du temps. La théorie des
processus aléatoires est un cas particulier de celle des fonctions aléatoires,
fonctions mesurables X X X tt t: ( ) ( , )w w wÆ = avec X Et:W Æ , ( , , )W F P
espace probabilisé et ( , )E G un espace probabilisable. La théorie des fonctions
aléatoires constitue un vaste domaine d'étude auquel ce cours n'est qu'une
introduction.
Nous introduirons d'abord, à l'aide de quelques exemples familiers, la notion de
processus aléatoire, puis nous en donnerons la définition précise ainsi que
quelques propriétés générales. Nous examinerons ensuite quelques exemples de
processus aléatoires élémentaires.
II-Prérequis et Objectifs
Ce que vous devez au minimum maîtriser pour aborder ce chapitre :
∑ Probabilités : Concepts d’espace probabilisable et d’espace probabilisé, de
variable aléatoire, de moments d’une variable aléatoire, de dépendance et
d’indépendance (en théorie des probabilités); la formule de Bayes. Les lois de
Bernoulli, Géométrique et de Gauss ainsi que leurs principales
caractéristiques. Le théorème de la limite centrale pour l’étude des processus
de Wiener.
∑ Analyse : Notions d’optimisation ; Transformation de Fourier pour l’appendice
et certains exercices.
B.A. Ferrif
24/07/01
29
Ce que vous devez maîtriser pour tirer pleinement profit de ce chapitre :
En plus des éléments précédents :
∑ Informatique: des éléments de programmation et des éléments de
programmation sous Mathematica ou sous un autre langage pour réaliser les
simulations.
Ce que vous devez savoir faire à la fin de cette leçon :
∑ Savoir déterminer si un processus est de nature stochastique,
∑ Savoir reconnaître et utiliser les processus de Bernoulli,
∑ Savoir reconnaître un processus Gaussien,
∑ Savoir poser et résoudre un problème simple d’optimisation stochastique
discrète.
Ce qui vous est proposé dans ce chapitre :
∑ Aborder les concepts généraux,
∑ Se familiariser avec la modélisation et la simulation de processus
stochastiques,
∑ S’exercer sur des applications immédiates,
∑ Réfléchir sur des problèmes concrets et de synthèse,
∑ S’évaluer par tests de connaissance et de savoir-faire.
B.A. Ferrif
24/07/01
30
1-Exemples de processus stochastiques, premières
définitions et premières questions.
1 - 1 - Les systèmes "Flip-Flop"
Un système Flip-Flop est un système qui peut occuper deux états ; par exemple
un interrupteur qui est ouvert ou fermé, une ligne téléphonique qui est libre ou
occupée. La description d’un tel système se fait à l'aide de deux états, disons a et
b :
∑ à l'instant to , que nous prenons comme origine, le système occupe l'un d'eux ;
∑ au terme d'une durée aléatoire T, de loi connue, il change d'état ;
∑ il reste dans ce nouvel état une durée aléatoire T' de même loi que la
précédente, mais indépendante de T ; et ainsi de suite...
Ainsi, on modélise le comportement du système :
∑ en décrivant l’ensemble E a b= { }, des états a priori possibles,
∑ en précisant la dynamique, c’est-à-dire l’occupation d’un état en fonction du
temps :
la description doit prendre en compte l’aspect aléatoire de la situation ;
on associe donc à chaque instant t une variable aléatoire Xt qui prend
ses valeurs dans l'espace des états E a b= { }, .
L’ensemble ( )Xt t RŒ des variables aléatoires Xt se trouve ainsi à la base de la
modélisation du système Flip-Flop ; ce système est un exemple de processus
stochastique. Il peut rendre compte de l'état d'occupation d'une ligne téléphonique
par exemple.
B.A. Ferrif
24/07/01
31
a
b
Il est alors naturel de s’interroger :
i) sur la nature de la loi de probabilité PX tde X t Rt " Œ( ) ;
ii) sur la probabilité d'être dans l'état x au temps t sachant que l'on est
dans l'état y au temps s < t ;
iii) sur l’existence de propriétés asymptotiques pour PX t quand t tend vers
+• ;
Une étude complète du processus flip-flop sera réalisée dans le chapitre 3 .
1- 2 - Processus arborescents
Il s’agit ici d’étudier l’évolution d’une population. Supposons connu le nombre
d’individus que compte cette population à l’instant n. On sait que chaque individu
génère, indépendamment des autres, une descendance dont le nombre est
aléatoire, laquelle engendre à son tour une descendance...
Si l’on désigne par Xn le nombre d'individus de la même génération, étudier
l’évolution de cette population c’est en particulier s’interroger sur :
i) la nature de la relation qui existe entre Xn et Xn +1 ;
B.A. Ferrif
24/07/01
32
en particulier Xn +1 dépend-il seulement de Xn ?
ii) le risque (la probabilité) d'extinction de l'espèce .
1- 3 - Files d'attente
Des clients se présentent à des guichets, en des temps aléatoires, pour recevoir
un service de durée aléatoire.
∑ Quel est, parmi les deux types d’organisation suivants, celui qui assure la
meilleure satisfaction des clients ?
Ensemble des clients
Service 1
Service 2
Service n-1
Service n
File d'attente 1
File d'attente 2
File d'attente n-1
File d'attente n
B.A. Ferrif
24/07/01
33
Ensemble des clients
Service 1
Service 2
Service n-1
Service n
File d'attente unique
∑ Comment déterminer le nombre minimum de guichets pour assurer le bon
écoulement de la file d'attente ?
1 - 4 - Optimisation de la gestion d'un barrage
∑ Comment décrire l'évolution du niveau d'eau dans un barrage dont les apports
sont aléatoires et sur lequel on peut agir en turbinant de l'eau pour produire de
l'électricité ?
∑ Comment optimiser la gestion en prenant des décisions qui dépendent de
l'état du système afin d'optimiser la production d'énergie ?
Dans cet exemple on souhaite non seulement prendre des décisions en avenir
incertain mais également optimiser ces décisions.
1 - 5 – Optimisation d’un chiffre d’affaires
Il est de notoriété publique que les compagnies aériennes, par exemple,
pratiquent la surréservation c’est-à-dire vendent plus de billets que de places
disponibles dans les avions. Les modalités d’utilisation des billets diffèrent suivant
le type de billet et la catégorie tarifaire à laquelle il appartient. Ainsi pour certains
billets il peut y avoir remboursement intégral de celui-ci s’il n’a pas été utilisé et
une indemnisation si le passager n’a pas pu embarquer.
B.A. Ferrif
24/07/01
34
Ces compagnies ont constaté qu’une proportion notable des détenteurs de billets,
elle peut atteindre 50%, ne se présente pas à l’embarquement. Elles sont
conduites à chercher à optimiser leur chiffre d’affaires en pratiquant la
surréservation (puisque le nombre de places dans l’avion, le prix de la place, et
les modalités d’utilisation des billets sont fixés au moment de la vente). Cette
pratique n’est pas sans risque, notamment pour l’image de la compagnie. Comme
le chiffre d’affaires dépend de la présence aléatoire du nombre de passagers ,
des questions vitales se posent aux compagnies aériennes :
Peut-on construire un modèle permettant de gérer ce problème de manière
optimale?
En amont de la question précédente, existe-t-il une méthode permettant de
déterminer le prix de vente du billet de manière à optimiser le chiffre d’affaires
tout en restant concurrentiel ?
1 - 6 – Observation
Regarder autour de soi et construire son propre ensemble d'exemples.
2 - Définitions générales
2 - 1 - Définition d’un processus stochastique
On appelle processus aléatoire, ou processus stochastique, toute application
X I E:W ¥ Æ où :
W , ,F P( ) est un espace probabilisé, I une partie de R ou de Z et E un espace
probabilisable, en général une partie de Rn ou de Zn ,
B.A. Ferrif
24/07/01
35
et où pour tout t dans I, X t Xt-( ) =, est un élément aléatoire (donc une variable
aléatoire si E = Rn ou Zn).
Un processus aléatoire peut donc être considéré comme une famille d'éléments
aléatoires (respectivement variables aléatoires) Xt t I( ) Œ (I représentant
généralement le temps).
Temps I
Oméga
Etats
x
t
(x,t)
e=X(x,t)
2 - 2 – Processus à temps continu.
Lorsque I P ZŒ ( ) , on dit que le processus est à temps discret ; on parle alors
parfois de série chronologique.
Lorsque I P RŒ ( ) , on dit que le processus est à temps continu.
L'ensemble E s'appelle l'espace des états, ou l'espace d'état, ou l'espace de
phase.
B.A. Ferrif
24/07/01
36
2 - 3 - Trajectoire ou réalisation du processus.
Lorsque w ŒW est fixé, X w,-( ) définit une fonction du temps t XtÆ ( )w ; cette
fonction s'appelle une trajectoire du processus X (ou encore une réalisation de X).
2 - 4 - Remarque
La connaissance de la loi de Xt , pour tout temps t, ne caractérise pas le
processus car elle ne donne aucune information sur l'évolution du processus, en
d'autres termes sur la probabilité de transition de Xt w( ) à Xs w( ) (avec t s< ). Cela
justifie l'introduction du concept suivant.
2 - 5 - Définition de la probabilité de transition
Soient B1 et B2 deux sous-ensembles mesurables de l'espace des états, s et t
deux instants dans I, par exemple s < t. On appelle probabilité de transition de B1
à B2, entre les instants s et t, la probabilité conditionnelle : P X B X Bt s( )Œ Œ2 1 .
Cette notion, comme on s'en doute, est un concept-clé de la théorie.
3- Processus de Bernoulli
3 - I- Définition d’un processus Nn n N( ) Œ de Bernoulli.
Rappels : Une variable aléatoire X est une variable de Bernoulli si et seulement
si c'est une variable aléatoire discrète prenant deux valeurs respectivement avec
les probabilités p et q=1-p. Pour fixer les idées nous dirons que X prend les
B.A. Ferrif
4/07/02
37
valeurs 0 et 1 et que P pX 1{ }( ) = et P p qX 0 1{ }( ) = - = . Nous dirons que X modélise
une épreuve de Bernoulli.
Si nous répétons n fois la même épreuve de Bernoulli, la i-ème épreuve sera notée
Xi, toutes les épreuves seront supposées indépendantes. Désignons par Nn la
somme des n premiers Xi. On constate que Nn compte le nombre de 1 (on dit aussi
le nombre de succès lorsque 1 désigne le succès et 0 l'échec).
Définition : La suite Nn n N( ) Œ porte le nom de processus de Bernoulli.
Certaines des questions que nous nous sommes posées lors de l’examen des
exemples du §1 se retrouvent ici de manière naturelle, et de nouvelles questions
apparaissent; ainsi :
∑ Quelle est la loi PNnde Nn ? Quelles sont les caractéristiques de PNn
?
∑ Quelle est la loi PT1du temps d’attente T1 du premier succès ? Quelles sont les
caractéristiques de cette loi?∑ Quelle est la loi PT Tn n- -1
du temps d’attente T Tn n- -1 entre les (n-1)-ème et n-ème succès ?
∑ Les variables aléatoires T T T T Tn n n n nk k1 2 1 1, ,..,- -
- sont-elles indépendantes
entre elles ( 0 1 2< < < <n n nk.. ) ?∑ Quelle est la loi PN Nm n- du nombre N Nm n- de succès dans l'intervalle ]n ,m]
(avec 0 £ <n m ) ?∑ Les variables aléatoires N N N N Nn n n n nk k1 2 1 1
, ,..,- --
sont-elles indépendantesentre elles ( 0 1 2< < < <n n nk.. ) ?
∑ Si aucun succès ne s'est produit pendant les m premiers intervalles de temps
de longueur h, quelle est la probabilité pour que k intervalles supplémentaires
se déroulent avant le prochain succès ?
3 – 2 - Loi PNnde Nn , et caractéristiques de PNn
.
La loi de Nn est donnée par P N kn
kp qn
k n k( )= =ÊËÁ
ˆ¯̃
- . Il s’agit de la loi binomiale de
paramètres (n,p).
� En effet la fonction génératrice de Nn est donnée par
G z q p z P N k zN
n
nk
k
n( ) . .= +( ) = =( )
=
+•
Â0
. Comme par ailleurs q p z C pz qn
nk
k
nk n k+( ) = ( )
=
-Â. .0
,
une simple identification nous donne : P k P N k C p q k nN n nk k n k
n( ) = =( ) = =-. ( , , ..., )0 1 2 . ☺
B.A. Ferrif
19/08/02
38
Espérance de Nn ? .
� Appliquons la méthode des fonctions génératrices :
G z q p z G z n q p z pN
n
N
n
n n( ) . , ( ) . .
'= +( ) ( ) = +( ) -1
, soit E N G n pn Nn( ) = ( ) =' .1
☺
Variance de Nn ?
� On a G z n n q p z pN
n
n( ) . .
''( ) = -( ) +( ) -1
2 2 , soit s 2 21 1 1N G G G n p qn N N Nn n n
( ) = ( ) + ( ) - ( )( ) ='' ' ' . .
☺
3 – 3 - Loi et caractéristiques de T1
T1 prend donc ses valeurs dans 1, 2, .. , n,....
� Loi de T1
En effet on a : T n X X X Xn n1 1 2 10 0 0 1={ } = = = = ={ }-, , ... , , . Comme les
variables aléatoires Xi sont indépendantes, on a :
P T n P X P X p pn ii
nn
10
11
1 0 1=( ) = =( ) =( ) = -( )=
--’. . .
Espérance de T1 ?
On a G z P T n z p p zp
qq z
p
q q zTn
n n
n
n n
n1 1
1
1
1 0
11
1( ) = =( ) = -( ) = ( ) =
-=
+•-
=
+•
=
+•
  Â. . . . ..
. Il
s'ensuit : Limd
dzG z Lim
p
zq pzT
zÆ Æ( ) =
-( )=
1 121 1
1
Variance de T1 ?
s 21
2
21 1 11 1 1T G G G
q
pT T T( ) = ( ) + ( ) - ( )( ) ='' ' '
☺
B.A. Ferrif
24/07/01
39
☺
3 - 4 - Loi PT Tn n- -1 du temps d’attente T Tn n- -1 entre les (n-1)-ème et n-ème
succès .
Il résulte directement du raisonnement précédent que : P T T n p pk k
n
+-- =( ) = -( )1
11
si n ≥ 1 . On reconnaît la loi géométrique d'espérance 1/p .
Loi de T T T1 2 1, -( )
�
On a
P T n T T n P X X X X X Xn n n n n n n( , ) ,..., , , ,..., ,1 1 2 1 2 1 1 1 10 0 1 0 0 11 1 1 1 2 1 2
= - = = = = = = = =( )- + + - +
soit P T n T T n q pq pn n( , )1 1 2 1 21 11 2= - = = - -
☺
3 – 5 - Indépendance des variables T T T T Tn n n n nk k1 2 1 1, ,..,- -
- (0 1 2< < < <n n nk.. )
� La simple extension du résultat précédent montre que les variables
T T T T Tn n n n nk k1 2 1 1, ,..,- -
- sont indépendantes entre elles ; de plus elles suivent la
même loi : P T T n p pk k
n
+-- =( ) = -( )1
11 si n ≥ 1 .
☺
3 – 6 - Loi de N Nm n- et caractéristiques de la loi.
� L’expression N Nm n- désigne le nombre de succès dans l'intervalle ]n ,m]
(avec 0 £ <n m ) . Il résulte directement du calcul de la loi de Nn que la loi de
N Nm n- est la loi binomiale de paramètres ( , )m n p- , soit donc
P N N km n
kp qm n
k m n k( )- = =-Ê
ËÁˆ¯̃
- - .
B.A. Ferrif
24/07/01
40
Le nombre moyen de succès dans l'intervalle ]n,m] est donc donné par
l'espérance E N Nm n-( ) de N Nm n- , soit E N N m n pm n-( ) = -( ). .
Variance de N Nm n- :
On a s 2 N N m n p qm n-( ) == -( ). .
☺
3 – 7 - Indépendance des variables aléatoires N N N N Nn n n n nk k1 2 1 1, ,..,- -
-
� Un raisonnement semblable au raisonnement précédent montre que les
variables aléatoires N N N N Nn n n n nk k1 2 1 1, ,..,- -
- sont indépendantes entre elles
(0 1 2< < < <n n nk.. ) .
☺
3 - 8 - P T k m T m= + ≥( )
� Cherchons la probabilité pour que k intervalles supplémentaires se déroulent
avant le prochain succès, sachant qu’aucun succès ne s'est produit pendant les
m premiers intervalles de temps de longueur h .
Cette probabilité est par définition
P T k m T mP T k m T m
P T m= + ≥( ) =
= +( ) « ≥( )[ ]≥( )
Comme on a :
T k m T m T k m= +( ) « ≥( ) = = +( ) et
P T m p q q qp q
qqm
mm≥( ) = + + +( ) =
-( ) =. ....
.11
2
Il s’ensuit :
P T k m T mpq
qpq P T k
m k
mk= + ≥( ) = = = =( )
+
soit :
B.A. Ferrif
24/07/01
41
P T k m T m pq P T kk= + ≥( ) = = =( ) .
☺
4 – Optimisation d’un chiffre d’affaires (Retour sur
l’exemple 1 - 5)
Rappel de la question : Il est de notoriété publique que les compagnies
aériennes, par exemple, pratiquent la surréservation c’est-à-dire vendent plus de
billets que de places disponibles dans les avions. Les modalités d’utilisation des
billets diffèrent suivant le type de billet et la catégorie tarifaire à laquelle il
appartient. Ainsi pour certains billets il peut y avoir remboursement intégral de
celui-ci s’il n’a pas été utilisé et une indemnisation si le passager n’a pas pu
embarquer.
Ces compagnies ont constaté qu’une proportion notable des détenteurs de billets,
elle peut atteindre 50%, ne se présente pas à l’embarquement. Elles sont
conduites à chercher à optimiser leur chiffre d’affaires en pratiquant la
surréservation (puisque le nombre de places dans l’avion, le prix de la place, et
les modalités d’utilisation des billets sont fixés au moment de la vente). Cette
pratique n’est pas sans risque, notamment pour l’image de la compagnie. Comme
le chiffre d’affaires dépend de la présence aléatoire du nombre de passagers ,
des questions vitales se posent aux compagnies aériennes :
Peut-on construire un modèle permettant de gérer ce problème de manière
optimale?
En amont de la question précédente, existe-t-il une méthode permettant de
déterminer le prix de vente du billet de manière à optimiser le chiffre d’affaires
tout en restant concurrentiel ?
B.A. Ferrif
24/07/01
42
Nous ne résoudrons pas ce problème dans toute sa généralité, c’est-à-dire en
considérant tous les segments tarifaires et tous les types de billets avec leurs
modalités d’utilisation. Nous allons réduire la complexité du problème, afin de
dégager une méthode de résolution du cas suivant, qui nous permettra d’obtenir
le germe d’une étude plus générale.
Supposons que nous disposions d’un avion qui possède N sièges et que la
compagnie ne pratique qu’un seul segment tarifaire et une modalité d’utilisation
unique sur ce vol : les billets sont proposés au prix a et sont intégralement
remboursés s’ils sont inutilisés ; de plus le passager et indemnisé s’il ne peut pas
embarquer pour cause de surréservation.
Comment optimiser le chiffre d’affaire de cette compagnie ?
Modélisation :
Valeur de l’indemnisation : Cette indemnisation peut prendre une forme
forfaitaire ou proportionnelle ; la valeur d’indemnisation est bien entendu fonction
du prix du billet, son montant I a( ) est tel que I a a( ) > (pour que ce soit une
indemnisation), il sera donc de la forme I a a( ) = +( ) +1 a b. avec
a b a b, ≥ + >0 0et .
Si a = 0 l’indemnisation est forfaitaire, si b = 0 l’indemnisation est proportionnelle.
Présence d’un passager à l’embarquement : On fait l’hypothèse qu’un
détenteur de billet se présente à l’embarquement avec la probabilité p et que les
comportements des passagers sont indépendants les uns des autres. (Cette
B.A. Ferrif
24/07/01
43
probabilité p est établie et affinée par des méthodes statistiques en consultant
l’historique des vols précédent).
Désignons par n le nombre de billets vendus et par X V V Vn n= + + +1 2 ... le nombre
de passagers présents effectivement à l’embarquement, où Vi est une variable
aléatoire qui vaut 1 si le passager est présent et 0 sinon.
Pour un total de n billets vendus, le chiffre d’affaires CAn de la compagnie est de :
CA n a a n X I a X N c X Nn n n n= - -( ) - ( ) -( ) - -( ). . . . (le second terme correspondant
aux remboursements des absents, le troisième terme à l’indemnisation des
passagers malheureux), le quatrième terme représente le montant associé au
risque de perdre ces client à jamais (c est choisi pour représenter en termes
monétaires le risque de perdre ce client à jamais). Négligeons, dans un premier
temps, le quatrième terme et posons CA n a a n X I a X Nn n n= - -( ) - ( ) -( ). . . .
Réaliser une optimisation du chiffre d’affaires a priori ne peut s’imaginer qu’en
moyenne. On doit donc optimiser la fonction :
E CA E n a a n X I a X Nn n n( ) = - -( ) - ( ) -( )( ). . . .
Résolution du problème réduit
La suite Xn n N( ) Πest un processus de Bernoulli.
On sait que E X n p et X n p pn n( ) = ( ) = -( ). . .s 2 1 . Il en résulte :
E CA E n a a n X I a X N
a E X I a E X N
a n p I a E X N
n n n
n n
n
( ) = - -( ) - ( ) -( )( )= ( ) - ( ) -( )= - ( ) -( )
. . .
. .
. . .
Nous sommes donc amenés à chercher le maximum, s’il existe, de la fonction
n E CAnÆ ( ) donc le premier entier γ tel que E CA E CAn n+( ) - ( )1 change de signe.
B.A. Ferrif 44
24/07/01
Or E CAn +1( )− E CAn( )= a.p − I a( ).p.P X n ≥ N( ) ; il s’ensuit que E CAn +1( )− E CAn( )
change de signe une seule fois en
>≥≥=)(
)(minaIa
NXPNn nγ .
Simulation
Ecrire un programme informatique permettant de calculer )(),(, γγ CAENXP n ≥ et
tabuler les résultats en fonction du nombre de places N et ceci pour différents taux
d’indemnisation et pour différentes valeurs de p.
5- Processus gaussien.
Nous nous limitons ici à l’énoncé de la définition des processus Gaussiens. Ces
derniers seront étudiés plus en détail dans le module « Signal aléatoire ».
Soit (Xt) t∈R un processus stochastique. Se donner la loi du processus stochastique
c'est se donner la loi du vecteur ( Xt 1, X t 2
,.., X t n
) pour tout n ∈ N , t1
, t2
, .., tn ∈R .
1- Définition d’un processus gaussien.
Nous dirons que le processus stochastique (Xt) t∈R est gaussien si et seulement si
∀n ∈N , ∀t1, t2,.., tn ∈ R , (Xt 1, X t2 , ..,X t n ) est un vecteur gaussien.
B.A. Ferrif
24/07/01
45
2- Bruit blanc échantillonné gaussien.
Soit ( )Xn n NΠun processus stochastique. On dit que ( )Xn n NΠest un bruit blanc
échantillonné si les variables aléatoires Xn sont toutes centrées, indépendantes,
de même loi et de même écart-type. Si de plus, pour tout n, les variables
aléatoires Xn sont gaussiennes, le bruit blanc sera dit gaussien.
3- Simulation
Simuler un bruit blanc gaussien. (La figure précédente est le résultat d’une telle
simulation).
6 – Etude du Processus de Wiener
Soit Xn n N( ) Œ un processus aléatoire représentant une marche aléatoire défini par
X X Un n n+ = +1 où Un est une suite de variables aléatoires indépendantes, de
même distribution, à valeurs dans l’ensemble -{ } Ã -[ ]r r r r, , et telle que
" Π-( ) = ( ) =n N P r P rU Un n,
12
.
Désignons par T l’intervalle de temps entre deux déplacements et posons X0 0= .
Pour passer de ce processus aléatoire discret à un processus continu, on fait
tendre n vers l’infini et T vers zéro en conservant le rapport r
Tc
2
= constant . Le
processus limite ainsi obtenu s’appelle le processus de Wiener.
B.A. Ferrif
24/07/01
46
Etudier le processus aléatoire ainsi défini. (On cherchera en particulier sa fonction
d’autocorrélation (cf la définition dans l’appendice à la fin du chapitre)) .
Moyenne et variance de Xn .
On a : X Un ni
n
==
Â1
, E U r rn( ) = - =12
12
0 ; il s’ensuit , comme toutes les variables
sont indépendantes, que
∑ E X E Un ni
n
( ) = ( ) ==
Â1
0 ,
∑ s s2 2
1
2X U n rn ni
n
( ) = ( ) ==
 .
Loi de P X k rn =( ). .
Xn prend ses valeurs dans k r k Z. Œ{ } .
Les Un sont assimilables à des variables de Bernoulli et Xn est assimilable à un
processus de Bernoulli. La probabilité pour que le nombre de déplacements
positifs soit égal à m suit une loi binomiale de paramètre 12
soit donc
12
0ÊËÁ
ˆ¯̃ Œ{ }
n
nmC m n, ,..., .
La somme des déplacements peut s’écrire k m n k= - -( ) ; on a donc
" Π-{ }k n n,...,
P X k r Cn
n
n
k n
=( ) = ÊËÁ
ˆ¯̃
+
.12
2 .
B.A. Ferrif
24/07/01
47
Etude de la forme limite de la loi PX nde Xn .
Désignons la durée de l’observation par t n T= . , et par c la limite de r
T
2
lorsque T
tend vers 0 (on impose au rapport r
Tc
2
= de rester constant) .
On a :
∑ E Xn( ) = 0 ,
∑ s 2 2 2X n rt
Trn( ) = =. .
Lorsque T Xt
Tr c tnÆ ( ) = Æ0 2 2, . .s .
La variance est donc proportionnelle au temps. Par le théorème de la limite
centrale, on déduit, lorsque n tend vers l’infini, que la loi de Xn est une loi de
Gauss, centrée, de variance c t. .
Fonction d’autocorrélation.
On a : " > -( ) -( )( ) =n m E X X X Xn m m, . 0 0 car les intervalles 0, ,m et m n[ [ [ [ sont
disjoints et les accroissements sont décorrélés et centrés. (Conséquence de ce
que la suite Un( ) est indépendante et équidistribuée).
Il en résulte que E X X E X Xn m m m. .( ) = ( ) ; par suite on a E X X m rn m. .( ) = 2.
Le passage à la limite donne, pour le processus continu, E X X s r t st s. . ,( ) = >2 .
7 - Etude de modélisation – simulation – estimation.
Un capteur de particules est constitué d’une boîte rectangulaire (cf.fig), dont on
assimilera la face avant à un segment, percé en son centre d’une fente qui va
fonctionner comme une porte à particules. Les particules arrivent successivement
B.A. Ferrif
24/07/01
48
sur cette paroi, réparties de manière uniforme. On supposera que l’émission des
particules se fait tous les tops d’une horloge et on prendra la durée d’inter-
émission comme unité de temps.
On s’intéresse plus particulièrement à la distribution des temps d’attente entre le
passage de deux particules dans la fente.
Modéliser cette situation. Simuler le dispositif et, à l’aide de la simulation,
estimer la loi demandée. Que peut-on en induire ?
B.A. Ferrif
24/07/01
49
2-Appendice
Compléments
Cet appendice regroupe un certain nombre de définitions ; il doit être ignoré
en première lecture. Il y sera fait référence en cas de nécessité.
A - 1 - Moments
Pour rendre compte du degré de régularité des trajectoires, on introduit les
fonctions de covariance ou d'autocorrélation.
Si, pour tout t, la variable aléatoire Xt admet une espérance E(Xt) = Et finie, les
variables aléatoires Xt définissent des fonctions du temps.
On introduit alors, étant donnés deux instants t et s,
-la fonction de covariance du processus : K(s,t) = Cov(Xs,Xt),
-la fonction d’autocorrélation du processus : R(s,t) = E(Xs.Xt),
-la fonction de corrélation:
rs s
( , )( , )
( ) ( )s t
K s t
s t= où s s s s( ) ( ) ( ) ( )s X et t Xs t= = ,
- le coefficient CX
E XX =s 2
2
( )
( ).
A - 2 - Processus de deuxième ordre
Un processus ( )Xt t IΠest dit de second ordre si, et seulement si ,
" Œ ( ) < •t I E Xt, 2 .
B.A. Ferrif
24/07/01
50
A - 3 - Densité spectrale de puissance
La transformée de Fourier de la fonction d’autocorrélation s’appelle la densité
spectrale de puissance .
A - 4 - Stationnarité
1 - On dit d'un processus qu'il est stationnaire au sens strict si sa loi de probabilité
est invariante par translation sur t ; autrement dit si P et PX Xt t +t ont les mêmes
caractéristiques .
2 - Remarque : Si pour un grand nombre de processus physiques on constate
cette propriété de stationnarité, ce n'est pas le cas, en général, pour les
processus économiques.
3 - Processus stationnaire d’ordre 2 : Un processus stationnaire d’ordre 2 est
un processus du second ordre tel que :
" Π( ) = " Π( ) = + +( )s I E X et h I C s t C s h t hs, , , ,m .
A - 5 - Bruit blanc
On appelle bruit blanc tout processus aléatoire stationnaire, du deuxième ordre,
centré, dont la densité spectrale de puissance est constante sur tout l’axe des
fréquences.
B.A. Ferrif
24/07/01
51
A - 6 - Ergodicité
1 - Un système sera dit ergodique s'il tend (aux divers sens du calcul des
probabilités) vers un état limite indépendant de la situation initiale.
La recherche de conditions nécessaires et de conditions suffisantes d'ergodicité
sont à la base de la théorie ergodique.
2 - Théorème ergodique.
1- Un processus stationnaire ( )Xt t ZΠdu second ordre sera dit ergodique si :
nk s
k n
n
k k s kLim nX X E X X presque sûrement
Æ •+
= -+Â = ( )1
2.
2- Un processus stationnaire ( )Xt t RΠdu second ordre sera dit ergodique si :
Tt sT
T
t k s kLim TX X dl t E X X presque sûrement
Æ •+-
+
+Ú = ( )12
( ) .
Ce résultat indique qu’un processus stationnaire ergodique de puissance
moyenne finie a son autocorrélation temporelle en puissance égale à E X Xk s k+( ).
B.A. Ferrif
24/07/01
52
2-Chaînes de Markov
B.A. Ferrif
24/07/01
53
I-Introduction
La structure de chaîne de Markov modélise un type particulier de processus
stochastiques : les processus "sans mémoire" et pour lesquels les changements
d'état se produisent à des instants déterminés. Dans certaines situations où la
mémoire du passé intervient, le concept de processus de Markov sera étendu et
précisera le niveau de mémoire nécessaire.
La découverte en est due à Markov, qui l’a dégagée d’une étude statistique sur la
dépendance entre certaines lettres d’un texte littéraire [étude de l’alternance des
voyelles et des consonnes dans "Eugène Oneguine" de Pouchkine], considéré
pour l’occasion comme suite de symboles. Il est intéressant de penser qu’un
siècle plus tard, le modèle et la problématique sous-jacente sont utilisés avec
succès aussi bien dans des projets de haute technologie que dans la gestion des
organisations.
Cette structure se retrouve fréquemment comme modèle de phénomènes
naturels et les modèles markoviens se révèlent très efficaces dans de multiples
secteurs; en particulier :
∑ dans les systèmes assimilables à des réseaux de files d’attente, par exemple
dans le domaine des télécommunications avec les réseaux à commutation de
paquets ;
∑ dans les organisations de gestion : affectation de personnel, systèmes de
maintenance ;
∑ en démographie, pour étudier l’évolution de la taille d’une population ;
∑ en vie artificielle, pour étudier l’évolution d’une population sous l’influence des
facteurs de mutation et de sélection ;
B.A. Ferrif
24/07/01
54
∑ en physique, pour étudier les mouvements de particules sur les réseaux ;
∑ dans les systèmes de reconnaissance des formes ;
∑ …….
Le concept de chaîne de Markov cachée que nous introduirons en conclusion est,
quand à lui, à la base de nombreux algorithmes dans un grand nombre de
domaines (par exemple dans la reconnaissance du langage naturel ou encore
dans le séquençage du génome).
II-Prérequis et Objectifs
Ce que vous devez au minimum maîtriser pour aborder de ce chapitre :
∑ Probabilités : Concepts d’espace probabilisé, de variable aléatoire, de
dépendance et d’indépendance (en théorie des probabilités); la formule de
Bayes.
∑ Algèbre : Algèbre matricielle.
Ce que vous devez maîtriser pour tirer pleinement profit de ce chapitre :
∑ Probabilités : Concepts d’espace probabilisé, de variable aléatoire, de
dépendance et d’indépendance (en théorie des probabilités); la formule de
Bayes.
∑ Algèbre : l’algèbre matricielle, les notions de base de la théorie des graphes.
∑ Informatique: des éléments de programmation et des éléments de
programmation sous Mathematica
B.A. Ferrif
24/07/01
55
Ce que vous devez savoir faire à la fin de cette leçon :
∑ Savoir reconnaître un modèle markovien,
∑ Savoir en déterminer les principales caractéristiques,
∑ Savoir le modéliser et le simuler.
Ce qui vous est proposé dans ce chapitre :
∑ Apprendre les concepts fondamentaux,
∑ Apprendre à modéliser et à simuler des processus markoviens,
∑ S’exercer sur des applications immédiates,
∑ Réfléchir sur des problèmes concrets et de synthèse,
∑ S’évaluer par tests de connaissance et de savoir-faire.
B.A. Ferrif
24/07/01
56
1-Processus et Chaînes de Markov
1-1-Définition des Processus de Markov
Un processus aléatoire ( )Xt t In n Œ est un processus de Markov (on dit parfois
processus de Markov d'ordre 1 ou de mémoire 1) s'il vérifie l'axiome suivant
fréquemment appelé propriété de Markov :
"( ) Œ < < < < "( ) Œ-+
- -+t t t t I t t t t x x x x En n
nn n n n
n0 1 1
10 1 1 0 1 1
1, ,..., , , ... , , ,..., , ,
P X x X x X xt t t t t tn n( ,..., , )
- -= = = >
1 1 1 1 0 00 ,
P X x X x X x X x P X x X xt t t t t t t t t t t tn n n n n n n n n n= = = =( ) = = =( )- - - - - -1 1 2 2 0 0 1 1
, ,..., .
Autrement dit :
La propriété de Markov exprime que l'état futur Xtn ne dépend pas des états
passés X i nti, , , ,.., ,Œ -{ }0 1 2 2 mais seulement de l'état présent Xt n -1 . Ainsi cette
propriété précise l'absence de mémoire du processus.
Chaîne et processus de Markov
1-Un processus de Markov tel que I=N et E dénombrable s'appelle une chaîne de
Markov à temps discret.
2-Un processus de Markov tel que I=N et E diffus s'appelle un processus de
Markov à temps discret.
3-Un processus de Markov tel que I=R et E dénombrable s'appelle une chaîne de
Markov à temps continu.
4-Un processus de Markov tel que I=R et E diffus s'appelle un processus de
Markov à temps continu.
B.A. Ferrif
24/07/01
57
1-2-Analogie déterministe
L'analogue déterministe d'un processus de Markov ( )Xt t In n Œ est un processus
d'évolution ( , )x t Nt Œ qui est décrit par une équation de récurrence du premier
ordre de la forme x f x tt t+ = ( )1 , plutôt que par une relation du type
x F x x x tt t t+ -= ( )1 1 0, ,..., , . Lorsque le phénomène est aléatoire les fonctions
x f x tt t+ = ( )1 , et x F x x x tt t t+ -= ( )1 1 0, ,..., , sont remplacées par les lois de probabilité
conditionnelle de la condition de Markov.
1- 3 – Exemple de chaîne de Markov : Marche aléatoire entre deux bornes
On considère un signal dont l’amplitude est comprise entre 0 et 5A et qui ne peut
prendre que des valeurs qui sont des multiples de A.
À tout instant n, si le signal vaut A, 2A, 3A ou 4A, il peut soit rester constant, soit
augmenter de A, soit diminuer de A avec équiprobabilité.
À tout instant n, si le signal vaut 0, il peut soit rester constant, soit augmenter de
A, avec équiprobabilité.
À tout instant n, si le signal vaut 5A, il peut soit rester constant, soit diminuer de
A avec équiprobabilité.
1 – 4 – Simulation
Ecrire un programme permettant de simuler une marche aléatoire entre 2 bornes.
1 – 5 – Exemple de chaîne de Markov : Marche aléatoire avec absorption
On considère un signal dont l’amplitude est comprise entre 0 et 5A et qui ne peut
prendre que des valeurs qui sont des multiples de A.
B.A. Ferrif
24/07/01
58
À tout instant n, si le signal vaut A, 2A, 3A ou 4A, il peut soit rester constant, soit
augmenter de A, soit diminuer de A avec équiprobabilité.
À tout instant n, si le signal vaut 0, il conserve la valeur 0.
À tout instant n, si le signal vaut 5A, il conserve la valeur 5A.
1 – 6 – Simulation
Ecrire un programme permettant de simuler une marche aléatoire avec
absorption.
1- 7 - Homogénéité d'un processus de Markov
Un processus de Markov est dit homogène s'il vérifie la propriété suivante :
Propriété d'homogénéité
" Π" Π= = = = =-( , ) , ( , ) , ( ) ( )s t I x y E P X y X x P X y X xs t s t2 2
0
Autrement dit :
La propriété d'homogénéité ou de stationnarité temporelle des transitions précise
que la probabilité de transition d'un état à un autre ne dépend que du temps
écoulé entre ces 2 états, ici (s - t), et non des instants de transition.
Tous les processus de Markov qui seront considérés dans ce cours seront
désormais homogènes sauf mention explicite du contraire.
1- 8 - Probabilité de transition de l'état x à l'état y pour un processus
homogène
La probabilité de transition de l'état x à l'état y, entre les instants n et n+1 est
indépendante de n. Plus précisément :
B.A. Ferrif
24/07/01
59
" ( ) Π" ( ) Π= = = = =+ +m n N x y E P X y X x P X y X xn n m m, , , , ( ) ( )2 21 1 .
Cette probabilité sera notée pxy ; c'est donc la probabilité de passer de l'état x à
l'état y en une seule transition, c'est-à-dire en une seule étape.
Critère : pour démontrer la propriété d'homogénéité d'une chaîne il est suffisant
de démontrer que :
" ( ) Œ = = =+x y E p P X y X xxy n n, , ( )21 est indépendante de n.
1- 9 - Matrice de transition d'une chaîne de Markov homogène
Lorsque x et y décrivent E les pxy décrivent une matrice que l'on appelle la
matrice de transitions ou matrice de la chaîne de Markov, elle sera notée
P pxy x y E= ( )
Œ,.
On a :
- " ( ) Œ = = = ≥+x y E p P X y X xxy n n, , ( )21 0
- " Œ =Œ
Âx E pxyy E
, 1 .
1- 10 - Exemples de matrice de transition :
Les matrices suivantes sont les matrices de transition d'un processus de Markov
∑ dont l'espace d'état E = { }1 2 3, , possède 3 éléments :
012
12
12
012
12
12
0
Ê
Ë
ÁÁÁÁÁ
ˆ
¯
˜˜˜˜˜
B.A. Ferrif
24/07/01
60
∑ dont l'espace d’état E = { }1 2 3 4, , , possède 4 éléments :
12
12
0 0
012
12
0
12
0 012
12
12
0 0
Ê
Ë
ÁÁÁÁÁÁÁÁ
ˆ
¯
˜˜˜˜˜˜˜̃
∑ dont l'espace d’état E = { }1 2 3 4 5 6 7 8 9 10, , , , , , , , , possède 10 éléments
0 0 0 014
034
0 0 0
0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0 0 012
0 0 016
013
0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 034
014
0 0 0
0 0 0 0 0 1 0 0 0 0
0 035
0 015
0 015
0
0 0 013
13
013
0 0 0
Ê
Ë
ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ
ˆ
¯
˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜
1 - 11 - Exercice :
Ecrire les matrices de transition des exemples (1-3) et (1-5)
1 - 12 - Préparation des simulations
La matrice de la chaîne de Markov permet de simuler, par exemple sous
Mathematica qui sera le logiciel pris en exemple dans cet enseignement, un
B.A. Ferrif
24/07/01
61
grand nombre de problèmes. Pour entrer la matrice vous pouvez utiliser la palette
"basic input" du sous-menu "palette" du menu "File" ;
∑ pour ajouter une colonne taper simultanément [ctrl]+[,] ;
∑ pour ajouter une ligne taper simultanément [ctrl]+[Return].
1- 13- Graphe d'une chaîne de Markov homogène
Lorsque l'espace d'états est fini, on peut associer à la chaîne de Markov, donc à
la matrice de transition, un graphe orienté dont les sommets représentent les
états et les flèches les probabilités non nulles de transition entre états;
généralement l'arête orientée de l'état x vers l'état y portera l'indication de la
probabilité pxy . (cf. Appendice Graphes)
Les graphes de transition des chaînes de Markov correspondant aux deux
premières chaînes de Markov des exemples (1 –10) sont donnés par les figures
suivantes :
B.A. Ferrif
24/07/01
62
1 2 3 4
1 / 2
Graphe du processus
1 / 21 / 2
1 / 2
1 / 2
1 / 2
1 / 2
1 / 2
1- 14 - Exercice
Dessiner le graphe de la troisième chaîne.
1- 15 - Simulation
Ecrire un programme permettant de visualiser le graphe correspondant à des
matrices de dimensions raisonnables.
Ecrire un programme qui associe à la matrice de la chaîne de Markov, la matrice
d'adjacence du graphe de cette chaîne. Appliquer à la matrice de l’exemple 1).
1- 16 - Exercice
Ecrire les matrices de transition des exemples (1-3) et (1-5).
B.A. Ferrif
24/07/01
63
2- Transition d'ordre supérieur
2-1 – Notations et définitions
Nous désignerons par pxyn( ) la probabilité de transition de l'état x à l'état y en n
étapes.
On pose par définition pxy xy( )0 = d (=1 si x=y , 0 sinon).
Autrement dit: pxyn( ) est la probabilité conditionnelle d'atteindre y après n étapes
partant de l'état x.
Autrement dit : Cette probabilité est la probabilité de l'ensemble de tous les
chemins possibles d'origine x d'extrémité y et de longueur n dans l'espace des
états.
2-2-Equations de Chapman-Kolmogorov
Proposition : Soit une chaîne de Markov homogène à temps et états discrets.
1- On a : " Π" Π= = =( )+m n N x y E p P X y X xxyn
m n m, , , , ( )
En d'autres termes la puissance n-ième Pn de la matrice de transition P, est la
matrice de transition en n étapes. L’élément pxyn( ) est situé à la ligne x et à la
colonne y.
2- Si on pose : P p P pnxyn m
xym= ( ) = ( )( ) ( ), , on a les équations de Chapman-
Kolmogorov
p p pxzm n
xym
yzn
y E
( ) ( ) ( ).+
Œ( ) =
Ê
ËÁˆ
¯̃Â
en d’autres termes P P Pm n m n+ = . .
� En effet la règle de Bayes séquentielle donne
B.A. Ferrif
4/07/02
64
" Π" Π= = =( ) =+-
-Âm n N x y E p P X y X x p pxyn
m n m xxx x x
x y
n
n, , , , ..( )
, ,..,1
1 2 1
1
On a
" Π" Π=+
ŒÂm n N x z E p p pxz
m nxym
yzn
y E
, , , , ( ) ( ) ( )
où p pxym
yzn( ) ( ) est la probabilité que, partant de l’état x, la processus atteigne l’état z en
m+n transitions par un chemin qui passe par l’état y à la mème transition.
On en déduit la relation matricielle : P P Pm n m n+ = où P p P pnxyn m
xym= ( ) = ( )( ) ( ), e t
P p p pm nxzm n
xym
xzn
y E
+ +
Œ= ( ) =
Ê
ËÁˆ
¯̃Â( ) ( ) ( ) et en particulier on a p p pxz
nxyn
yzy E
( ) ( ) ( )+
Œ= Â1 1 ☺
2-3- Exercice
Pour chacun des processus de Markov définis ci-dessous, donner " Œi j E Pij, , ( )3
∑ Processus dont l'espace d'état E = { }1 2 3, , possède 3 éléments et de matrice
de transition :
012
12
12
012
12
12
0
Ê
Ë
ÁÁÁÁÁ
ˆ
¯
˜˜˜˜˜
∑ Processus dont l'espace d’état E = { }1 2 3 4, , , possède 4 éléments et de matrice
de transition :
B.A. Ferrif
4/07/02
65
12
12
0 0
012
12
0
12
0 012
12
12
0 0
Ê
Ë
ÁÁÁÁÁÁÁÁ
ˆ
¯
˜˜˜˜˜˜˜̃
2-4- Simulation
Ecrire un programme permettant d'obtenir les puissances successives, sous forme
booléenne, de la matrice d'adjacence de la matrice P d'une chaîne de Markov . La
puissance n-ième de la matrice d'adjacence est-elle égale à la matrice d'adjacence
de la puissance n-ième de P ?
2-5- Loi initiale de la chaîne de Markov.
La loi de la variable aléatoire Xo s'appelle la loi initiale. (Cette loi, connue dans les
applications, est définie, rappelons-le, par " Œ = =x E P X x px, ( ) .0
C'est une loi de probabilité sur l'espace des états.
2-6 - Loi de probabilité de Xn.
Le théorème suivant va nous permettre de trouver la loi PX n de Xn pour tout entier
positif n . Il est connu sous le nom de théorème de Markov.
Théorème : A tout instant n la loi de probabilité PX n de Xn est donnée par :
P P PX Xn n+=
1. , P P PX X
n
n=
0.
B.A. Ferrif
24/07/01
66
�Posons p P X x P xxn
n X n
( ) ( ) ( )= = = ; on a : p P X y P y p pyn
n X x xyn
x Nn
( ) ( )( ) ( ) .= = = =Œ
Â
avec " Π= =x E p P X xx, ( )0 .
La formule précédente s'obtient par simple application de la règle de Bayes
séquentielle; il est alors clair que la matrice de transition P pxy x y E= ( )
Œ, et la loi
initiale P X x px x E( ) ( )
00= =( ) Œ
déterminent PX n pour tout n . ☺
La loi PX nde Xn , notée parfois P PX nn
= , est donc une loi marginale au sens
habituel du terme.
2-7- Une caractérisation d'une chaîne de Markov homogène
Tout processus aléatoire à temps et à états discrets vérifiant :
" Π"( ) Π= = = = =+- - -
n N x x x E P X x X x X x P X x p p pt t tn
t t t t t t t t x x x x x xn n n n n t t t t tn tn, , , ... , , ( , ,..., ) ( ). . ... .
0 1 1 1 0 0 0 0 0 1 1 2 1
1
est une chaîne de Markov de loi initiale PX 0 et de matrice P pxy x y E
= ( )Œ,
..
3- Relations de communication entre états dans l'espace
des états d'une chaîne de Markov homogène.
3-1 - Relation de communication sur l'espace d'états E.
3-1-1 - On dit que l'état x conduit à l'état y (ou que y est atteignable à partir de x)
si et seulement si: $ Π>n N pxyn, ( ) 0 .
B.A. Ferrif
24/07/01
67
3-1-2 - On dit que x et y communiquent si et seulement si l'état x conduit à y et
l'état y conduit à x.
Autrement dit si et seulement s'il existe des entiers m et n tels que pxym( ) > 0 et
pyxn( ) > 0 .
3-2 - La relation de communication est une relation d'équivalence.
Il s'ensuit que la donnée d'une chaîne de Markov définit sur son espace d'états E
une partition en classes d'équivalence qui sont (donc) des classes de
communication disjointes.
Une chaîne à une seule classe sera dite irréductible.
3-3- Test
Les chaînes suivantes sont-elle irréductibles ?
i)
012
12
12
012
12
12
0
Ê
Ë
ÁÁÁÁÁ
ˆ
¯
˜˜˜˜˜
ii)
12
12
0 0
012
12
0
12
0 012
12
12
0 0
Ê
Ë
ÁÁÁÁÁÁÁÁ
ˆ
¯
˜˜˜˜˜˜˜̃
iii)
B.A. Ferrif
24/07/01
68
0 0 0 014
034
0 0 0
0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0 0 012
0 0 016
013
0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 034
014
0 0 0
0 0 0 0 0 1 0 0 0 0
0 035
0 015
0 015
0
0 0 013
13
013
0 0 0
Ê
Ë
ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ
ˆ
¯
˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜˜
3-4- Simulation
Pour réaliser automatiquement une partition de l'espace des états en classes de
communication, on peut utiliser la fermeture transitive du graphe correspondant à
la matrice d'adjacence. Ecrire un programme permettant de réaliser cette
opération.
3-5- Remarque
La classification des états à l’aide des propriétés des graphes n’est strictement
équivalente à la classification probabiliste que dans le cas des chaînes de Markov
à espace d’états fini.
3-6- Parties fermées et parties absorbantes.
3-6-1-Définitions:
1- Une partie C de l'espace des états sera dite fermée si et seulement si
P X C X Cn n+ Œ Œ( ) =1 1.
B.A. Ferrif
4/07/02
69
2- Une partie C de l'espace des états sera dite absorbante si et seulement si
pour tout x P P X x où n N X Cx C C C nt t t< +•( ) = < +• =( ) = = Œ Œ{ }0 1 inf ,
3- Pour une partie arbitraire C de l'espace des états, la plus petite partie
fermée contenant C est appelée la fermeture de C.
4- Un état k d'une chaîne de Markov est dit absorbant si le processus ne peut
plus quitter cet état une fois qu'il y est entré; en d'autre termes si pkk = 1
3-6-2-Chaînes de Markov homogènes absorbantes.
Définition: Une chaîne de Markov est dite absorbante si elle possède au moins un
état absorbant et si l'on peut passer de n'importe quel état à un état absorbant.
3-6-3-Délais d'absorption et probabilités d'absorption
Lorsqu'une chaîne de Markov est absorbante, on se pose naturellement les
questions suivantes:
� Combien de temps faudra-t-il pour que le processus soit absorbé, étant donné
son état initial?
� S'il existe plusieurs états absorbants, quelle est la probabilité pour un
processus d'être absorbé par un état donné?
Pour répondre à ces questions nous allons introduire les quantités suivantes:
∑ Ni = nombre de transitions jusqu'à l'absorption en partant de l'état i (Ni est
une variable aléatoire discrète),
ni = E (Ni) = temps moyen jusqu'à l'absorption en partant de i,
B.A. Ferrif
24/07/01
70
∑ bij = probabilité que le processus soit absorbé dans j si son état initial est i.
Pour les deux dernières quantités, on a immédiatement :
∑ ni = 0 si i est absorbant,
∑ bii = 1 si i est absorbant,
∑ bij = 0 si i est absorbant et j π i.
Considérons maintenant des chaînes de Markov comprenant plusieurs états
absorbants. Le théorème suivant permet alors de calculer la probabilité que le
processus soit absorbé par un état donné.
3-6-4 - Théorème - Les nombres ni sont les solutions du système d'équations
n p ni ik kk S
= +Œ
Â1 .©
où i est un état non absorbant et S' l'ensemble de tous les états non absorbants.
�Supposons que la chaîne a un état absorbant j, désignons par i l'état initial (i
différend de j) et par Ak l'évènement : le processus passe de i à k lors de la
p r e m i è r e t r a n s i t i o n . O n a :
E N E N A P A E N p E N pi i kk S
k kk S
ik kk S
ik( ) = ( ) ( ) = ( ) +[ ] = + ( )Œ Œ Œ
  Â1 1. .©
☺
3-6-5 - Théorème - Soit j un état absorbant et S' l'ensemble de tous les états non
absorbants. Alors les probabilités bij (i SŒ ©) sont les solutions du système
d'équations :
b p p bij ij ik kjk S
= +Œ
 .©
B.A. Ferrif
24/07/01
71
�Cela résulte directement du théorème des probabilités totales. En effet si A
désigne l'ensemble des états absorbants, on a :
b p b p b p b p b pij ik kjk S
ik kjk S
ik kjk A
ik kjk S
ij= = + = +Œ Œ Œ Œ
   Â. . . . .© ©
1 ☺
Plus généralement :
3-7- Temps d'atteinte et probabilités d'atteinte
3-7-1-Théorème du temps d'atteinte : Soit Xn n N( ) Œ une chaîne de Markov
homogène de matrice de transition P pij i j E= ( )
Œ, . Désignons par C un sous-
ensemble de l’espace des états E, par B le complémentaire de C dans E, et par
tC nn N X C= Œ Œ{ }inf , (tC = +• si le processus n’atteint jamais C). Posons,
pour tout i dans E, n E X ii C n= =( )t .
On a :
∑ pour tout i dans B , n p ni ik kk B
= +Œ
Â1 . ;
∑ pour tout i dans C , ni = 0 .
3-7-2-Théorème de la probabilité d'atteinte : Soit Xn n N( ) Œ une chaîne de
Markov homogène de matrice de transition P pij i j E= ( )
Œ, . Désignons par A et B
deux sous-ensembles fermés et disjoints de l'espace des états E, et
supposons A BU absorbant .
Posons u i P P X ii A B i A B( ) = <( ) = < =( )t t t t 0 , alors on a
∑ u i p u jijj E
( ) . ( )=Œ
 ;
∑ u i si i A et u i si i B( ) ( )= Œ = Œ1 0 .
B.A. Ferrif
24/07/01
72
3-7-3- Test
Un jeu!
Trois enfants sont placés chacun à un sommet d’un triangle équilatéral. Toutes
les dix secondes (prises comme unité de temps), chacun, indépendamment des
deux autres, choisit de se rendre en l’un des deux autres sommets (avec
équiprobabilité). Au bout de combien d’unités de temps en moyenne les trois
enfants se retrouveront-ils au même sommet ?
4- Périodicité des états d'une chaîne de Markov à temps
et états discrets.
Nous allons classer les états d'une chaîne de Markov homogène en états
persistants et états transitoires ainsi qu'en états périodiques et apériodiques afin
de pouvoir préciser les réponses aux questions suivantes :
∑ La chaîne peut-elle repasser par un état i ?
∑ Si oui, ce nouveau passage s'effectue-t-il dans un temps moyen fini ou infini ?
4-1- Notations et définitions
Notons Tji[ ] le temps mis par la chaîne de Markov pour retourner une jème fois à
son état initial i.
On montre que pour tout j, les T Tji
ji
+[ ] [ ]-1 sont de même loi, dépendant de i.
Désignons par T i[ ] la variable aléatoire de loi commune aux T Tji
ji
+[ ] [ ]-1 .
Posons T Min n X j X iijn N
n= = ={ }Œ
, 0 , Tij est le temps de premier passage en j en
partant de i.
B.A. Ferrif
4/07/02
73
Notons f P X j X j X j X iijn
n n( ) ( , ,.., )= = π π =-1 1 0 la probabilité d'être pour la première
fois en l'état j au temps n, étant parti de l'état i au temps 0.
Il est clair que f P T nijn
ij( ) = =( )
Posons :
∑ fij( )0 0= ,
∑ F fijn
ijk
k
n( )
== Â ( )
1
∑ f f F F P X j X iij ij
nij ij n
nn
= = = = =[ ] =ÊËÁ
ˆ¯̃
+•( )
=
+•
=
+•
 ( )0
11U
∑ m j jjn
n
n f==
+•
 . ( )
1
.
Il est clair que fkj est la probabilité que, partant de l’état k, le système atteigne l’état j.
Il s'ensuit que fkj £ 1.
Quand fkj = 1, la suite fkjn( ){ } est une suite de probabilités dite distribution de premier
passage pour ek.
En particulier f jjn( ){ } représente la distribution des temps de premier passage pour
l’état j, autrement dit la distribution de probabilités du temps de premier retour en j.
La probabilité pour que, partant de l'état i, on retourne toujours dans l'état i est
donnée par fii.
4-2 – Définition de la Périodicité d'un état
On dira d'un état x qu'il a la périodicité p x( )si et seulement s'il existe un entier
p x( ) > 1 où p x PGCD n pxxn( ) ( )= >{ }0 .
B.A. Ferrif
24/07/01
74
Dans le cas contraire l'état sera dit apériodique.
Un état x dans lequel aucun retour n'est possible (i.e pour lequel pxxn( ) = 0 pour
tout n>0) sera considéré comme apériodique.
Un état x tel que pxx >0 est de période 1. Il est apériodique, le système pouvant
rester en x indéfiniment
4-3- Remarque
La périodicité est un phénomène assez rare dans la pratique, et généralement
lorsque c’est le cas il apparaît de manière évidente.
4-4 –Périodicité et atteignabilité
Proposition
∑ Si l'état ei a la période p(i), alors il existe un entier e dépendant de i tel que,
pour tout entier n ≥ e, piin p i( . ( )) > 0. Autrement dit, un retour dans l'état i peut se
produire pour tout multiple suffisamment grand de la période.
∑ Si p jim( ) > 0 , alors p ji
m n p i( . ( ))+ > 0 pour tout n NΠsuffisamment grand.
4-5- Périodicité et irréductibilité
Proposition : Tous les états d'une chaîne irréductible ont la même période.
Si x,y,z,u sont des états de E et m,p,q des entiers naturels strictement positifs,on
a
p p p pxym p q
xzm
zup
uyq( ) ( ) ( ) ( )+ + ≥ .
� En effet le chemin X x X z X u X ym m p m p q0 = = = =+ + +, , , représente une
manière d’aller de x à y. Si les états x et y communiquent, il existe des entiers
B.A. Ferrif
24/07/01
75
naturels m et n tels que p pxyn
yxm( ) ( ),> >0 0 . Ainsi on a :
p p p p pxxm p q
xzm
zzp
zxq
zzm( ) ( ) ( ) ( ) ( ). . . ,+ + ≥ = >( )a a 0
Prenant p=0, il apparaît que m+q est nécessairement multiple de la période p(x)
de x , ce qui entraîne la nullité du terme de gauche pour tout p non multiple de
p(x); cela entraîne que la période p(y) de y est telle que p y p x( ) ≥ ( ) . Par symétrie
on conclut à l'égalité de p(y) et p(x).☺
4-6- Exercice
Etudier la périodicité des états de la chaîne définie dans l'exemple 1 :
4-7- Exercice
Etudier la périodicité des états de la chaîne définie par la matrice de transition :
0 1 0
0 0 1
1 0 0
Ê
Ë
ÁÁ
ˆ
¯
˜˜
B.A. Ferrif
24/07/01
76
4-8- Partition de l’espace des états en classes cycliques
Proposition : Si Xn n N( ) Œ est une chaîne de Markov irréductible de période d il
existe une partition de l'espace des états en d classes (les classes cycliques C0 ,
C1 ,…, Cd-1 ) telles que " Œ = = + £ <( )( )x C p sauf si n k d k dk xyn, .0 0a .
4-9- Exercice
Expliciter les classes périodiques de la chaîne (4-7).
5- Etat persistant et état transitoire.
5-1 - Définitions :
∑ L'état i est persistant ( ou récurrent) si et seulement si fii = 1.
∑ L'état i est transitoire si et seulement si fii < 1.
∑ Un état i persistant est dit nul si et seulement si mi = +•.
∑ Un état i persistant est dit positif si et seulement si mi < +• .
5-2- Equivalences des définitions
Théorème :
1-Les conditions suivantes sont équivalentes :
i) L’ état i est persistant,
ii) piin
n
( )
=
+•
 = +•1
,
iii) P X i i o X in = =( ) =. 0 1 i.o signifie infiniment souvent.
2-Les conditions suivantes sont équivalentes :
B.A. Ferrif
24/07/01
77
i) L’ état i est transitoire ,
ii) piin
n
( )
=
+•
 < +•1
,
iii) P X i i o X in = =( ) =. 0 0 i.o signifie infiniment souvent.
5-3- Remarques
a. Les états transitoires sont donc à rechercher parmi les états i qui
possèdent la propriété : Lim pn
iin
Æ +•=( ) 0 .
b. Si l'état i est transitoire alors " Œ < +•( )
=
+•
Âj E p jin
n
,1
.
c. L'état i est persistant nul si et seulement si " Œ = +•( )
=
+•
Âi E piin
n
,1
et
Lim pn
iin
Æ +•=( ) 0 . Alors " Œ =
Æ •
( )j E Lim pn
jin, 0 .
5-4- Exercices :
1-Montrer que les définitions (5-1) sont équivalentes à:
i) Un état i est persistant si P T i[ ] < +•( ) = 1 ;
ii) un état persistant sera dit persistant nul si E T i( )[ ] = +• et persistant positif
si E T i( )[ ] < +• ;
iii) un état non persistant est dit transitoire ; il s’agit donc d’un état i qui
satisfait à P T i[ ] = +•( ) > 0
2- Justifier les remarques (5-3).
B.A. Ferrif
24/07/01
78
5-5- Remarque
L'importance des théorèmes précédents réside principalement dans leurs aspects
sémantiques. Ils sont en effet assez malaisés à utiliser comme critères de
classification dans les applications. Nous donnerons ultérieurement quelques
critères d'utilisation plus aisés; malheureusement il n'en existe pas de simples et
universels.
5-6- Martingale
Une chaîne de Markov de matrice de transition pij i j N( )
Œ,est appelée une
martingale si et seulement si pour tout i l'espérance de la loi pij j N{ } Œ
est égale à i.
Autrement dit si et seulement si j p iijj N
. =Œ
 .
5-7- Exercice
Supposons donnée une chaîne de Markov finie dont l'ensemble des états est
0 1 2, , ,...,n{ } ; afin d'éviter des trivialités, nous supposerons que cette chaîne ne
possède pas plus de deux sous-ensembles persistants. Supposons que cette
chaîne est une martingale.
Etudier les états 0 et n .
Calculer Lim p et Lim pk
ik
kink
Æ +•
( )Æ +•
( )0 et interpréter ces limites.
B.A. Ferrif
24/07/01
79
5-8- Une caractéristique des états d'une même classe
Proposition : Soit Xn n N( ) Œ une chaîne de Markov homogène. Les états d'une
même classe sont tous
o ou persistants positifs,
o ou persistants nuls,
o ou transitoires.
5-9- Exercice :
Nature des états de la chaîne :
i
k
r p 0 e 0
0 r p e 0
0 0 r e p
0 0 0 1 0
0 0 0 0 1
y
{
5-10 – Durées et probabilités de séjour dans l’ensemble des états
transitoires
Notons :
∑ Ni X in
n= ={ }
=
+•
Â11
le nombre de fois où la chaîne se trouve dans l'état i durant son
évolution ;
∑ Nij le nombre de passages en j, partant de l’état i, avant absorption ;
∑ Fij la probabilité de passage en j, partant de l’état i, avant l’absorption ;
B.A. Ferrif
4/07/02
80
∑ Ti la durée du séjour dans l’ensemble des états transitoires en partant de l’état
i.
On a, bien évidemment : T Ni ijj
=Œ
Ât
où t désigne l’ensemble des états transitoires.
Un raisonnement élémentaire nous montre que si i est persistant la chaîne visite
l'état i une infinité de fois presque sûrement .
Posons
A={Le système passe au moins n fois par l'état j},
B={Le système atteint l'état j} , on a :
∑ g P A X iijn( ) = =( )0
∑ g P B X i Fij ij1
0( ) = =( ) =
On a :
∑ g F gij ij jj2 1( ) ( )= ¥
Pour que le système passe au moins deux fois par l’état j, il doit dans un premier
temps atteindre l’état j, puis ensuite repasser par ce dernier. Il s’ensuit par
récurrence :
∑ g F g F F
g F
ijn
ij jjn
ij jjn
iin
iin
( ) -( ) -
( )
= ¥ = ¥
=
1 1
On a :
P N n g g
P N n F F
ii iin
iin
ii ii iin
=( ) = -
=( ) = -( ) ¥
-( ) ( )
-
1
11
B.A. Ferrif
24/07/01
81
Il s’ensuit que Nii suit une loi de Pascal de paramètre 1-( )Fii .
5-10-1- Loi des Nij et nombre moyen de passages.
On a :
∑
P N m g g
P N m F F F
P N m F F F
ij ijm
ijm
ij ij jjm
jjm
ij ij jj jjm
=( ) = -
=( ) = ¥ -( )=( ) = ¥ -( ) ¥
( ) +( )
-
-
1
1
11
Il s’ensuit que :
∑ Le nombre moyen de retours en i en partant de i est E NFii
ii
( ) =-1
1 .
∑ Le nombre moyen de passages en j en partant de i est E NF
Fijij
jj
( ) =-1
.
En résumé on a :
Proposition : On a
∑ P N r X i f f f F F F si r et
P N r X i f F si r
j ij jjr
jj ij jjr
jj
j ij ij
= =( ) = -( ) = -( ) >
= =( ) = - = - =
- -0
1 1
0
1 1 0
1 1 0
. . ,
Théorème : L'espérance du nombre de passages par l'état j, conditionnée par Xo
= i, est égale à :
E N X i pj ijn
n0 1=( ) =
=
+•Â ( )
5-10-2- Calcul des Fij pour i j, Œt
Notons :
B.A. Ferrif
24/07/01
82
∑ t l’ensemble des états transitoires,
∑ c l’ensemble des états récurrents,
∑ T les probabilités de passage entre états transitoires de t ,
∑ C les probabilités de passage entre états récurrents de c ,
∑ R les probabilités de passage entre un état transitoire de t et un
état récurrent de c .
On peut décomposer la matrice P de la manière suivante :
PT R
C=
ÊËÁ
ˆ¯̃0
t ctc
T R
C0
On a :
F p P passage en j X kij ikk E
= ¥ =( )Œ
 0 , où
P passage en j X k
si k
si k j
F si k jkj
1
0
1=( ) =Œ=
π
Ï
ÌÔ
ÓÔ
c
Soit :
" Œ = +π ŒÂi j F p p Fij ij ik kj
k j k
, ,,
tt
; si parmi les n états de l’espace des états, m sont
récurrents, on a n m-( )2 équations à n m-( )2 inconnues. On en déduit :
∑
FI T
FI T
I T
jj
jj
ijij
jj
=-( )
=-( )-( )
-
-
-
11
1
1
5-10-3- Durée moyenne du séjour dans les états transitoires.
Nous avons :
B.A. Ferrif
24/07/01
83
T Ni ijj
=Œ
Ât
; il s’ensuit :
E T E N I T I T Ui ijj
ijj
i( ) = ( ) = -( ) = -( )Œ
-
Œ
-Â Ât t
1 1. où :
∑ U est la matrice colonne à n-m composantes égales à 1 et
∑ I T i-( )-1 est la i-ème ligne de la matrice I T-( )-1
Si E T( ) est le vecteur colonne E Ti i( ){ } Œt
alors E T I T U( ) = -( )-1. .
5-11- Matrice fondamentale :
Compte tenu du rôle tenu par la matrice I T-( ) elle porte souvent le nom de
matrice fondamentale de la chaîne de Markov.
5-12 - Problème :
Soit Xn n N( ) Œ une chaîne de Markov homogène irréductible dont l’espace des
états est fini ou dénombrable et de matrice de transition P pij i j E= ( )
Œ, .
On pose
∑ f P X j X j X j X iijn
n n( ) ( , ,.., )= = π π =-1 1 0 la probabilité d'être pour la première fois
en l'état j au temps n, étant parti de l'état i au temps 0,
∑ f fkj kjn
n
==
+•
 ( )
1
,
∑ g P Le système passe au moins n fois par j X iijn( ) = =( )0 .
1- Montrer que :
∑ " Œ " Œ =+( ) ( )
πÂi j E n N f p fij
nik kj
n
k j
, , , .* 1
∑ " Œ " Œ =+( ) ( )i j E n N g f gijn
ij ijn, , , .* 1
B.A. Ferrif
24/07/01
84
2- Montrer que la chaîne Xn n N( ) Œ est récurrente si et seulement si Lim g
niin
Æ •
( ) = 1.
Que peut-on en déduire si l’espace des états est fini ?
3- Supposons i jπ , posons a ij n kP n N X j X i k n X i= $ Œ = π £ £ =( )* , , ,1 0 ; montrer
que f fii ij ji£ - -( )1 1a . En déduire la valeur de f ji lorsque la chaîne est
récurrente.
4- Posons mij ijn
n
n f= ( )
=
•
 .1
, mij représente le temps moyen de premier passage en j
sachant qu’à l’instant 0 le système était en i ; montrer que si la chaîne Xn n N( ) Œ est
récurrente, alors " Œ = +π
Âi j E pij ik kjk j
, , .m m 1.
Que peut-on dire de mij si fij < 1 ?
6-Ergodicité
Nous avons précisé, au paragraphe 2, la notion de transition d’ordre supérieur
pour une chaîne de Markov Xn n N( ) Œ et mis en évidence que la probabilité
d’atteindre l’état x à partir de l’état y en n étapes était donné par la matrice
P pnxyn= ( )( ) puissance nème de la matrice de transition P.
6-1- Définition :
Nous dirons qu’une chaîne de Markov est ergodique si et seulement si la
limite " ŒÆ •
x y E Lim pn
xyn, , ( ) existe et est indépendante de l’état initial x . Comme cette
limite ne dépend que de l’état final y , nous la noterons Lim pn
xyn
yÆ •=( ) p .
B.A. Ferrif
24/07/01
85
Ainsi une chaîne de Markov ergodique atteint après un grand nombre d’étapes
une situation d’équilibre statistique au sens suivant :
nous avons vu que la loi marginale PX n est définie pour tout y EŒ par
p P X y P y p pyn
n X x xyn
x En
( ) ( )( ) ( ) .= = = =Œ
 ;
il s’ensuit alors que
Lim p Lim P X y Lim P y Lim p p Lim p p Lim pn
yn
nn
nX
nx xy
n
x En
xyn
xx E
nxyn
ynÆ • Æ • Æ • Æ • Œ Æ • Œ Æ •= = = = = = = Â( ) ( ) ( ) ( )( ) ( ) . . p
car pxx E
=Œ
 1.
Un problème important de la théorie des chaînes de Markov est donc de
déterminer sous quelles conditions une chaîne de Markov est ergodique.
Nous reviendrons plus généralement sur la question des limites et sur les critères
d’ergodicité au paragraphe 8.
6-2- Remarques
∑ Lorsque " Œ = >Æ •
y E Lim pn
xyn
y, ( ) p 0 on précise parfois que la chaîne de Markov
est fortement ergodique.
∑ Lorsque " Œ = =Æ •
y E Lim pn
xyn
y, ( ) p 0 on précise parfois que la chaîne de Markov
est faiblement ergodique.
6-3- Théorème et définition
Un état y apériodique, persistant, est ergodique si et seulement si my < +• . Alors
" Œ =Æ •
-y E Lim p fn
xyn
xy y, ( ) m 1.
B.A. Ferrif
24/07/01
86
6-4- Remarque
Il résulte de ce qui précède que si l'état y est apériodique alors soit
Lim p fn
xyn
xy yÆ •
-=( ) m 1 soit Lim pn
xyn
Æ •=( ) 0.
7- Chaîne irréductible, décomposition des chaînes.
7-1 – Partie irréductible fermée
Théorème : Si i est un état persistant, il existe une unique partie irréductible
fermée C contenant i et telle que pour tout couple (j,k) d'états dans C, on ait
f fik kj= =1 1, .
Autrement dit partant d'un état arbitraire i dans C, le système est certain de
passer par tous les autres états de C; par définition de la fermeture, aucune sortie
de C n'est réalisable.
7-2 – Décomposition d'une chaîne de Markov
Théorème : L'espace des états d'une chaîne de Markov se décompose en une
partition d'ensembles T, C1 , C2 ,… tels que :
∑ T est l'ensemble de tous les états transitoires.
∑ Si j est dans Cn alors fjk = 1 pour tout k dans Cn et fjk = 0 pour tout k extérieur
à Cn.
B.A. Ferrif
24/07/01
87
7-3- Probabilité d'absorption par une classe récurrente
Considérons une chaîne de Markov Xi( ) dont l'espace des états E a pour cardinal
n. Supposons que cette chaîne possède un ensemble d'états transitoires T de
cardinal n-m, où m désigne le cardinal de l'ensemble C des états récurrents.
Supposons enfin que cette chaîne possède r classes récurrentes C1 , C2 , ... , Cr
(dont la réunion est C).
Nous allons déterminer l'ensemble bip{ } des probabilités d'absorption du
processus par la classe récurrente Cp pour p rŒ{ }1,..., et i TŒ .
On a :
bip ij pj E
p P Absorption par C X j= =( )Œ
 . 1 avec
∑ P Absorption par C X j si j C Cp p1 0=( ) = Œ -
∑ P Absorption par C X j si j Cp p1 1=( ) = Œ
∑ b jp si j TŒ
Il s'ensuit :
b bip ij ijj Tj C
jpp pp
= +ŒŒ
ÂÂ . ,
d'où l'on déduit l'équation vectorielle
B.A. Ferrif
24/07/01
88
p
p
p
I T
jj C
jj C
n m jj C
p
p
n m p
p
p
p
1
2
1
2
Œ
Œ
-Œ
-
Â
Â
Â
Ê
Ë
ÁÁÁÁÁÁÁÁ
ˆ
¯
˜˜˜˜˜˜˜˜
= -( )
Ê
Ë
ÁÁÁÁ
ˆ
¯
˜˜˜˜...
....
( )
( )
bb
b
(en numérotant les éléments de T de 1 à (n-m) )
et la solution
bb
b
1
2 1
1
2
p
p
n m p
jj C
jj C
n m jj C
I T
p
p
p
p
p
p
....
...( )
( )
-
-
Œ
Œ
-Œ
Ê
Ë
ÁÁÁÁ
ˆ
¯
˜˜˜˜
= -( )
Ê
Ë
ÁÁÁÁÁÁÁÁ
ˆ
¯
˜˜˜˜˜˜˜˜
Â
Â
Â
Remarque : Une démonstration rigoureuse se déduit du théorème de
Gerschgörin.
7-4 – Caractérisation de la nature des états (1)
Théorème : Dans une chaîne finie il n'existe pas d'état nul et il n'est pas possible
que tous les états soient transitoires.
Autrement dit :
7-5 - Caractérisation de la nature des états (2)
Théorème : Avec une probabilité égale à 1, un état transitoire ne peut être visité
qu'un nombre fini de fois. Il s'ensuit que dans une chaîne de Markov à nombre fini
d'états, tous les états ne peuvent pas être transitoires; au moins l'un d'eux est
persistant.
B.A. Ferrif
24/07/01
89
7-6 - Caractérisation de la nature des états (3)
Théorème : Si une chaîne de Markov est absorbante, tout état non absorbant est
un état transitoire.
7-7- Caractérisation de la nature des états (4)
Théorème : Une chaîne de Markov homogène irréductible Xn n N( ) Œ est transitoire
si et seulement si pour un état quelconque k le système linéaire :
x p x i k et j ki ij jj
= π π . , ,
0 1£ £ πx i ki ,
admet une solution non identiquement nulle.
Résultat équivalent à :
7-8- Caractérisation de la nature des états (5)
Théorème : Une chaîne de Markov homogène irréductible Xn n N( ) Œest persistante
si et seulement si pour un état quelconque k le système linéaire :
x p x i k et j ki ij jj
= π π . , ,
0 1£ £ πx i ki , ,
n'admet aucune solution autre que xi = 0 pour tout i.
7-9- Exercice
Caractériser les états de la chaîne de Markov définie par la matrice de transition :
B.A. Ferrif
4/07/02
90
M =
Ê
Ë
ÁÁÁÁÁ
ˆ
¯
˜˜˜˜˜
012
12
12
012
12
12
0
7-10-Test
Caractériser les états de la chaîne de Markov définie par la matrice de transition :
P =
i
k
0 0.7 0 0 0 0 0 0 0.3 0
0.8 0 0.2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0.4 0 0.05 .0 0.25 0.05 0.25
0 0 0 0 0 0.2 0.8 0 0 0
0 0 0 0 0.1 0.2 0.7 0 0 0
0 0 0 0 0.7 0.3 0 0 0 0
0 0 0 0.35 0 0.15 0.1 0 0 0.4
1 0 0 0 0 0 0 0 0 0
0 0 0 0.5 0 0 0.05 0.05 0 0.4
y
{
Réécrire cette matrice sous la forme :
T R
C0
ÊËÁ
ˆ¯̃
.
8- Distributions stationnaires et lois limites.
8-1- Distribution stationnaire.
Une chaîne de Markov homogène d'espace d'états fini ou non est dite posséder une
distribution stationnaire p p p p= ( )0 1, ,.., ,...n (où " Œ ≥ =Âi N eti nn
,p p0 1) si et
seulement si p satisfait l'équation p p= .P .
Autrement dit : la loi de Xn est invariante dans le temps.
B.A. Ferrif
24/07/01
91
8-2- Lois limites
Une chaîne de Markov homogène est dite posséder une loi limite
p p p p= ( )0 1, ,.., ,...n si et seulement si Lim Lim P X jn jn
n n jÆ +• Æ +•= = =p p( ) ( ) pour j=
0, 1, 2, ... .
8-3- Lois limites et lois stationnaires des chaînes de Markov homogènes
irréductibles et apériodiques.
Théorème :
1. Soit Xn n N( ) Œ une chaîne de Markov homogène irréductible apériodique,
La loi limite ( ( ) )( )Lim Lim P X jn jn
n n j j NÆ +• Æ +• Œ= = =p p existe toujours et est
indépendante de la loi initiale.
2. Si tous les états ne sont pas persistants positifs (donc sont soit transitoires,
soit persistants nuls) alors p j = 0 pour tout j et aucune distribution stationnaire
n'existe.
3. Si tous les états de Xn n N( ) Œ sont persistants positifs alors p j > 0 pour tout j et
p p p p= ( )0 1, ,.., ,...n forme une distribution stationnaire avec p mj j= 1 .
Auquel cas la limite est l'unique solution de l'équation :
p ii N
=Œ
 1
p pj i iji N
p=Œ
 . j = 0, 1, 2, ..
8-4- Loi stationnaire pour une chaîne arbitraire
Le critère suivant s'applique à une chaîne arbitraire :
B.A. Ferrif
24/07/01
92
Théorème : Si une chaîne de Markov possède une loi stationnaire
p p p p= ( )0 1, ,.., ,...n alors p n = 0 pour tout n correspondant à un état transitoire ou à
un état persistant nul.
Autrement dit p n > 0entraîne que l'état n correspondant est persistant et a un
temps de récurrence fini (en revanche l'état n peut être périodique).
� Dire que p p p p= ( )0 1, ,.., ,...n est une loi stationnaire entraîne que p pn i ink
i N
p= ( )
ŒÂ . .
Si l'état n est transitoire ou persistant nul, on a pour tout i Lim pk
ink
Æ •
( ) = 0 ce qui
entraîne p n = 0 .
☺
8-5- Remarques :
∑ Dans le cas (3) d'une chaîne de Markov fortement ergodique, la loi
stationnaire et la loi limite coïncident. De telles distributions sont dites
distributions d'équilibres.
∑ Ces distributions sont fondamentales pour traiter des files d'attente. Cela
indique aussi pourquoi il est important de posséder des critères permettant de
savoir si une chaîne de Markov est ou non ergodique.
∑ Il importe de noter qu'une distribution limite est aussi une distribution
stationnaire mais que l'inverse n'est pas exact.
Le théorème suivant montre que le comportement d'une chaîne de Markov dont le
nombre d'états est fini est plus simple que celle dont le nombre d'états est infini:
B.A. Ferrif
24/07/01
93
8-6- Ergodicité des chaînes à espace d’états fini
Théorème : Une chaîne de Markov Xn n N( ) Œ dont le nombre d'états est fini et qui
est irréductible et apériodique est (fortement) ergodique.
� En effet, d’après (7-3) la chaîne est persistente et d’après (8-3-3) elle est
fortement ergodique. ☺
8-7- Exercice :
Loi stationnaire et loi limite de la chaîne de Markov :
012
12
12
012
12
12
0
Ê
Ë
ÁÁÁÁÁ
ˆ
¯
˜˜˜˜˜
8-8- Test
Le siège d'une entreprise est assimilable à un polygone ayant Ns sommets. À
chaque sommet est situé un accès au bâtiment. Une partie de la sécurité du
bâtiment est assurée par un vigile. Il est décidé qu'il se déplacera d’un accès à
l'autre de telle sorte que, s'il quitte un sommet, il y a une probabilité p qu’il décide
d’aller au sommet adjacent dans le sens des aiguilles d’une montre et une
probabilité (1-p) qu'il aille à l’autre sommet adjacent.
1 –Analyser la situation lorsque Ns = 5 et Ns = 6.
B.A. Ferrif
24/07/01
94
1
2
3
4
5
1
23
4
5
6
2 – On se place dans le cas du pentagone, Ns = 5. Imaginons pour fixer les idées
que le vigile commence sa surveillance à l'accès n°1, que p=1/3, que le vigile
met 1’30’’ pour passer d’un accès à un autre et demeure 30’’ à chaque accès. On
souhaite connaître l'accès le plus vulnérable au sens suivant : celui pour lequel le
temps moyen de premier passage est le plus élevé.
9- Extension:
9-1- Matrices de transition d'une chaîne de Markov non-homogène.
Lorsque la chaîne de Markov n'est pas homogène, la probabilité de transition de
l'état x à l'état y dépend de l'indice n. On a donc une famille de matrices de
transition satisfaisant à :
∑ " Œ " Œ = = =( ) >+n N x y E p n P X y X xxy n n, , , ( ) 1 0 ,
∑ " Œ " Œ =Œ
Ân N x E p nxyy E
, , ( ) 1 .
9-2-Processus de Markov d'ordre supérieur.
La définition des processus de Markov d’ordre 1 s'avère parfois insuffisante. Il est
en effet des situations dans lesquelles l'état futur ne dépend pas seulement de
B.A. Ferrif
24/07/01
95
l'état présent mais également de l'état antérieur à l'état présent; la définition
précédente est alors modifiée en:
9-2-1-Définition:
Un processus aléatoire est un processus de Markov d'ordre 2 s'il vérifie l'axiome
suivant, que nous appellerons propriété de Markov à l'ordre 2 :
"( ) Œ < < < < "( ) Œ-+
- -+t t t t I t t t t x x x x En n
nn n n n
n0 1 1
10 1 1 0 1 1
1, ,..., , , ... , , ,..., , ,
P X x X x X xt t t t t tn n( ,..., , )
- -= = = >
1 1 1 1 0 00 ,
P X x X x X x X x P X x X x X xt t t t t t t t t t t t t tn n n n n n n n n n n n( , ,..., ) ( , )= = = = = = = =
- - - - - - - -1 1 2 2 0 0 1 1 2 2.
Autrement dit :
La propriété de Markov exprime que l'état futur Xtn dépend seulement de l’état
passé immédiatement antérieur à l’état présent Xtn-2 et de l’état présent Xtn-1
.
Plus généralement :
9-2-2-Processus de Markov d’ordre a i
Un processus aléatoire ( )Xt t IŒ est un processus de Markov d’ordre a i s'il vérifie
l'axiome suivant, fréquemment appellé propriété de Markov :
"( ) Œ < < < < "( ) Œ " Œ{ }-+
- -+t t t t I t t t t x x x x E nn n
nn n n n
ni0 1 1
10 1 1 0 1 1
1 1, ,..., , , ... , , ,..., , , ,..,a ,
P X x X x X xt t t t t tn n( ,..., , )
- -= = = >
1 1 1 1 0 00 ,
P X x X x X x X xt t t t t t t tn n n n n n( , ,..., )= = = =
- - - -1 1 2 2 0 0=
P X x X x X x X xt t t t t t t tn n n n n n n i n i( , ,.., )= = = =
- - - - - -1 1 2 2 a a.
Autrement dit :
B.A. Ferrif
24/07/01
96
La propriété de Markov exprime que l'état futur Xtn ne dépend pas de l’ensemble
des états passés X i nti, , , ,.., ,Œ -{ }0 1 2 2 mais seulement des l'états
X X Xt t tn n n i- - -1 2, ,..,
a.
Cette propriété précise le niveau de mémoire du processus.
9-3-Modèles de Markov cachés.
La notion de chaîne de Markov d’ordre a i nous a permis de préciser plus avant le
niveau de mémoire. Cette généralisation ouvre la possibilité de présenter un
concept émergent dans un grand nombre d’applications (informatique, traitement
du signal, reconnaissance des formes, ingénierie de la connaissance…) : les
Modèles de Markov Cachés (HMM pour : Hidden Markov Models). L’ingénierie
linguistique, qui vise une mise en œuvre de l’ensemble des techniques
permettant une compréhension plus ou moins large du langage naturel par une
machine, en fait un usage particulier ainsi que nous le constaterons. Ce domaine
(l’ingénierie linguistique) fait partie, soulignons-le, des domaines répertoriés dans
les technologies clefs du développement industriel avec une progression
prévisible du marché importante et une intensité de la concurrence faible.
Insuffisance du modèle markovien.
Imaginons un espace réel qui nous est caché (par exemple le temps qu’il fait
dehors alors que nous sommes enfermés dans une pièce aveugle ; réduisons
pour fixer les idées le temps à 3 états : pluvieux, nuageux, ensoleillé) ; supposons
en revanche que nous disposons d’un baromètre : une grenouille qui occupe sur
B.A. Ferrif
24/07/01
97
son échelle la position basse si le temps et ensoleillé (avec une certaine
probabilité), la position haute s’il est pluvieux (avec une certaine probabilité) et
intermédiaire s’il est incertain (avec une certaine probabilité). Nous souhaitons
pouvoir prédire le temps sans le voir directement, éventuellement enregistrer une
séquence de prévision et en induire si l’on est en été ou en hiver.
Nous sommes donc en présence de deux ensembles d’états : l’ensemble des
états observables (celui des positions de la grenouille) et l’ensemble des états
cachés (les états du temps). Par ailleurs nous savons que l’évolution du temps
obéit à un modèle markovien. La prévision du temps qu’il fait serait grandement
améliorée si nous pouvions combiner l’observation du temps qu’il faisait
réellement hier avec la position de la grenouille.
La description d’un modèle markovien caché se fait donc à l’aide d’un modèle
markovien sur l’espace des états cachés, d’un ensemble d’états observables et
d’une distribution de probabilité conditionnelle qui lie la réalité du temps à la
nature de l’observation.
Plus formellement (nous nous limiterons aux modèles d’espaces d’états finis), se
donner un modèle de Markov caché s’est se donner :
∑ l’ensemble E des états « cachés » ;
∑ l’ensemble M des états « observables » de cardinal m (éventuellement
différent du cardinal n de E) ;
∑ la matrice de transition P pij i j n= ( )
£ £1 ,sur E, avec
" ( ) Π= = =+i j E p P X j X iij n n, , ( )21 ;
∑ la matrice B bkj k m j n= ( )
£ £ £ £1 1, telle que " Œ " Œ = = =j E k M b P O o X ikj n k n, , ( ) où
ok désigne le symbole qui représente le résultat de l’observation ;
B.A. Ferrif
24/07/01
98
∑ la loi initiale PX 0 de X0 sur E.
Se donner un modèle de Markov caché c’est donc plus brièvement se donner un
triplet P p B b Pij i j n kj k m j n X= ( ) = ( )ÊË
ˆ¯£ £ £ £ £ £1 1 1 0, ,
, , .
B.A. Ferrif
24/07/01
99
APPENDICE A :
Formule de Bayes
A-1-Formule de Bayes : rappel et compléments.
� Si E F P, ,( ) est un espace probabilisé et A un événement tel que P(A) > 0,
alors l'application de F à valeurs dans R définie par
" Œ Æ«
, (- ) : ( ) = ( )
( ) B F P A B P B A
P A B
P A
définit sur F une loi de probabilité qui s'appelle la probabilité de B sachant A .
� Si E F P, ,( ) est un espace probabilisé, si A1, A2, ... , An est une famille
d'évènements de E telle que : A Ai j« = ∆ si i jπ et P Aii
n
=
ÊËÁ
ˆ¯̃
=1
1U , alors
pour tout évènement B FŒ on a : P B P B Aii
n
( ) = «( )=
Â1
.
Cette dernière relation porte souvent le nom de "principe des probabilités totales".
� Si E F P, ,( ) est un espace probabilisé et si A1, A2, ... , An est une famille
d'évènements de E telle que : A Ai j« = ∆ si i jπ et P Aii
n
=
ÊËÁ
ˆ¯̃
=1
1U , alors
B.A. Ferrif
24/07/01
100
pour tout évènement B FŒ on a : P A BP B A P A
P B A P Ai
i i
j jj
n( ) =¥ ( )
( ) ¥ ( )=
Â( )
1
pour i = 1 , 2 , ...
,n .
� Si E F P, ,( ) est un espace probabilisé et si A1, A2, ... , An est une famille
d'évènements de E, on a :
P A A A P A P A A P A A A P A A An n n( .. ) = ( ) ( ) ( ) .. ( .... )-1 2 1 2 1 3 1 2 1 1« « « ¥ ¥ « ¥ ¥ « «à condition que le second membre ait un sens (une condition suffisante est que le
premier membre soit strictement positif).
� Comme les événements A et B sont parfaitement définis par leurs fonctions
indicatrices, on a :
P B A PP
PB AA B
A
( ) = ({ = } { = }) = ({ } { = })
({ = })
=1 1 1 1
1 1 1 11 1
«
= P
PA B
A
( ( , ) = ( , ) )
({ = })
1 1 11
1 1{ }
� Si X est une variable aléatoire définie sur l'espace probabilisé E F P, ,( ) à
valeurs dans l'espace probabilisable E F1 1,( ) et de loi PX , alors
pour toute variable aléatoire Y E Rn: Æ , on appelle loi conditionnelle de Y en X la
famille des lois de probabilité sur Rn indexées par les valeurs x de X (de
probabilité > 0) et définies par :
P B P Y B X xP Y B X x
P X x
P Y B X x
P X xYX x= ( ) := ( = ) =
( , = )( = )
=( = )
( = ) Œ
Œ{ }{ }
Œ{ } « { }{ } .
� Si Xi i n( ) =1,.., est une famille de variables aléatoires discrètes définie sur l'espace
probabilisé E F P, ,( ) on a, bien entendu :
B.A. Ferrif
24/07/01
101
P X X X P X P X X P X X X P X X Xn n n( .. ) = ( ) ( ) ( ) .. ( .... )-1 2 1 2 1 3 1 2 1 1, , , ,, ,¥ ¥ ¥ ¥ .
� Par substitution, on déduit le résultat utile suivant : si Xi i n( ) =1,.., est une famille
de variables aléatoires discrètes et si U est une variable aléatoire discrète
définies sur l'espace probabilisé E F P, ,( ) on a:
P X X X U P X U P X X U P X X X U P X X X Un n n( .. ) = ( ) ( , ) ( , ) .. ( .... , )-1 2 1 2 1 3 1 2 1 1, , , ,, ,¥ ¥ ¥ ¥
A-2 Formule de Bayes généralisée.
Nous avons vu précédemment que si l’on prend des variables aléatoires discrètes
on a : P Y XP Y X
P X( ) =
,( )
( )
.
De manière analogue on a pour quatre variables aléatoires discrètes :
P W Y X ZP W Y X Z
P X Z
P W Y P X Z W Y
P X Z, , =
, , ,
( , )=
, , ,
( , )( ) ( )( ) ( ) ( )( )
( )( )( ) ( ) ( )( )
( ) .
B.A. Ferrif
24/07/01
102
Appendice B :
Graphes
Cet appendice regroupe quelques résultats de théorie des graphes auxquels il est
fait référence dans le cours de systèmes stochastiques.
B-1-Définitions
Définition des graphes : Un graphe G est un couple (E,V) où E est l’ensemble
des sommets et V l’ensemble des arcs , l’ensemble des arcs étant un sous-
ensemble de l’ensemble ExE.
figure 1
Si (x,y) est un arc de V , x est le prédécesseur de y et y le successeur de x.
B.A. Ferrif
24/07/01
103
Soit G=(E,R) un graphe où E est l’espace des sommets (dans ce cours l’espace
des états) et R l’ensemble des arcs (dans ce cours les transitions).
∑ Un arc du sommet x vers le sommet y est souvent noté (x,y).
(m,l) , (m,k) , (m,m) , (k,l) , (k,j) , (i,j) , (i,m) , (j,k) sont les arcs de la
figure 1 .
∑ Un arc (x,x) s’appelle une boucle.
(m,m) est une boucle dans l’exemple de la figure 1
∑ Deux sommets reliés par un arc sont dits adjacents.
Les sommets adjacents de l’exemple 1 sont décrits ci-dessus.
∑ Deux arcs sont dits adjacents s’ils ont une extrémité commune.
Sur la figure 1 les arcs (j,k) et (k,l) sont adjacents, il en est de même
des arcs (m,m) et (m,l) etc….
∑ Un arc qui a son extrémité terminale (resp. initiale) en un sommet est dit
incident vers l’intérieur (resp. vers l’extérieur) à ce sommet.
L’arc (k,j) est incident vers l’intérieur à j, l’arc (k,j) est incident vers
l’extérieur à k.
∑ On appelle demi-degré intérieur et l’on note d-(x) le nombre d’arcs incidents
vers l’intérieur à x. On appelle demi-degré extérieur et l’on note d+(x) le
nombre d’arcs incidents vers l’extérieur à x.
Exemple : d+(I)=2, d-(I)=0, d+(m)=3, d-(m)=2, d+(j)=1, d-(j)=2,..
B.A. Ferrif
24/07/01
104
Définition d’une arborescence : Une arborescence de racine r est un graphe
G(E,V) tel que r est un élément de E et que, pour tout sommet x de E, il existe un
chemin unique de r vers x.
figure 2
Une arborescence est donc sans cycle et le demi-degré intérieur de chaque
nœud est égal à 1 sauf pour la racine. Les sommets de demi-degré extérieur nul
sont appelés les feuilles de l’arborescence.
Dans l’exemple de la figure 2 les feuilles sont f1 ,f2 ,f3 .
En informatique les arborescences se prêtent bien à une définition récursive.
Un graphe est dit simple si et seulement si :
1- Il n’a pas de boucle ;
2- Il y a au plus un arc entre deux sommets.
B.A. Ferrif
24/07/01
105
figure 3
Un graphe est toujours orienté. On est parfois amené à ignorer cette orientation si
le problème posé est de nature non orientée. Un arc s’appelle alors une arête,
notée [x,y], et l’on a [x,y]=[y,x].
On désigne parfois sous le nom de multigraphe un graphe G sans son orientation.
Inversement, à partir d’un multigraphe G, on construit un graphe orienté en
orientant chaque arête dans les 2 sens.
Exemple de multigraphe : (multigraphe associé au graphe simple de la figure 3)
figure 4
B.A. Ferrif
24/07/01
106
Un graphe est dit complet si et seulement si l’on a :
x y E y x E, ,( ) œ fi ( ) Œ
U n chemin c v v vn= ( )1 2, ,... est une suite d’arcs telle que pour chaque arc
v x xi i i= ( )+, 1 ( i n< ) de la suite l’extrémité terminale x de vi i+1 coïncide avec
l’extrémité initiale de vi+1 .
Autrement dit, un chemin de x à y est une suite de sommets x x xn1 2, ,...( ) telle que
x x x y et i N x x Vn p i0 1 1 1= = " Œ ( ) Œ- +, , . On dit alors parfois que y est descendant
d’ordre n de x.
Si l’on fait abstraction de l’orientation, le chemin s’appelle une chaîne. Une chaîne
est donc une séquence d’arêtes pouvant être parcourues de manière que
l’extrémité terminale de l’arête que l’on quitte soit l’extrémité initiale de l’arête que
l’on va parcourir.
Un chemin est dit élémentaire s’il ne rencontre pas deux fois le même sommet.
Lemme : Etant donnés deux sommets x et y de G, s’il existe un chemin de x à y
dans G alors il existe un chemin élémentaire de x à y (ce chemin sera de
longueur inférieure ou égale au cardinal de l’ensemble des sommets).
Un chemin est dit simple s’il n’utilise pas deux fois le même arc.
Un circuit (resp. un cycle) est un chemin (resp. une chaîne) qui se referme sur lui-
même (resp. sur elle-même)
B.A. Ferrif
24/07/01
107
La longueur d’un chemin (resp. d’une chaîne) est égale au nombre d’arcs (resp.
d’arêtes) qui le constituent.
La suite de sommets (1,2,4,1,5,3,6,2,4) est un chemin de longueur 8 reliant 1 à 4
.
La suite de sommets (1,2,4) est un chemin élémentaire de longueur 2 reliant 1 à
4.
La suite de sommets (1,2,4,1) est un chemin circuit de longueur 3.
Un chemin qui passe une seule fois par tous les sommets d’un graphe est appelé
chemin hamiltonien.
B-2-Connexité
B-2-1-Graphe connexe.
Un graphe connexe est un graphe tel que pour toute paire x, y de sommets
distincts, il existe un chemin qui les relie.
B.A. Ferrif
24/07/01
108
B-2-2-Composante connexe d’un graphe
Soient x et y deux sommets d’un graphe. La relation « x y ou x y= π et il existe
un chemin reliant x et y » est une relation d’équivalence. Les classes
d’équivalence forment une partition de E et sont appelées composantes connexes
de G.
B-2-3-Graphe fortement connexe
Soit G=(E,V) un graphe connexe et soit R la relation sur E définie par :
R(x,y) si et seulement si il existe un chemin de x vers y et un chemin de y vers x ;
un chemin de longueur 0 est un chemin réduit à x.
Cette relation d équivalence induit une partition de l’ensemble E dont les
éléments sont les composantes fortement connexes de G.
Un graphe est fortement connexe si et seulement s’il n’admet qu’une composante
connexe.
Autrement dit si et seulement si pour tout couple de sommets x et y il existe un
chemin de x vers y et un chemin de y vers x.
B-3-Matrice d’adjacence associée à un graphe
Etant donné un graphe G = (E,V) , on associe à G une matrice, appelée matrice
d’adjacence, de type (Card(E),Card(E)), telle que tout élément situé à
l’intersection de la ligne a Œ E et de la colonne b Œ E est égal à 1 si a b,( ) ŒV et
à 0 sinon.
B.A. Ferrif
24/07/01
109
La matrice d’adjacence M associée au graphe précédent est donc
M =
Ê
Ë
ÁÁÁÁÁÁÁ
ˆ
¯
˜˜˜˜˜˜˜
0 1 0 0 1 0
0 0 1 0 0 0
0 1 0 1 0 0
0 0 0 0 0 0
0 0 1 1 1 0
0 0 0 0 0 0
avec
i j k l m n
i
j
k
l
m
n
0 1 0 0 1 0
0 0 1 0 0 0
0 1 0 1 0 0
0 0 0 0 0 0
0 0 1 1 1 0
0 0 0 0 0 0
Le carré, le cube ,… la puissance d’ordre n de la matrice d’adjacence calculés
avec les règles habituelles donnent le nombre de chemins quelconques de
longueur 2, 3,…,n existant entre les éléments de tout couple de sommets du
graphe.
Ce qui est clair sur la définition du produit matriciel. En effet le terme situé à
l’intersection de la i-ème ligne et à de la j-ème colonne s’écrit a aik kjk
n
.=
Â1
; il s’ensuit
que si l’un des produits a aih hj. est égal à 0, on a a ou aih hj= =0 0 , autrement dit il
n’existe pas d’arc i h,( ) ou d’arc h j,( ) ; si le produit a aih hj. est différent de 0, on a
a et aih hj= =1 1 , autrement dit il existe un d’arc i h,( ) et un arc h j,( ). La somme
a aik kjk
n
.=
Â1
donne donc le nombre de chemins de longueur 2 entre i et j.
B.A. Ferrif
24/07/01
110
B-4-Fermeture transitive d’un sommet du graphe.
Désignons par F(x) l’ensemble des sommets du graphe G liés à x par un arc
d’origine x :
F(i)={j,m} , F(j)={k} , F(k)={j,i}, F(m)={m,i,k} , F(l)={ }= = ∆ , F(n)={ } = ∆ .
On appelle fermeture transitive du sommet x d’un graphe G l’ensemble :
F x x F x F x
où F x F F x
n
n n
( ) = { } » » » »
= ( )-
( ) ... ( ) ....
( ) ( )1
Autrement dit la fermeture transitive de x représente l’ensemble des sommets
reliés à x par un chemin (on dit parfois que ce sont les sommets descendants de
x).
Calcul de la fermeture transitive
A la fermeture transitive d’un graphe correspond la matrice :
M G I M M M n( ) = + + + + +1 2 ... ... (Addition booléenne)
Rappel du théorème du binôme : I M I M M Mk k+( ) = + + + +1 2 ... (Opérations
booléennes).
B.A. Ferrif
24/07/01
111
Il est clair qu’il n’est pas utile de considérer les puissances de M supérieures à n-
1 (n étant le nombre de sommets du graphe). En pratique on peut s’arrêter dès
que M Mp p+ =1 .
Si r est le nombre des sommets du graphe, c’est-à-dire le nombre d’évènements
de l’espace des états, et si r est fini, le chemin élémentaire de longueur maximale
dans le graphe comprend au plus r-1 arcs. On obtient la fermeture transitive en
calculant I Mr+( ) -( )1 où M est la matrice d’adjacence du graphe et I la matrice
identité. [La matrice M est une matrice booléenne]. Les opérations sur les
constituants de M et de I+M s’obtiennent en utilisant comme lois de composition
le produit et la somme logique.
Table du produit logique :
. 0 1
0 0 0
1 0 1
Table de la somme logique :
+ 0 1
0 0 1
1 1 1
Ainsi il suffit de calculer I Mp
+( )( )2 jusqu’à ce que I M I Mp p
+( ) = +( )+( ) ( )2 2 1
pour
obtenir la fermeture transitive du graphe .
La présence d’un 1 à la i-ème ligne et à la j-ème colonne de M p signifie qu’il
existe au moins un chemin de longueur p entre les sommets i et j.
B-5-Valeurs propres des matrices stochastiques
B-5-1-Valeurs propres et classes récurrentes
L’ordre de multiplicité de la valeur propre 1 de la matrice M est égal au nombre de
classes récurrentes pour une matrice stochastique finie.
B.A. Ferrif
24/07/01
112
B-5-2-Valeurs propres et classes périodiques
Si M est la matrice de transition d’une chaîne de Markov finie irréductible et
périodique de période d, alors les racines d-ièmes de l’unité sont des valeurs
propres de M, chacune de multiplicité 1 et il n’existe pas d’autre valeur propre de
module 1.
Si M est la matrice de transition d’une chaîne de Markov finie, toute valeur propre
de M de module 1 est racine de l’unité. Les racines d-ièmes de l’unité sont des
valeurs propres de M si et seulement si M contient une classe récurrente de
période d. La multiplicité de chaque d-ème racine de l’unité est exactement le
nombre de classes récurrentes de période d.
Remarque : La classification des états à l’aide des propriétés des graphes n’est
strictement équivalente à la classification probabiliste que dans le cas des
chaînes de Markov à espace d’états fini.
B.A. Ferrif
24/07/01
113
Problèmes de synthèse
Thème d'étude 1 : Etude du cursus d’un élève dans une
grande école
Ce thème d'étude servira de fil rouge tout au long de ce chapitre. Nous
résoudrons les questions qui se pose
Dans certaines grandes écoles les études durent trois ans ; à l’issue de chaque
année, chaque élève a une certaine probabilité de passer dans l’année
supérieure (ou d’obtenir le diplôme s’il est en troisième année); une certaine
probabilité de redoubler, et une certaine probabilité d’être renvoyé. Pour certains
établissements, disons les établissements de type A, le nombre de
redoublements n'est pas limité; pour d'autres, appelons-les de type B, il n'est pas
possible d'une part de faire les deux premières années en plus de 3 ans (un élève
en échec qui a déjà accompli deux années est exclu) et d'autre part de faire la
troisième année 3 fois (un élève en échec qui a déjà accompli deux troisièmes
années est exclu).
Nous traiterons dans un premier temps le cas des établissements de type A, les
établissements de type B pourrons faire l'objet d'une étude de synthèse à la fin du
chapitre 3.
1.Quel est le modèle du cursus d’un élève dans un établissement de type A .
2. Quelle est la probabilité pour qu’un élève obtienne son diplôme de fin d’études
selon son état présent dans le cursus dans un établissement de type A.
3.Quel est le temps moyen pour qu’un élève obtienne son diplôme, selon son
état présent dans le cursus, dans un établissement de type A
B.A. Ferrif
24/07/01
114
4. Quelle est la durée moyenne des études dans un établissement de type A.
5. Quel est le temps moyen avant renvoi dans un établissement de type A.
6. Que doit penser un élève qui entre dans le système en première année ?
Comment peut-il augmenter ses chances de succès ?
Remarque: L'ensemble de ces questions sera repris pour un établissement de
type B à la fin du chapitre 2.
B.A. Ferrif
24/07/01
115
Thème d'étude 2 : Un problème de reconnaissance des
formes.
À chaque instant n NŒ , un automate écrit un nombre qui est soit 0 soit 1 avec
une probabilité de 1/2 pour chacun d’eux. On obtient ainsi, par exemple, la
séquence :
0111010110101110001010.........
Dans une telle séquence de nombres, on cherche la fréquence empirique
d’occurrence du motif 010 sans compter les occurrences qui chevauchent une
occurrence déjà comptée :
0111010110101110001010
oui oui
non
} }{.........
1- Quelle est la fréquence empirique d’occurrence du motif 010 ?
2- Quelle est la durée moyenne d’attente du motif 010 ?
3- Quelle est la fréquence empirique d’occurrence du motif 111 ?
4- Quelle est la durée moyenne d’attente du motif 111 ?
Nous allons maintenant créer un jeu à deux joueurs : le jeu consiste à obtenir, en
4 jets successifs, le mot 1111 ou le mot 0011. Si c’est le mot 1111, c’est le joueur
A qui gagne ;si c’est le mot 0011, c’est le joueur B le vainqueur.
5- Quelle est la durée moyenne du jeu ?
6- Quelle est la probabilité que le joueur A gagne ?
7- Quelle est la probabilité que le joueur B gagne ?
8- Quel est le temps moyen d'attente avant que le joueur B gagne ?
B.A. Ferrif
24/07/01
116
3-Processus de Poisson et
Processus de renouvellement
B.A. Ferrif
24/07/01
117
Prérequis et Objectifs
Ce que vous devez au minimum maîtriser pour aborder ce chapitre :
∑ Probabilités : Concepts d’espace probabilisable et d’espace probabilisé, de
variable aléatoire, de moment d’une variable aléatoire, de dépendance et
d’indépendance (en théorie des probabilités); la formule de Bayes. La loi
exponentielle et la loi de Poisson ainsi que leurs principales caractéristiques.
Le théorème de la limite centrale pour l’étude des processus de Wiener. Les
processus de Markov.
∑ Analyse : La résolution des systèmes différentiels du premier ordre. La
transformation de Fourier, la distribution de Dirac.
Ce que vous devez maîtriser pour tirer pleinement profit de ce chapitre :
En plus des éléments précédents :
∑ Informatique: des éléments d'algorithmique et des éléments de
programmation sous Mathematica ou sous un autre langage pour réaliser les
simulations.
∑ Processus stochastiques : Les processus de Markov.
Ce que vous devez savoir faire à la fin de cette leçon :
∑ Savoir reconnaître, modéliser, simuler et utiliser les processus de comptage,
de Poisson, de naissance et de disparition, de renouvellement.
∑ Savoir poser et résoudre un problème y faisant référence.
B.A. Ferrif
24/07/01
118
Ce qui vous est proposé dans ce chapitre :
∑ Aborder les concepts généraux,
∑ Se familiariser avec la modélisation et la simulation des processus de
comptage, de Poisson, de naissance et de disparition, de renouvellement;
∑ S’exercer sur des applications immédiates,
∑ Réfléchir sur des problèmes concrets et de synthèse,
∑ S’évaluer par tests de connaissance et de savoir-faire.
B.A. Ferrif
24/07/01
119
Introduction
La notion de chaîne de Markov nous permet la modélisation et l'étude des
phénomènes aléatoires pour lesquels les changements d'états se produisent à
des instants déterminés a priori. Une telle discrétisation de l'axe temporel
n'autorise pas une étude satisfaisante des phénomènes où les évènements
peuvent se produire à n'importe quel moment. Pour de tels phénomènes, nous
devons utiliser des modèles à temps continu. Les processus de Poisson en sont
des exemples. C'est par la notion de processus de comptage que nous
commencerons cette leçon, puis nous étudierons la notion de processus de
Poisson que nous généraliserons en celle de processus de renouvellement après
avoir étudié les processus de naissance et de disparition.
1- Processus de comptage.
1-1 - Exemples :
Considérons les phénomènes aléatoires suivants :
1 - L'arrivée d'une requête dans le système d'un centre informatique.
2 - Un appel téléphonique dans un centre de réservation.
3 - Une panne dans un système manufacturé.
De tels évènements peuvent être décrits à l'aide de processus de comptage
( )Nt t RŒ + où Na représente le nombre d'issues depuis le temps t = 0 et avant
(strictement) t = a .
Une trajectoire d'un tel processus est représentée par une fonction en escalier
non décroissante.
Précisons la définition d'un tel processus.
B.A. Ferrif
24/07/01
120
1-2 - Définition des processus de comptage
Le processus Nt t N( ) Πest un processus de comptage si et seulement si :
1 - N0 0= ,
2 - N Nt Π,
3 - Si s t< alors N Ns t£ ,
4 - N Nt s- est le nombre d'issues qui se sont produites dans l'intervalle s t,[ [.
2 - Processus de Poisson.
2-1 – Processus stochastique à accroissements indépendants
Un processus stochastique ( )Xt t RŒ sera dit à accroissements indépendants si, et
seulement si, les évènements se produisant dans des intervalles de temps
disjoints sont indépendants ; c'est-à-dire:
si a b1 1,] [, a b2 2,] [, .. , a bn n,] [ sont des intervalles disjoints, alors les n variables
aléatoires X Xb a1 1- , X Xb a2 2
- , … , X Xb an n- sont indépendantes.
2-2 - Processus stochastique à accroissement stationnaire
Un processus stochastique ( )Xt t RŒ sera dit à accroissement stationnaire si
X Xt h s h+ +- a la même distribution que X Xt s- quels que soient s et t avec s t< et
pour tout h > 0; ce qui signifie que la loi de probabilité de X Xt s- dépend
seulement de la longueur de l'intervalle s t,] [ et non de s et t.
B.A. Ferrif
24/07/01
121
2-3 – Définition d’un processus de Poisson
Un processus de comptage ( )Xt t RΠest un processus de Poisson de taux (ou
d'intensité) l > 0 si, et seulement si, les conditions suivantes sont satisfaites :
1 - Le processus est à accroissements indépendants.
2 - Le processus est à accroissement stationnaire.
3 - La probabilité qu'un (et un seul) événement se produise dans tout intervalle
de longueur h est égale à l.h o h+ ( ) i.e. P N h h o h( ) . ( )=( ) = +1 l
4 - La probabilité que plus d'un événement se produise dans tout intervalle de
longueur h est o(h) , i.e., P N h o h( ) ( )≥( ) =2 .
Remarque :
- (3) et (4) entraînent que P N h h o h( ) . ( )=( ) = - +0 1 l .
2-4- Simulation :
Simuler une variable aléatoire dont la loi de probabilité est :
∑ une loi de Poisson homogène,
∑ Une loi exponentielle
∑ une loi de Poisson non homogène.
2-5 – Loi de probabilité du nombre d’événements dans un intervalle de
temps donné.
Théorème : Soit ( )Xt t RŒ un processus de Poisson de taux l > 0 . La variable
aléatoire N décrivant le nombre des évènements dans tout intervalle de temps de
longueur t > 0 a une loi de Poisson de paramètre l.t .
C'est-à-dire P N k et
ktt
k
( ).!
.= =( )-l l
k = 0, 1, 2,..
B.A. Ferrif
24/07/01
122
Il s'ensuit que le nombre moyen d'évènements se produisant dans tout intervalle
de temps de longueur t est l.t
���� Par hypothèse ( )Xt t RŒ est un processus de Poisson de taux l > 0 ; il s'ensuit
que le nombre d'évènements se produisant dans tout intervalle de temps ne
dépend que de la longueur de cet intervalle. On peut donc sans perdre de
généralité se limiter à l'intervalle 0,t[ ]. Afin d'alléger les notations, posons :
" Π( ) = ( ) =( )n N P t P N t nn, .
La probabilité qu'aucun événement ne se soit produit à l'instant t+h, i.e
P t P N t0 0( ) = ( ) =( ) , est donnée par
P t h P t P N t h N t0 0 0+( ) = ( ) +( ) - =[ ]( ). ( ) (car les accroissements sont
indépendants),
P t h P t P N t0 0 0+( ) = ( ) =[ ]( ). ( ) (car les accroissements sont stationnaires),
P t h P t h o h0 0 1+( ) = ( ) - + ( )( ). .l (conséquence directe de la définition).
Il en résulte que:P t h P t
hP t
o h
h0 0
0
+( ) - ( )= - ( ) +
( )l. ,
et lorsque h Æ 0 on a LimP t h P t
h
dP
dtt P t
hÆ
+( ) - ( )= ( ) = - ( )
0
0 0 00l. ,
équation différentielle du premier ordre, dont la condition initiale
P P N0 0 0 0 1( ) = ( ) =( ) = entraîne la solution P t e t0 ( ) = -l . .
Supposons N t h n+( ) = > 0 ; en d'autres termes supposons que n évènements se
produisent jusqu'à l'instant t+h.
Cette hypothèse se décompose en :
∑ n évènements se produisent entre les instants 0 et t et aucun évènement ne
se produit entre t et t+h;
∑ n-1 évènements se produisent entre les instants 0 et t et un évènement se
produit entre t et t+h;
B.A. Ferrif
24/07/01
123
∑ n-k évènements se produisent entre les instants 0 et t et k évènements se
produisent entre t et t+h (avec k nŒ{ }2,..., ).
Il s'ensuit :
P t h P t h o h h P t o hn n n+( ) = ( ) - +( ) + ( ) +-. . ( ) . . ( )1 1l l ,
soitP t h P t
hP t P t
o h
hn n
n n
+( ) - ( )= - ( ) + ( ) +-l l. .
( )1
Lorsque h Æ 0 on a LimP t h P t
h
dP
dtt P t P t
h
n n nn nÆ -
+( ) - ( )= ( ) = - ( ) + ( )
01l l. . .
Nous avons ainsi :dP
dtt P t P t P t e t1
1 0 1( ) = - ( ) + ( ) = - ( ) + -l l l l l. . . . . ,
l'équation homogène dP
dtt P t1
1 0( ) + ( ) =l. est de la même forme que l'équation
précédente, on a donc P t f t e t1( ) = -( ). .l avec P1 0 0( ) = , d'où f ( )0 0= . Il s'ensuit
dP
dtt f t e f t et t1 ( ) = - +- -( ). ©( ).. .l l , d'où par identification f t©( ) = l et f t t( ) .= l puisque
f ( )0 0= .
Il en résulte P t t e t1( ) = -l l. . . .
Par récurrence, on vérifie que :
P t P N ne t
nn
t n
( ) = =( ) =( )-l l. .!
☺
2-6- Equations d'Erlang
Les équations :dP
dtt P t0
0( ) = - ( )l.
dP
dtt P t P tn
n n( ) = - ( ) + ( )-l l. . 1
sont connues sous le nom d'équations différentielles d'Erlang.
B.A. Ferrif
24/07/01
124
2-7- Exercice : Un problème de qualité :
Une étude de qualité montre qu’une machine qui produit des câbles
téléphoniques sous-marins génère des défauts de fabrication qui suivent une loi
de Poisson de taux 0,1 par kilomètre.
Quelle est la probabilité qu’aucun défaut n’apparaisse dans les deux premiers
kilomètres du câble?
Supposons qu’il n’existe pas de défaut dans les deux premiers kilomètres de la
production. Quelle est la probabilité qu’aucun défaut ne se trouve entre les
kilomètres 2 et 3 ?
Dans l’une des productions, on a constaté 3 défauts dans le premier kilomètre et
4 défauts sur les 3 kilomètres suivants. Quelle est La probabilité de cet
évènement ?
2-8- Test :
L’analyse des accidents de la circulation touchant les piétons d’une certaine zone
géographique montre que les trafics des voitures particulières et des camions
peuvent être modélisés par des variables aléatoires.
Désignons par t n la variable aléatoire décrivant la durée qui sépare les
passages de deux voitures particulières, disons ceux des n-ième et (n+1)-ième
véhicules. Les variables t n sont supposées indépendantes et de même densité :
f t eT
t
( ) =-1
1010 si t ≥ 0 et f tT ( ) = 0 si t < 0 (où t est mesuré en
secondes).
Désignons par un la variable aléatoire décrivant la durée qui sépare les
passages de deux camions, disons ceux des n-ième et (n+1)-ième véhicules.
B.A. Ferrif
24/07/01
125
Les variables un sont supposées indépendantes et de même densité :
f t eT
t
( ) =-1
4040 si t ≥ 0 et f tT ( ) = 0 si t < 0 (où t est mesuré en
secondes).
1) Supposons que seulement les voitures particulières soient autorisées à rouler
un certain jour.
Quelle est la probabilité pour qu’un passant traverse la route sans se faire heurter
par un véhicule s’il met 4 secondes pour le faire ? (On suppose, bien entendu,
qu’il est exposé pendant toute cette durée).
2) Sur cette même voie de circulation, un autre passant plus lent traverse en 6
secondes ; mais, comme il est plus robuste, il peut supporter sans dommage
deux collisions avec les voitures particulières.
Quelle est la probabilité qu’il traverse sans dommage cette voie ?
3) Sur une autre voie de circulation, les voitures particulières et les camions sont
autorisés à circuler. Les arrivées des voitures et des camions sont supposées
indépendantes.
Quelle est la probabilité, pour un passant traversant cette voie en 4 secondes, de
le faire sans être heurté ?
4) Sur la même voie de circulation que dans la question (3):
quelle est la probabilité, pour un passant lent (il met 6 secondes pour traverser la
voie), mais robuste (il peut sans dommage supporter 2 collisions avec des
voitures particulières ou (exclusif) une collision avec un camion), de traverser
cette voie sans dommage ?
5) On se place sur la voie de circulation des questions (1) & (2).
Quelle est la probabilité pour que le passant lent et robuste et le passant rapide,
qui débutent leur traversée immédiatement après le passage d’une voiture,
traversent sans dommage pour aucun d’eux ?
B.A. Ferrif
24/07/01
126
2-9 – Loi des temps d’attentes inter-évènements
Théorème : Soit ( )Xt t RŒ un processus de Poisson de taux l . Soit
0 1 2 3< < <t t t ,...une suite d'instants d'apparition d'évènements et soit t n n N( ) Œ * les
temps d ' a t t en te en t re ces évènemen ts dé f i n i s pa r
t t t1 1 2 2 1 1= = - = - -t t t t tk k k, ,..., ; t n est la durée séparant le (n-1)-ième évènement
du n-ième évènement , autrement dit le temps pendant lequel le processus reste
dans l'état n-1.
La suite de variables aléatoires t n n N( ) Œ * est indépendante, équidistribuée,
exponentielle, d'espérance 1l
, donc de densité f te si t
si t
t
( ) =>£
ÏÌÓ
-l l 0
0 0.
� La suite de variables aléatoires t n n N( ) Œ * est indépendante : en effet un
processus de Poisson est à accroissements indépendants ; il s'ensuit que les
évènements se produisant après l'instant tk sont indépendants des évènements
se produisant avant l'instant tk et donc que la suite de variables aléatoires
t n n n n Nt t= -( )- Œ1 * est indépendantes.
Pour tout h ≥ 0 et tout n ≥ 1 les évènements t n h>{ } et N t h N tn n- -+( ) - ( ) ={ }1 1 0
sont équivalents. Il s'ensuit
P h P N t h N t P N h en n nht l>{ }( ) = +( ) - ( ) ={ }( ) = ( ) ={ }( ) =- -
-1 1 0 0 .
et donc
P h enht l£{ }( ) = - -1 . ☺
Si l'on pose Sn n= + + +t t t1 2 ... , Sn représente le temps écoulé jusqu'à la
réalisation du nème évènement.
B.A. Ferrif
24/07/01
127
2-10- Loi du temps d'attente du nème événement Sn n= + + +t t t1 2 ... .
Théorème : La loi du temps d'attente du nème événement, Sn n= + + +t t t1 2 ... , a
pour densité la fonction f tt
ne n tS
n nt
n( ) =
-( ) = >-
-l l1
11 2 0
!, , ,...,. (autrement dit une
distribution gamma).
� Désignons ,conformément à ce qui précède, le temps d'attente du nème
évènement par Sn .
L'événement S tn £ se produit si et seulement si au moins n évènements se sont
produits dans l'intervalle 0, t( ] . Comme de plus le nombre des évènements qui se
produisent dans l'intervalle 0, t( ] possède une loi de Poisson de moyenne l.t , on
a
F t P S t P N nt e
j
t e
jn tS n t
j t
j n
j t
j
n
n( ) = £( ) = ≥( ) =
( )= -
( )=
-
=
+• -
=
-
 Âl ll l.!
.!
, , ,...,. .
1 1 20
1
. Il en
résulte que la densité f tSn( ) de la loi de Sn est donnée par
f td
dt
t e
j
t
ne n tS
j t
j
n n nt
n( ) = -
( )È
ÎÍ
˘
˚˙ =
-( ) =-
=
- --Â1
11 2
0
1 1l lll.
! !, , ,...,
..
☺
2-11 – Processus de comptage et processus de Poisson
Théorème : Soit ( )Nt t RŒ + un processus de comptage tel que les temps d'attente
des évènements t n n N( ) Œ * soient des variables aléatoires indépendantes
équidistribuées et exponentielles, d'espérance 1l
. Alors ( )Nt t RΠ+ est un processus
de Poisson de taux l .
B.A. Ferrif
24/07/01
128
2-12 – Equivalence d'évènements
On vérifie que l'évènement N t n( ) £ est équivalent à l'évènement S tn + >1 et de
manière duale que l'évènement N t n( ) ≥ est équivalent à l'évènement S tn + £1 . On
en déduit que : P N t n P S t et S t P S t P S tn n n n( ( ) ) ( ) ( ) ( )= = > £ = £ - £+ +1 1 .
2-13 – Temps d'occurrence d'un évènement
Théorème : Soit ( )Nt t RŒ un processus de Poisson et supposons qu'un
évènement se produise dans l'intervalle [0, t]. La variable aléatoire Y décrivant les
temps d'occurrence de cet évènement a une distribution continue uniforme sur [0,
t]. Ainsi, tout sous-intervalle de longueur d Œ] ]0,t a la probabilité dt
de contenir
le temps d'occurrence de l'évènement.
2-14 - Graphes associés à un processus de Poisson
Deux représentations sont fréquentes :
Première représentation :
∑ Les états sont numérotés par le nombre d'arrivées qui se sont produites
depuis l'instant initial;
∑ Les arcs sont valués par les probabilités de passage, pendant un intervalle de
temps petit (i.e rendant négligeable la probabilité d'avoir plus d'une arrivée
pendant cette durée) :
B.A. Ferrif
24/07/01
129
La matrice (différentielle) P des probabilités de transition s'écrit :
H
t t
t t
t
t t
t t
t
=
--
-
--
-
Ê
Ë
ÁÁÁÁ
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0 0
0 0 0 1 0
0 0 0 0 1
0 0 0 0 0 1
l ll l
l
l ll l
l
. . ... ...
. . ... ...
. ... ...
... ... ... ... ... ... ... ...
... . . ...
... . . ...
... . ...
... ... ... ... ... ... ... ...
D DD D
D
D DD D
D
ÁÁÁÁÁÁÁ
ˆ
¯
˜˜˜˜˜˜˜˜˜˜
et on a :
P t t
P t t
P t t
P t t
P t t
P t t
t t
t t
t
0
1
2
4
5
6
1 0 0 0 0
0 1 0 0 0
0 0 1
+( )+( )+( )
+( )+( )+( )
Ê
Ë
ÁÁÁÁÁÁÁÁÁÁ
ˆ
¯
˜˜˜˜˜˜˜˜˜˜
=
--
-
DDD
DDD
D DD D
D...
...
. . ... ...
. . ... ...
. ...
l ll l
l 00 0 0
0 0 0 1 0
0 0 0 0 1
0 0 0 0 0 1
0
1
2
4
5
...
... ... ... ... ... ... ... ...
... . . ...
... . . ...
... . ...
... ... ... ... ... ... ... ...
....
--
-
Ê
Ë
ÁÁÁÁÁÁÁÁÁÁ
ˆ
¯
˜˜˜˜˜˜˜˜˜˜
( )( )( )
( )l ll l
l
D DD D
D
t t
t t
t
P t
P t
P t
P t
P tt
P t
o t
( )( )
Ê
Ë
ÁÁÁÁÁÁÁÁÁÁ
ˆ
¯
˜˜˜˜˜˜˜˜˜˜
+ ( )
6
...
D
ce qui s'écrit encore :
B.A. Ferrif
24/07/01
130
P t t P t
P t t P t
P t t P t
P t t P t
P t t P t
P t t P t
0 0
1 1
2 2
4 4
5 5
6 6
1 0+( ) - ( )+( ) - ( )+( ) - ( )
+( ) - ( )+( ) - ( )+( ) - ( )
Ê
Ë
ÁÁÁÁÁÁÁÁÁÁ
ˆ
¯
˜˜˜˜˜˜˜˜˜˜
=
-DDD
DDD
...
...
...l l 00 0 0
0 1 0 0 0
0 0 1 0 0 0
0 0 0 1 0
0 0 0 0 1
0 0 0 0 0 1
0
1
2
4
...
... ...
... ...
... ... ... ... ... ... ... ...
... ...
... ...
... ...
... ... ... ... ... ... ... ...
....
--
--
-
Ê
Ë
ÁÁÁÁÁÁÁÁÁÁ
ˆ
¯
˜˜˜˜˜˜˜˜˜˜
( )( )( )
l ll
l ll l
l
P t
P t
P t
P tt
P t
P t
t o t( )( )( )
Ê
Ë
ÁÁÁÁÁÁÁÁÁÁ
ˆ
¯
˜˜˜˜˜˜˜˜˜˜
+ ( )
5
6
...
.D D
soit
dP t
dtG P t
( )= ( ). .
La matrice G est fréquemment appelée matrice génératrice du processus (de
Markov!). La solution du système différentiel du premier ordre est alors donnée
par :
P t e P tG t( ) = ≥. ,0 0 où P P0 0= ( ) .
Rappelons que e I G t G t G tG t. .!
.!
. ....= + + ( ) + ( ) +12
13
2 3 qui converge pour tout t fini.
Seconde représentation :
∑ Les états sont numérotés par le nombre d'arrivées qui se sont produites
depuis l'instant initial;
∑ Seuls les arcs de i à i+1 sont représentés et ces derniers sont valués par
l'intensité l :
B.A. Ferrif
24/07/01
131
3 - Processus de naissance et de disparition.
Intuitivement, un processus de naissance et de disparition modélise l'évolution
d'une population s'accroissant au rythme de l'arrivée de nouveaux membres et
diminuant par la disparition de membres anciens. Un tel modèle, dont l'intérêt
dans l'étude des problèmes de nature sociale ou biologique est évident, s'avère
également très utile dans l'étude de certains problèmes de files d'attente (cf
Leçon 5); ainsi, par exemple, dans l'étude de l'arrivée et du traitement des
requêtes dans un système de traitement de l'information.
3-1- Définition
Soit ( )Xt t RŒ un processus stochastique à temps continu et à espace d'états
discret N. Supposons que ce processus décrive un système se trouvant dans
l'état en à l'instant t, et interprétons cet état de la façon suivante : le système a
une population composée de n éléments.
Le système est dit décrire un processus de naissance et de disparition si et
seulement si :
il existe une suite de taux de naissance ln n N( ) Πet une suite de taux de disparition
mn n N( ) Œ à termes positifs ou nuls tels que les conditions suivantes soient
satisfaites :
1- Les seuls changements d'état autorisés sont de l'état e0 à l'état e1 ainsi que,
pour tout n ≥ 1, de l'état en à l'état en+1 et de l'état en à l'état en-1 .
Autrement dit : à un instant donné, ne peut avoir lieu qu'une naissance ou
qu'une disparition; aucune disparition ne peut avoir lieu dans un système vide.
B.A. Ferrif
24/07/01
132
2- Si au temps t le système est dans l'état en , pour n ≥ 1, la probabilité de
transition de l'état en à l'état en+1 entre les instants t et t+h est donnée par
ln h o h. ( )+ et celle de transition de l'état en à l'état en-1 par mn h o h. ( )+ .
Autrement dit : Cette condition fixe la probabilité de transition lorsque la
population est de cardinal n.
3- La probabilité que plus d'une transition s'effectue dans l'intervalle de temps
[t,t+h] , "h petit", est o(h).
Autrement dit : dans un intervalle de temps petit, la probabilité d'avoir plus d'une
naissance, ou plus d'une disparition, est négligeable.
3-2- Graphe d'un processus de naissance et de disparition
3-3- Remarques :
∑ Dans l'hypothèse où nous interprétons un processus de naissance ou de
disparition comme une file d'attente, l'état en s'interprète comme la présence
de n consommateurs (ou requêtes) attendant ou recevant un service.
∑ Autrement dit, un processus de naissance et de disparition se modélise
comme la superposition de deux processus de Poisson.
B.A. Ferrif
24/07/01
133
3-4- Probabilité d'un état pour un processus de naissance et de disparition
Proposition : Avec les notations précédentes, si on pose P t P X nn t( ) = =( ) et si
pour tout n, P t pn n( ) = (c’est-à-dire si P tn ( ) ne dépend pas de t), on a :
p p nnn
nn+
+
=È
ÎÍ
˘
˚˙ ≥1
1
0l
m. , soit p p1
0
10=
È
ÎÍ
˘
˚˙
lm
. , p p21
21=
È
ÎÍ
˘
˚˙
lm
. , ..
p p nnn
n
=È
ÎÍ
˘
˚˙ ≥-l l l
m m m0 1 1
1 20 1
. .... ...
. .
La probabilité que le système soit dans l'état eo est donnée par pnn NŒÂ = 1 .
On a donc p p Sn
n0
0
1
0 1 1
1 201 1. ...
. .... ...
.... . ,+ÊËÁ
ˆ¯̃
+ +ÊËÁ
ˆ¯̃
+È
ÎÍ
˘
˚˙ = =-l
ml l l
m m m
et l'équilibre statistique existe si S < +• .
� Pour n ≥ 1, la probabilité P t hn +( ) pour qu’à l’instant t h+ le système soit dans
l’état en a quatre composantes :
1) La probabilité que le système ait été dans l’état n à l’instant t et qu’aucune
transition ne se soit produite entre les instants t et t+h. Cette probabilité est le
produit de P tn ( ) par la probabilité que le système ne passe pas de l’état n à l’état
n+1, soit 1- + ( )ln h o h. , par la probabilité que le système ne passe pas de l’état n
à l’état n-1, soit 1- + ( )mn h o h. .
Il s’ensuit que
P t h o h h o h P t h o h h h ho h o hn n n n n n n n n( ) . . ( ) . . . .1 1 1 2- + ( )( ) - + ( )( ) = - + ( ) - + - ( ) + ( )( )l m m l l m l
= - - + ( )( ) = - -( ) + ( )P t h h o h P t h h o hn n n n n n( ) . . ( ) . .1 1m l m l
puisque :
- o h h o h o hn( ) - ( )( ) = ( )1 m . . ,
- - - ( ) + ( ) = ( )l m ln n nh ho h o h o h2 . ,
B.A. Ferrif
24/07/01
134
- P t o h o hn ( ). ( ) = ( ) .
2- La probabilité P tn - ( )1 que le système soit dans l’état en-1 à l’instant t, multipliée
par la probabilité qu’une transition de l’état n-1 vers l’état n ait lieu dans l’intervalle
de temps t, t+h soit :
P t h o h P t h o hn n n n- - - -+ ( )( ) = + ( )( )1 1 1 1( ) . ( ) .l l
3- La probabilité P tn + ( )1 que le système soit dans l’état n+1 à l’instant t , multipliée
par la probabilité qu’une transition de l’état n+1 vers l’état n se produise durant
l’intervalle de temps t, t+h soit :
P t h o hn n+ + + ( )1 1( ) .m
4- La probabilité que deux transitions ou plus se produisent entre les instants t et
t+h qui laissent le système dans l’état n soit : o(h).
Les quatre évènements précédents étant mutuellement exclusifs il s’ensuit que
P t h P t h h hP t hP t o hn n n n n n n n( ) ( ) . . . ( )+ = - -( ) + ( ) + + ( )- - + +1 1 1 1 1l m l m
Il s’ensuit :
(1) P t h P t
hP t P t P t
h
hn n
n n n n n n n
( ) ( )( ). ( ) . ( ) ( )
( )+ -= - + + + +- - + +l m l m1 1 1 1
0 ,
soit, lorsque h -> 0 :
(2) dP t
dtP t P t P tn
n n n n n n n
( )( ). ( ) . ( ) . ( )= - + + +- - + +l m l m1 1 1 1 (si n ≥ 1).
Pour n = 0 on a : dP t
dtP t P t0
0 0 1 1
( ). ( ) . ( )= - +l m .
Si l'état initial est ei alors les conditions initiales sont données par
(3) Pi(0) = 1 , Pj(0) = 0 si i jπ .
B.A. Ferrif
24/07/01
135
3-5- Remarques
1- Un processus de naissance ou de disparition donne lieu à un ensemble infini
d'équations. On démontre que ce système a une solution Pn(t) pour tout n et tout
t sous des conditions très générales, mais, sauf dans des cas particuliers, celles-
ci sont analytiquement difficiles à obtenir.
2- Un processus tel que mn = 0 (respectivement tel que ln = 0 ) est dit processus
de naissance pur (respectivement processus de disparition pur).
3- Dans le cas d'un processus de naissance pur avec l ln = et mn = 0 pour tout
n , on a :
dP t
dtP t P t si nn
n n n
( ). ( ) . ( ) ( )= - + ≥-l l 1 1
pour n = 0 on a : dP t
dtP t0
0
( ). ( )= -l , de solution :
P tn
e t n tnt n( )
!.( . ) ,.= ≥ ≥-1
0 0l l .
Il en résulte que l'on peut caractériser les processus de Poisson comme des
processus de naissance purs avec taux de naissance constant.
Un autre cas où il est possible de trouver la solution du problème est le cas où
Pn(t) tend vers une valeur constante pn lorsque t tend vers l'infini pour tout n. Ce
cas, souvent dit d'équilibre statistique, correspond à un système stationnaire
(encore appelé à équilibre d'état car l'état du système ne dépend pas du temps).
Alors, en utilisant la situation d’équilibre statistique , par passage à la limite dans
les équations (1) et (2) précédentes on a : LimdP t
dttn
Æ +• =( )
0 pour tout n et
Lim P t pt n nÆ +• =( ) ;
on obtient alors :
B.A. Ferrif
24/07/01
136
- l m l mn n n n n n np p p si n- - + ++ - + = ≥1 1 1 1 0 1. ( ).
- m l1 1 0 0 0 0. . .p p si n- = =
Soit : m l m ln n n n n n n np p p p si n+ + - -- = - ≥1 1 1 1 1. . . . .
Posons g p p si n N on a g g pour nn n n n n n n= - Œ = ≥- - +m l. . , : .1 1 1 1
Il s'ensuit gn = constante et par (2) g1 = 0, donc gn = constante = 0 pour tout n
(µn > 0 pour tout n).
On a ainsi :
p p nnn
nn+
+
=È
ÎÍ
˘
˚˙ ≥1
1
0l
m. , soit p p1
0
10=
È
ÎÍ
˘
˚˙
lm
. , p p21
21=
È
ÎÍ
˘
˚˙
lm
. , ..
p p nnn
n+
-=È
ÎÍ
˘
˚˙ ≥1
0 1 1
1 20 1
l l lm m m
. .... ...
. .
La probabilité que le système soit dans l'état eo est donnée par pnn NŒÂ = 1 .
On a donc p p Sn
n0
0
1
0 1 1
1 201 1. ...
. .... ...
.... . ,+ÊËÁ
ˆ¯̃
+ +ÊËÁ
ˆ¯̃
+È
ÎÍ
˘
˚˙ = =-l
ml l l
m m m
et la probabilité de l'état d'équilibre existe si S < +• .☺
3-6- Equation des flux et loi de Khirchhoff
La relation dP t
dt
dP X n
dtn t( )
==( ) = [Intensité du flux de probabilité qui entre dans
l'état n à l'instant t]-[ Intensité du flux de probabilité qui sort de l'état n à l'instant t],
devient en régime stationnaire (permanent)
[Intensité du flux de probabilité qui entre dans l'état n] = [ Intensité du flux de
probabilité qui sort de l'état n] , (car X A et P X n pt t nÆ =( ) Æ ).
On reconnaît la loi de Khirchhoff de l'électricité.
3-7- Test
On considère la salle d'attente d'un médecin dans laquelle :
∑ Les patients arrivent suivant un processus de Poisson de taux l ,
B.A. Ferrif
24/07/01
137
∑ Le temps nécessaire pour servir un client a une distribution exponentielle de
paramètre m .
On pose r lm
= .
Calculer p P X nn t= =( ) en fonction de r .
Quel est le temps moyen passé par un client qui arrive dans le système ?
Quel est le temps moyen passé par un client dans la salle d'attente ?
Quel est le nombre moyen de clients dans le système ?
Quel est le nombre moyen de clients dans la salle d'attente ?
Analyser r lm
= .
Calculer pour l =1
16 et m =
115
puis pour l =1
16 et m =
114
le nombre de patients
dans le système et le temps moyen dont dispose le médecin pour se reposer
dans la journée.
3-8- Test :
Le système de réservation d’une compagnie aérienne est architecturé autour de
deux ensembles informatiques fonctionnant en redondance. Le taux de panne de
chacun d’eux obéit à une loi exponentielle de moyenne 2000 heures.
1- Quelle est la probabilité que le système n’ait pas de panne pendant :
a) 168 h ?
b) 30 jours (24 h de fonctionnement par jour)?
2- Quel est le temps moyen entre deux pannes ?
B.A. Ferrif
24/07/01
138
L’étude précédente est peu réaliste, elle néglige la possibilité de réparation. Nous
allons donc supposer maintenant qu’un ordinateur en panne peut être réparé (!).
3- Prenons comme hypothèse que le temps moyen de réparation suit une loi
exponentielle de moyenne 10 h. Quel est, sous cette nouvelle hypothèse, le
temps moyen entre deux pannes ?
4- Processus de renouvellement.
Un processus de Poisson peut être caractérisé comme un processus de
comptage pour lequel les temps d'attente entre deux évènements sont des
variables aléatoires indépendantes, équidistribuées et exponentielles. Un
processus de renouvellement est une généralisation du processus de Poisson.
4-1 - Définition d’un processus de renouvellement
Définition : Soit ( )Nt t RŒ + un processus de comptage et X1 le temps d'occurrence
du premier évènement. Désignons par Xn la variable aléatoire qui mesure
l'intervalle de temps séparant les évènements n-1 et n de ce processus pour n>1.
( )Nt t RΠ+ est un processus de renouvellement si et seulement si la suite de
variables aléatoires positives ou nulles Xn n( ) >1 est indépendante et équidistribuée.
4-2- Test
Montrer qu'un processus de Poisson de taux l est un processus de
renouvellement .
B.A. Ferrif
24/07/01
139
4-3 - Remarques :
1 - Quand un évènement compté par Nt se produit, on dit qu'un
renouvellement est intervenu.
2 - W W X X X nn n0 1 20 1= = + + + ≥, ... , s'appelle le temps d'attente jusqu'au
nième renouvellement.
On peut représenter les relations entre N et Wt n par
X1X
2 X3 X4
t
Nt
W0 W1 W2 W3
1
2
3
4-4 – Loi de Wn
Désignons par F x P X xn( ) = £( ) la fonction de répartition de la variable aléatoire
Xn (rappelons que toutes les variables Xn ont la même fonction de répartition) et
par F x P W xn n( ) = £( ) la fonction de répartition de la variable aléatoire Wn ; on sait
que F xn ( ) est le produit de convolution F x Fn
n( ) = ( )* , soit :
B.A. Ferrif
24/07/01
140
F x F x y dF y F x y dF yn n n
x( ) = -( ) ( ) = -( ) ( )-
+•
-Ú Ú10 10
4-5 – Fonction de renouvellement
Définition : Soit ( )Nt t RŒ + un processus de renouvellement. Alors la fonction Mt
définie pour tout t RŒ + par M E Nt t= ( ) est dite fonction de renouvellement du
processus .
4-6- Test
Quelle est la fonction de renouvellement d'un processus de Poisson considéré
comme processus de renouvellement .
4-7 – Equivalence de Nt et de Wt
Théorème : Soit ( )Nt t RŒ + un processus de renouvellement.
Alors N k W tt t≥ ¤ £ .
� Dire que N kt ≥ c'est dire qu'il y a eu au moins k renouvellements jusqu'à
l'instant t ; c'est donc dire que W tt £ . Et inversement dire que W tt £ c'est dire
qu'au moins k renouvellements se sont produits à l'instant t ☺
Autrement dit :
Dire que le nombre de renouvellements ayant eu lieu jusqu'à l'instant t est au
moins k équivaut à dire que le kème renouvellement s'est produit avant (ou à)
l'instant t.
Ceci explique que le processus de comptage ( )Nt t RŒ + et le processus ( )Wn n NŒ
soient tous les deux appelés processus de renouvellement.
B.A. Ferrif
24/07/01
141
4-8 – Relation entre la fonction de renouvellement Mt et la fonction de
répartition Fn
Il résulte de (4-5) que " Œ " Œ ≥( ) = £( ) = ( )+t R k N P N k P W t F tt t k, ,* . Il s'ensuit que
" Œ " Œ =( ) = ≥( ) - ≥ +( ) = ( ) - ( )++t R k N P N k P N k P N k F t F tt t t k k, ,* 1 1 . Or comme
M E N P N k P W t F tt t tk
kk
kk
= ( ) = ≥ = £ = ( )=
+•
=
+•
=
+•
  Â( ) ( )1 1 1
, on a :
Théorème : Soit ( )Nt t RŒ + un processus de renouvellement de fonction de
renouvellement Mt . Alors Mt et F x P X nn( ) = £( ) n =1 2 3, , ,... peuvent être
définies de manière unique l'une par l'autre.
4-9 – Quelques variables aléatoires de la théorie du renouvellement
Les variables aléatoires suivantes présentent un intérêt particulier dans les
problèmes de renouvellement.
Définition : Soit ( )Nt t RŒ + un processus de renouvellement. Posons :
g t NW tt
= -+1 (durée de vie résiduelle)
d t nt W= - (durée de vie courante)
b g dt t t= + (durée de vie totale)
Autrement représenté :
B.A. Ferrif
24/07/01
142
t
Nt
W0 W 1 WNt
1
2
3
WNt +1t
bt
gtdt
4-10- Processus de Poisson vu comme un processus de renouvellement
Théorème : Soit ( )Nt t RŒ + un processus de Poisson de paramètre l . Alors :
∑ P x e xtx( ) .g l£ = - ≥( )-1 0 ou P x e xt
x( ) .g l> = ≥( )- 0
∑ P xe x t
t xt
x
( )( ).
dl
< =- £ <
£ÏÌÓ
-1 0
1
∑ E etx( ) . .b
l ll= + -( )-1 1
1
���� On a par définition
" Π=( ) =( )
= ( ) =-k N P N kt
ke et M E N tt
nt
t t* .,
.!
.l ll .
Illustrons la situation à l'aide de :
B.A. Ferrif
24/07/01
143
t
Nt
1
2
3
gt
t t+x
x
Or la durée de vie résiduelle ( g t NW tt
= -+1 ) à l'instant t est supérieure à x si et
seulement s'il n'y a pas de renouvellement dans l'intervalle t t x, +( ] . Comme un
processus de Poisson est à accroissements indépendants cet événement a la
même probabilité que l'événement : aucun renouvellement ne s'est produit dans
l'intervalle 0,x( ].
Autrement dit P x P N N P N et t x t xx( ) ( ) ( ) .g l> = - = = = =+
-0 0 .
B.A. Ferrif
24/07/01
144
La durée de vie courante d t nt W= - ne peut pas être supérieure à t. Si x t< , la
durée de vie courante dépasse x si et seulement si aucun renouvellement n'est
intervenu dans l'intervalle t x t-( ], d'où : P xe x t
t xt
x
( )( ).
dl
< =- £ <
£ÏÌÓ
-1 0
1.
Par définition de la durée de vie totale b g dt t t= + on a :
E E E e dx et t tt
ttb g d
l l ll l( ) = ( ) + ( ) = + = + -( )- -Ú1 1 1
10
. .
☺☺☺☺
4-11 - Théorème du renouvellement élémentaire
Les processus de Poisson sont des processus de renouvellement dont la
fonction de renouvellement est linéaire; ce sont les seuls ayant cette particularité.
Toutefois chaque processus de renouvellement a une fonction de renouvellement
asymptotiquement linéaire au sens suivant :
Théorème (théorème du renouvellement élémentaire)
Soit ( )Nt t RΠ+ un processus de renouvellement avec E Xn( ) = m pour tout n.
Alors M t
tquand t
( )Æ Æ +•
1m
.
����☺☺☺☺ Nous renvoyons à la littérature pour la démonstration de ce résultat ☺☺☺☺����
4-12- Test
Désignons par ( )Nt t RŒ + un processus de renouvellement de fonction de
renouvellement M t t( ) .= 5 . Quelle est la loi de probabilité du nombre de
renouvellements jusqu'à l'instant t=15 ?
B.A. Ferrif
24/07/01
145
5- Etude d’un processus "Flip-Flop"
Désignons par ( )Xt t RŒ un processus aléatoire Flip-Flop d’espace d’états 0 1,{ };
supposons que les instants de transition suivent une loi de Poisson ; en d’autres
termes, supposons que la probabilité d’avoir n transitions dans un intervalle de
temps de longueur t est donnée par : P n tt
ne
nt,
.!
.( ) =( ) -l l , loi de Poisson de
paramètre l.t ( l représente le nombre moyen de transitions par unité de temps)
et supposons qu’à l’origine le processus vaut 0 avec la probabilité p et 1 avec la
probabilité 1-p.
Simuler ce processus puis l’étudier.
5-1- Simulation
Nous présentons ci-dessous les graphes résultats de 4 simulations pour l = 1 et
100 observations. Les graphes ont été tracés pour les valeurs d’état - +{ }1 1, pour
une meilleure lisibilité; les points ont été reliés pour la même raison.
B.A. Ferrif
24/07/01
146
Les traits horizontaux représentent les durées inter-évènements, les traits
verticaux symbolisent l’instant du changement d’état.
5-2- Etude du processus Flip-Flop.
Calcul de E Xt( )
On a E X P X P Xt t t( ) = =( ) + =( )0 0 1 1. . ; cherchons P Xt =( )1 :
P X P X X P X P X X P X
P pour un nombre pair decommutationssur t P X
P pour un nombreimpair decommutationssur t P X
t t t t t=( ) = = =( ) =( ) + = =( ) =( ) =
= [ ]( ) =( ) +
[ ]( ) =( )
1 1 0 1 1 0 0
0 1
0 0
0 0
0
0
. .
, .
, .
Comme les instants de commutation suivent une loi de Poisson, il vient :
B.A. Ferrif
24/07/01
147
P pour un nombre pair decommutationssur tt
ne e ch t
nt
n
t02
2
0
,.. !
. .. .[ ]( ) =( )
( ) = ( )-
=
•-Â l ll l
P pour un nombre pair decommutationssur tt
ne e sh t
nt
n
t02 1
2 1
0
,.. !
. .. .[ ]( ) =( )
+( ) = ( )+
-
=
•-Â l ll l
Soit :
P X e p ch t e p sh ttt t=( ) = -( ) ( ) + ( )- -1 1l ll l. .. . . . . . ,
d’où il s’ensuit :
E X e p ch t e p sh t e p ch t p sh ttt t t( ) = -( ) ( ) + ( ) = -( ) ( ) + ( )[ ]- - -l l ll l l l. . .. . . . . . . . . .1 1
Si p =12
, le processus est clairement stationnaire. On a en effet :
" Π=( ) = =( ) =t R P X P Xt t, 1 012
Si p π12
, lorsque t est grand par rapport à l-1 on a P Xt =( ) ª112
et le processus
est « quasi-stationnaire ».
Supposons désormais que p =12
.
Fonction d’autocorrélation :
On a :
E X X P X X
P X X P X
P pour un nombre pair decommutationssur t t
t t t t
t t t
. . . ,
.
,
+ +
+
( ) = = =( )= = =( ) =( )= +[ ]( )
t t
t
t
1 1 1 1
1 1 1
Or on a P Xt =( ) =112
, d'où
E X X en
et t
n
n
..
!. .
+-
=
•-( ) = ( )
( ) = +( )Âtl t l tl t1
2 214
12
1
2 .
B.A. Ferrif
24/07/01
148
Densité spectrale de puissance de ( )Xt t RŒ
F E X X F et t. .+
-( )( ) = +( )ÊËÁ
ˆ¯̃ = +
+tl t d l
l p w14
114 4 4
22 2 2 .
B.A. Ferrif
24/07/01
149
Appendice
Processus de Poisson non
homogène
B.A. Ferrif
24/07/01
150
Introduction
La faiblesse majeure des processus de Poisson tient à ce qu’ils modélisent des
situations en faisant pour hypothèse que le processus est à accroissement
stationnaire, autrement dit homogène. Mais, dans la pratique, les processus de
Poisson que l’on peut inventorier ne le sont que rarement. La difficulté d’obtenir
des résultats analytiques avec des processus de Poisson non homogènes
conduit, trop fréquemment, à une approximation des problèmes par des
processus homogènes. L’usage de la simulation aide, toutefois, à aplanir cette
difficulté et promet les modèles non homogènes à un avenir certain ; qu’il
convient donc de maîtriser.
Définition : Un processus de comptage ( )Nt t RŒ est un processus de Poisson de
taux (ou d'intensité) l t t( ) >, 0si, et seulement si, les conditions suivantes sont
satisfaites :
1 - Le processus est à accroissements indépendants.
2 - La probabilité qu'un (et un seul) événement se produise dans l’intervalle
[t, t+ h] est égale à LimP N
ht
h
h
Æ
=( ) = ( )0
1l .
3 - La probabilité que plus d'un événement se produise dans l’intervalle
[t, t+h] est égale à LimP N
hh
h
Æ
≥( ) =0
20 .
B.A. Ferrif
24/07/01
151
La fonction m(t) définie par m t s ds tt
( ) ,= ( ) ≥Ú l0
0est la fonction de valeur moyenne
et on peut établir le résultat suivant :
Proposition : N t s N t+( ) - ( ) est une variable aléatoire de Poisson d’espérance
m t s m t+( ) - ( ) .
Pour interpréter un processus de Poisson non homogène on peut s’appuyer sur le
résultat suivant :
Proposition : Si des évènements se produisent suivant un processus de Poisson
d’intensité l et si, indépendamment du passé, un événement qui arrive à
l’instant t le fait avec une probabilité p(t), alors le processus ainsi imaginé est un
processus de Poisson non homogène d’intensité l lt p t( ) = ( ). .
B.A. Ferrif
24/07/01
152
4-Réseaux de files d’attente
B.A. Ferrif
24/07/01
153
Prérequis et Objectifs
Ce que vous devez au minimum maîtriser pour aborder ce chapitre :
∑ Probabilités : Concepts d’espace probabilisable et d’espace probabilisé, de
variable aléatoire, de moments d’une variable aléatoire, de dépendance et
d’indépendance (en théorie des probabilités); la formule de Bayes. Les lois de
Bernoulli, exponentielle, de Poisson, ainsi que leurs principales
caractéristiques. Les fonctions génératrices.
Ce que vous devez maîtriser pour tirer pleinement profit de ce chapitre :
En plus des éléments précédents :
∑ Informatique: des éléments d'algorithmique et des éléments de
programmation sous Mathematica ou sous un autre langage pour réaliser les
simulations.
∑ Analyse : Transformation de Fourier , en Z.
∑ Probabilités : Les fonctions génératrices.
∑ Systèmes stochastiques : Les processus de naissance et de disparition.
Ce que vous devez savoir faire à la fin de cette leçon :
∑ Savoir reconnaître et utiliser les concepts de files d'attente et de réseaux de
files d'attente dans des cas simples.
∑ Savoir modéliser et simuler des problèmes qui relèvent de ces concepts.
B.A. Ferrif
24/07/01
154
Ce qui vous est proposé dans ce chapitre :
∑ Aborder les concepts généraux,
∑ Se familiariser avec la modélisation de files d'attente ou de réseaux de files
d'attente dans des cas simples
∑ S’exercer sur des applications immédiates,
∑ Réfléchir sur des problèmes concrets et de synthèse,
∑ S’évaluer par tests de connaissance et de savoir-faire.
B.A. Ferrif
24/07/01
155
1-Système à files d'attente
1-1- Schéma général
Un système à files d'attente est constitué :
∑ d'un ensemble de clients pris dans une population donnée (client est un mot
générique pour désigner aussi bien un individu qu'une requête à un système
informatique ...),
∑ d'un ensemble d'équipements de service (équipement de service = serveur
destiné à répondre à la demande du client).
∑ d'un ensemble de files d'attente (si tous les serveurs sont occupés lorsqu’un
client arrive, celui-ci doit rejoindre la ou les files d'attente).
1-2- Description des caractéristiques d'un système à files d'attente (SAFA).
Parmi les éléments qui permettent de caractériser un SAFA on trouve :
B.A. Ferrif
24/07/01
156
∑ La population ou source : celle-ci peut être finie ou infinie. Il est clair qu'une
population infinie est plus simple à décrire qu'une population finie en ce sens
que le nombre de clients dans le système n'affecte pas le modèle d'arrivée
des clients dans ce dernier.
∑ Le modèle des arrivées : La capacité d'un SAFA à fournir un service à un flot
de clients dépend non seulement du taux moyen des arrivées mais également
du modèle de ces arrivées. Ainsi supposons que les clients arrivent aux
instants 0 0 1 2< < < < < <t t t tn... ... . Les variables aléatoires T t tk k k= - -1
" Œ( )k N * appelées temps d'inter-arrivée, seront usuellement supposées
indépendantes et équidistribuées. Le modèle de ces arrivées sera donné par
la distribution de probabilité des temps d'inter-arrivées. Un modèle fréquent
est le modèle exponentiel; la densité de probabilité est alors d t e t( ) = -l l. . sur
R+, où l désigne le taux moyen des arrivées. On parle alors de modèle
poissonnien. Les modèles d'Erlang et hyperexponentiel sont également
fréquents (cf exercices).
∑ La distribution de la durée des services :
Il est fréquent que l'on utilise une distribution exponentielle car cette distribution
est "sans mémoire" [propriété de Markov : le temps moyen pour le client, pour
recevoir le service qu'il attend, est indépendant du service déjà fourni par le
serveur].∑ Systèmes multiserveurs à distribution de service exponentielle :
B.A. Ferrif
24/07/01
157
Supposons le système à plusieurs serveurs identiques, chacun possédant
une distribution exponentielle de durée de service égale à µ, et supposons de
plus qu'à l'instant présent, n serveurs soient occupés. Désignons alors par Ti
le temps pendant lequel le serveur i (i=1,..,n) va demeurer occupé par le
service en cours. Il résulte de la propriété de Markov que chaque variable
aléatoire Ti a pour loi une loi exponentielle de paramètre µ . Si T désigne la
durée s'écoulant jusqu'à l'achèvement de la première tâche en cours, cette
durée est égale à Min T T Tn1 2, ,...,( ) ; il s'ensuit que la distribution de T est une
distribution exponentielle de paramètre n.m .
∑ Fonction de répartition du service aléatoire :
Dans toute la théorie des files d'attente, la distribution de la durée des services
s'appelle le service aléatoire et la fonction de répartition est donnée par :
W t P s t e est
t
Ws( ) = <( ) = - = ---
1 1m. où Ws =1m
.
∑ Capacité maximum d'un système à files d'attente :
Dans certains systèmes, la capacité de la file d'attente est supposée infinie :
ainsi tout client arrivant dans le système est autorisé à attendre jusqu'à ce que
le service désiré puisse lui être fourni.
Pour d'autres systèmes, la capacité de la file d'attente est nulle: tout client
arrivant dans le système alors que les serveurs sont occupés est rejeté (appel
téléphonique).
D'autres systèmes enfin autorisent un nombre de clients fini K dans la file
d'attente.
B.A. Ferrif
24/07/01
158
∑ Nombre de serveurs
Le système le plus simple a un seul serveur, il ne peut servir qu'un seul client
à la fois.
Un système multiserveur a c serveurs habituellement indentiques , un tel
système peut servir c clients simultanément.
Un système est dit à un nombre infini de serveurs si tout client pénétrant dans
le système est immédiatement traité.
∑ Discipline de file d'attente ( ou discipline de service) :
Plusieurs règles de sélection existent pour sélectionner le client à traiter; les
plus courantes sont :
� FIFO (first-in, first-out) encore dite FCFS (first-come, first-
served),
� LCFS (last-come, first-served), encore dite LIFO (last-in, first-
out),
� RSS (random-selection-for-service), encore dite SIRO (service-
in-random- order).
1-3- Notation de Kendall.
Cette notation est souvent utilisée pour décrire un système à files d'attente; elle
se présente sous la forme suivante :
A/B/c/K/m/Z où :
∑ A désigne la distribution des temps entre deux arrivées,
∑ B désigne la distribution des durées de service,
B.A. Ferrif
24/07/01
159
∑ c le nombre de serveurs,
∑ K la capacité du système,
∑ m la taille de la population,
∑ Z la discipline de service.
Les symboles habituellement utilisés pour A et B sont :
� GI (general independent interarrival time),
� G (general service time),
� Hk (k-stage hyperexponential interarrival or service time distribution),
� Ek (Erlang-k interarrival or service time distribution),
� M (exponential interarrival or service time distribution),
� D (deterministic (constant) interarrival or service time distribution),
� U (uniform interarrival or service time distribution).
La notation abrégée A/B/c est d'usage fréquent; elle suppose: qu'il n'y a pas de
limite à la longueur de la file d'attente, que l'ensemble des clients est infini et que
la discipline de file est FCFS.
Ainsi par file d'attente de type M/G/1 nous entendrons que les équations du
modèle sont valables en général, donc par exemple pour un système M/M/1.
1-4- Notations et définitions de base pour les systèmes à files d'attente.
Les notations suivantes sont courantes :
B.A. Ferrif
24/07/01
160
c Nombre de serveurs identiques.
L Nombre moyen de clients dans le système à l'équilibre L E N= ( ).
Lq Nombre moyen de clients dans la file d'attente à l'équilibre,
L E Nq q= ( ).
Ls Nombre moyen de clients recevant un service dans le système à
l'équilibre, L E Ns s= ( ).
l Taux moyen des arrivées dans le système.
m Taux moyen de service par serveur.
N t( ) Variable aléatoire décrivant le nombre de clients dans le système
à l'instant t.
N Variable aléatoire décrivant le nombre de clients dans le système à
l'équilibre.
N tq ( ) Variable aléatoire décrivant le nombre de clients dans la file
d'attente à l'instant t.
Nq Variable aléatoire décrivant le nombre de clients dans la file à
l'équilibre.
N ts( ) Variable aléatoire décrivant le nombre de clients recevant un
service à l'instant t.
Ns Variable aléatoire décrivant le nombre de clients recevant un
service dans le système à l'équilibre.
p tn ( ) Probabilité de la présence de n clients dans le système à l'instant
t.
pn Probabilité de la présence de n clients dans le système à l'état
d'équilibre.
B.A. Ferrif
24/07/01
161
q Variable aléatoire décrivant le temps passé par un client dans la file
d'attente (avant de recevoir un service).
r Utilisation de serveurs r lm
= =c
E N
cs( )
.
s Variable aléatoire décrivant le temps de service E s( ) =1m
.
t Variable aléatoire décrivant le temps d'inter-arrivée E( )tl
=1
.
w Variable aléatoire décrivant le temps total qu'un client passe dans
le système w q s= + .
W Temps moyen passé par un client dans le système à l'équilibre
W E w W Wq s= ( ) = + .
Wq Temps moyen passé par un client dans la file d'attente à l'équilibre
W E q W Wq s= ( ) = - .
Ws Temps moyen passé en traitement par un client dans le système à
l'équilibre W E ss = ( ) .
1-5- Loi de Little
Désignons par :
� L le nombre moyen de consommateurs dans le système,
� W le temps moyen passé par un consommateur dans le système,
� l le taux moyen d'arrivée dans le système.
La loi de Little dit que , dans un système en équilibre, L W= l .
B.A. Ferrif
24/07/01
162
Une autre version de ce résultat est le :
Théorème de Little : Soit L(x) le nombre de consommateurs présents dans le
système à l'instant x. Définissons :
L par L Limt
L x dxt
t= Æ +• Ú1
0( ) ,
l par l = Æ +•LimN t
tt
( ) où N t( ) est le nombre de consommateurs arrivant
dans le système dans l'intervalle de temps 0,t[ ],
désignons par Wi le temps passé dans le système pour le i-ème consommateur
et définissons le temps moyen passé dans le système par W Limn
Wn ii
n
= Æ +•=
Â1
1
.
Si l et W existent et sont finis, il en est de même de L et on a : L W= l .
2- Processus de naissance et de disparition considérés
comme systèmes à files d'attente.
Un grand nombre de systèmes à files d'attente se modélisent comme des
processus de naissance et de disparition. Dans ce cas l'interprétation est la
suivante : le système sera dans l'état n à l'instant t si et seulement si le nombre
de consommateurs dans le système est n, c'est-à-dire N t n( ) = . Une naissance
est l'arrivée d'un consommateur, une disparition correspond au départ d'un
consommateur après que celui-ci ait reçu un traitement complet. Nous ne
considérerons que les SAFA à l'état d'équilibre.
B.A. Ferrif
24/07/01
163
Ainsi, étant donnés l’ensemble ln{ } des taux de naissances et l’ensemble mn{ }
des taux de disparition, on sait que si on pose P t P X nn t( ) = =( ) et si pour tout n,
P t pn n( ) = (c’est-à-dire si P tn ( ) ne dépend pas de t) on a :
p p nnn
nn+
+
=È
ÎÍ
˘
˚˙ ≥1
1
0l
m. , soit p p1
0
10=
È
ÎÍ
˘
˚˙
lm
. , p p21
21=
È
ÎÍ
˘
˚˙
lm
. , …
p p nnn
n
=È
ÎÍ
˘
˚˙ ≥-l l l
m m m0 1 1
1 20 1
. .... ...
. .
La probabilité que le système soit dans l'état eo est donnée par pnn NŒÂ = 1 .
On a donc p p Sn
n0
0
1
0 1 1
1 201 1. ...
. .... ...
.... . ,+ÊËÁ
ˆ¯̃
+ +ÊËÁ
ˆ¯̃
+È
ÎÍ
˘
˚˙ = =-l
ml l l
m m m
et l'équilibre statistique existe si S < +• .
☺
3- Etude d’une file d’attente de type M/M/1
3-1- Rappel de quelques notations et définitions de base pour les systèmes à
files d'attente.
L Nombre moyen de clients dans le système à l'équilibre L E N= ( ).
Lq Nombre moyen de clients dans la file d'attente à l'équilibre,
L E Nq q= ( ).
Ls Nombre moyen de clients recevant un service dans le système à
l'équilibre, L E Ns s= ( ).
l Taux moyen des arrivées dans le système.
B.A. Ferrif
24/07/01
164
m Taux moyen de service par serveur.
N Variable aléatoire décrivant le nombre de clients dans le système à
l'équilibre.
Nq Variable aléatoire décrivant le nombre de clients dans la file à
l'équilibre.
Ns Variable aléatoire décrivant le nombre de clients recevant un
service dans le système à l'équilibre.
pn Probabilité de la présence de n clients dans le système à l'état
d'équilibre.
r Utilisation de serveurs r lm
= =c
E N
cs( )
.
(c représente le nombre de serveurs identiques).
W Temps moyen passé par un client dans le système à l'équilibre
W E w W Wq s= ( ) = + .
Wq Temps moyen passé par un client dans la file d'attente à l'équilibre
W E q W Wq s= ( ) = - .
Ws Temps moyen passé en traitement par un client dans le système à
l'équilibre W E ss = ( ) .
3-2- Caractéristiques des systèmes à files d'attente de type M/M/1
Dans un système de type M/M/1 :
∑ le modèle des arrivées est poissonien; si nous désignons par l le taux des
arrivées , il est indépendant du nombre de consommateurs dans le système,
B.A. Ferrif
24/07/01
165
∑ le temps de service est exponentiel de moyenne m ; cette moyenne est
indépendante du nombre de consommateurs dans le système.
∑ le nombre de serveurs est égal à 1.
Les caractéristiques les plus utilisées des systèmes à files d'attente de type
M/M/1 sont données par le théorème suivant :
Théorème : Un système à files d'attente de type M/M/1 possède les
caractéristiques suivantes:
r l= Ws ;
p P N nnn= = = -( ) ( )1 r r , n=0,1,2, ... ;
P N n n Nn( ) ,≥ = Œr ;
L E N W= = =-
( ) l rr1
;
E Nq( ) =-r
r
2
1;
s rrN
221
=-( )
;
L Wq q= =-
l rr
2
1 ;
s r r rrNq
22 2
2
11
=+ --
( )( )
;
W E wWs= =-
( )1 r
;
WW
qs=
-r
r1.
B.A. Ferrif
24/07/01
166
� On sait, par définition d’un processus de Poisson, que la probabilité pour qu’un
unique événement se produise dans un intervalle de longueur h est donnée par
l.h o h+ ( ) .
Nous avons donc ici " Π=n N n* ,l l .
Quand un client reçoit un service, la probabilité que ce dernier soit terminé dans
un intervalle de temps de longueur h est donnée par m.h o h+ ( ) et on a
" Π=n N n* ,m m . Comme r l
m= , on a :
1 1 11
10
1
0 1 1
1 2
2+ÊËÁ
ˆ¯̃
+ +ÊËÁ
ˆ¯̃
+ = +ÊËÁ
ˆ¯̃
+ +ÊËÁ
ˆ¯̃
+ = + + + + + =-
-lm
l l lm m m
lm
lm
r r rr
.... .... ...
... ... ... ... ...n
n
n
nn
Il en résulte :
" Π= =( ) = -( )n N p P N nnn, .1 r r .
De plus P N n n Ni n
i( ) ,≥ = -( ) Œ=
+•
 1 r r ; il s'ensuit :
P N ni n
i in
i
n( )≥ = -( ) = =-( )
-( ) ==
+•
=
+•
 Â11
10
r r rr r
rr
La loi PN de N est donc une loi géométrique de paramètres p q= - =1 r r, , donc
de moyenne : E Nq
p( ) = =
-( )r
r1 et de variance s r
rN
q
p2
2 21
= =-( )
.
Il en résulte que L E N= ( ) =-( )r
r1.
Comme Ws =lr
, la loi de Little permet d’écrire W E wL Ws= ( ) = =
-l r1 .
W E q W WW
q ss= ( ) = - =
-r
r.
1 .
B.A. Ferrif
24/07/01
167
En appliquant la loi de Little on obtient :
L E N Wq q q= ( ) = =-
l rr
.2
1.
La probabilité que le serveur soit occupé est : 1 0 1 1- =( ) = - -( ) =P N r r .
Loi de Nq :
On a :
P N P N P Nq =( ) = =( ) + =( ) = -( ) + -( )0 0 1 1 1r r r.
et
" Π=( ) = = +( ) = -( ) +n N P N n P N nqn* , .1 1 1r r
La fonction génératrice (transformée en Z) de Nq est donc
G z E z P N i z z
zz
Nx
qi
i i i
i
i i
i
q( ) = ( ) = =( ) = -( ) + -( ) + -( )
= - + -( ) = - +-( )-
=
+•+
=
+•
=
+•
 Â
Â
0
1
0
2
0
2
1 1 1
1 1 11
1
. . . .
. ..
.
r r r r r
r r r r rr rr
Il s'ensuit que
d
dzG z
d
dz z zNq
( ) = - +-( )-
ÊËÁ
ˆ¯̃
=-( )-( )
11
1
1
12
2
2rr rr
r rr
.
.
.
.
et comme E N Limd
dzG zq
zNq
( ) = ( )Æ1
, on a :
E N Limd
dzG z Lim
zq
zN
zq( ) = ( ) =
-( )-( )
=-Æ Æ1 1
2
2
21
1 1
r rr
rr
.
.
Comme on sait que s N N N Nq q q q
d
dzG
d
dzG
d
dzG2
2
2
2
1 1 1= ( ) + ( ) - ( )ÊËÁ
ˆ¯̃ , on obtient :
s r r rrNq
22 2
2
11
=+ --
( )( )
☺
B.A. Ferrif
24/07/01
168
On montre également que :
Théorème - Un système à files d'attente de type M/M/1 possède les
caractéristiques suivantes:
E N Nq q >( ) =-
01
rr
Var N Nq q >( ) =-
01 2
rr( )
W t P w tt
W( ) ( ) exp= £ = -
-ÊËÁ
ˆ¯̃1
P w tt
W( ) exp .> =
-ÊËÁ
ˆ¯̃
s w W2 2=
W t P q tt
Wq ( ) ( ) exp= £ = --Ê
ËÁˆ¯̃1 r
P q tt
W( ) exp .> =
-ÊËÁ
ˆ¯̃r
sr r
rqsW22
2
2
1=
-( )-( )
�☺ La démonstration est laissée au lecteur amateur d'analyse ☺�
4 - Réseaux de files d’attente
4-1- Réseaux à commutation de paquets
Un réseau à commutation de paquets – Internet par exemple – transporte des
blocs de symboles binaires. Pour transporter les paquets émis par un utilisateur,
B.A. Ferrif
24/07/01
169
le réseau utilise une route constituée d’une suite de canaux de transmission
reliant la source à la destination. Entre deux canaux successifs sont situés des
commutateurs munis de mémoires, les nœuds du réseau. Un canal donné
apparaît dans plusieurs routes. Le commutateur en amont d’un canal sert à
mettre en attente les paquets qui ne peuvent pas être émis immédiatement. Un
tel réseau peut donc être vu comme un réseau de files d’attente.
4-2- Systèmes informatiques
Les systèmes informatiques peuvent fréquemment s’imaginer comme des
réseaux de files d’attente. Ainsi par exemple dans un « Personal Computer » on
trouve la mémoire principale, la mémoire virtuelle et aussi les mémoires et
caches d’entrée – sortie, de périphériques d’entrée – sortie, l'unité centrale,… ; il
peut y avoir une file d’attente associée à chacune de ces ressources. Nous
supposerons dans la suite que les ressources sont interconnectées. Ainsi la sortie
d’une file d’attente peut être considérée comme l’entrée d’une autre file d’attente.
Très peu de résultats sont accessibles directement de manière analytique.
Heureusement ,il existe quelques modèles de réseaux de files d’attente qui
permettent de modéliser les systèmes informatiques.
Un réseau de files d’attentes est ouvert si les « clients » arrivent de l’extérieur,
sont traités par le système et en repartent.
Dans un réseau de files d’attentes fermé un nombre fini de « clients » circulent
indéfiniment dans le système. (Ce modèle convient bien aux systèmes de
maintenance).
Il existe bien entendu des réseaux de files d’attente mixtes.
B.A. Ferrif
24/07/01
170
Nous désignerons par :
- K le nombre de nœuds (centres de service) du réseau ;
- Sk le temps moyen de service par visite au centre k ;
- Vk le nombre moyen de visites d’un client au centre k ,
- Dk = Vk * Sk la demande de service totale au centre k pour un client (en unités de
temps de service).
Si le système a une capacité de traitement moyenne (on dit également un débit
moyen) l alors on a la relation Vkk=
ll
qui porte souvent le nom de loi du flux
forcé.
Un des concepts fondamentaux quand on étudie un système informatique est le
concept de saturation. Par système saturé on entend un système dont l’une au
moins des ressources est saturée. Ressource ou serveur sont dit saturés
lorsqu’ils fonctionnent à 100%. Il est clair que la saturation est dépendante de la
demande. Il faut noter que suivant la nature de la charge de travail, la nature de la
saturation est modifiée. Ainsi pour les traitements en calcul scientifique la
saturation provient généralement du CPU et pour les traitements de gestion elle
se situe en général au niveau des entrées – sorties.
4-3- Les Réseaux de Jackson.
Les réseaux de Jackson sont décrits dans le théorème suivant :
Théorème de Jackson :
Soit un réseau de files d’attente formé de k nœuds satisfaisant les conditions
suivantes:
B.A. Ferrif
4/07/02
171
1) Chaque nœud k consiste en ck serveurs ou ressources identiques de loi
exponentielle, de taux moyen de service mk pour chacun d’eux;
2) Le modèle des arrivées des clients qui viennent de l’extérieur au nœud k du
système est poissonnien avec un taux moyen des arrivées lk . Les clients
arrivent également au nœud k à partir des autres nœuds à travers le réseau.
3) Une fois servi au nœud k, un client va instantanément au nœud j (j=1, 2, …,m)
avec la probabilité pkj ; ou quitte le réseau avec la probabilité 11
-=
 pkjj
K
.
Alors pour chaque nœud k, le taux moyen Lk des arrivées au nœud k est donné par
L Lk k jkj
K
jp= +=
Âl1
. .
De plus, si nous posons p n n nK1 2, ,..,( ) pour désigner le fait qu’à l’équilibre la
probabilité pour qu’il y ait nk clients au kème nœud pour k = 1, 2, ….K , et si de plus
Lk k kc< .m pour k = 1, 2, ….K alors p n n n p n p n p nK K K1 2 1 1 2 2, ,.., ...( ) = ( ) ( ) ( ) où p nk k( ) est
la probabilité pour qu’à l’équilibre il y ait nk clients au kème nœud s’il est traité comme
une M/M/ ck file d’attente de taux moyen d’arrivée Lk et de temps moyen de service
1 /mk pour chacun des ck serveurs.
De plus chaque nœud k se comporte comme s’il était un système à files d’attente
indépendant de type M/M/ ck de taux moyen d’arrivée Lk.
4-4- Test
On considère le système bouclé de type M/M/1 (dans la notation de Kendall abrégée)
suivant :
B.A. Ferrif
24/07/01
172
File d'attenteServeur
1/ m
Entrée
q=1-p
l l L
Sort ie
p
Bouclage
Ce système représente, par exemple, une installation qui reçoit des messages
(entrée) et les oriente vers une destination appropriée (sortie). Lorsque le
message arrive à destination, un accusé de réception parvient au système et lui
indique si la transmission est correcte (en utilisant un code détecteur d'erreur). Si
la transmission n'a pas été correcte, ce qui arrive avec une probabilité q=1-p, il
est nécessaire de retransmettre le message donc de le renvoyer au serveur
(bouclage) ; le message est transmis correctement avec la probabilité p.
L'intensité des arrivées sur le serveur par l'entrée est notée l , l'intensité des
arrivées sur le serveur (entrée + bouclage) est notée L.
Le temps moyen de service du serveur est 1 / m
Application numérique :
- On pose l = 4 messages par seconde,
- Le temps moyen passé dans le serveur est Ws = 0 22, seconde,
- La probabilité qu'un message soit transmis correctement est p=0,99.
1- Trouver l'intensité L.
B.A. Ferrif
24/07/01
173
2- Trouver le niveau d'utilisation r du serveur.
3- Trouver le nombre moyen L de messages dans le système.
4- Trouver le temps moyen W passé par un message dans le système.
4-5- Modèle du serveur central
Ce réseau de files d’attente est utilisé pour modéliser certains systèmes
informatiques à multiprogrammation. Il apporte, en particulier, des réponses à
certaines questions concernant l’utilisation de la mémoire centrale du calculateur.
Un système informatique multiprogrammé est caractérisé par un ensemble de K
ressources interconnectées (unités centrales, disques, unités d’entrée – sortie
etc..) et par un ensemble de programmes qui doivent recevoir certains services
de ces ressources lors de leur exécution. Ainsi, par exemple, un programme peut
avoir besoin d’un service de l’unité centrale (exécution de lignes de code sans
accès mémoire), puis d’un service de l’un des disques, puis à nouveau de l’unité
centrale…Chaque ressource doit traiter un flux de demandes de services
émanant des divers programmes en cours de traitement. Si plusieurs
programmes demandent la même ressource à un instant donné, un mécanisme
de file d’attente est activé.
Nous allons nous intéresser à un réseau fermé (cf. schéma). Le serveur central
est l’unité centrale (le CPU). On dispose de K-1 ressources d’entrée-sortie de
taux moyen de service mk (k = 2, ….K) et de discipline de file d’attente FCFS. Le
nombre de programmes en circulation sera fixé égal à N. Un programme sera
considéré comme étant une entité (certains disent un jeton) circulant
« interminablement » dans le système. À l’issue d’un traitement complet dans le
B.A. Ferrif
24/07/01
174
serveur central (CPU) un programme peut retourner dans la file d’attente du
serveur central avec une probabilité p1 ou dans la file d’attente de l’une des E/S
avec la probabilité pk (k = 2, ….K). Après passage dans la ressource, il retourne
dans le serveur central pour un nouveau traitement…
Les algorithmes ci-dessous permettent d’analyser en valeur moyenne l’évolution
du système.
Algorithme 1.
On considère le système à serveur central schématisé ci-dessous. On suppose
donnée la valeur Dk pour chaque nœud k ainsi que le niveau de
multiprogrammation N. Nous pouvons mesurer les performances du système
par :
1ère étape (Initialisation) : Lk 0 0[ ] = , k = 1, 2, ….K .
2ème étape (Calcul) : Pour n = 1, 2, ….N calculer :
W n D L nk k k[ ] = + -[ ]( )1 1 , k = 1, 2, ….K ;
W n W nkk
K
[ ] = [ ]=
Â1
;
l nn
W n[ ] = [ ] ;
L n n W nk k[ ] = [ ] [ ]l , k = 1, 2, ….K .
3ème étape (Mesure de performance) :Temps de réponse
W W N= [ ] ,
Débit
B.A. Ferrif
24/07/01
175
l l= [ ]N
Utilisation des serveurs
r lk kD= , k = 1, 2, ….K .
Algorithme 2.
On considère le système à serveur central schématisé ci-dessous. L’algorithme 2
permet de construire les paramètres nécessaires à l’utilisation de l’algorithme 1.
1ère étape (Initialisation) : Fixons le taux de visite V1 pour l’unité CPU à :
Vp1
1
1=
2ème étape (Calcul) : Pour k = 2, ….K calculer :
V p Vk k= 1,
3ème étape (Calcul de Dk) :
D V Sk k k= , k = 1, 2, ….K .
4-6- Schéma d’un modèle du serveur central
B.A. Ferrif
24/07/01
176
CPU
2
3
K - 1
K
N programmes en circulation
Organes d'entrée-sortie
pK
p2
p3
p1
pk-1
Nouveau programme
4-7- Test
Un ingénieur de la société NetSouris est chargé de réaliser l’étude de
performance d’un système informatique architecturé autour d’une unité centrale
(nœud 1), d’une unité d’entrée-sortie (nœud 2) et d’un niveau de
multiprogrammation N=2. La demande D1 est estimée à 0,4 s ; la demande D2 est
estimée à 0,4 s et les modèles de chacun des deux temps de service sont des
modèles exponentiels.
Le cahier des charges prévoit la fourniture de :
1) Lk[n] pour k=1,2 et n= 0, 1, 2 ;
B.A. Ferrif
24/07/01
177
2) Lk pour k=1,2 ;
3) Wk[n] pour k=1,2 et n= 1, 2 ;
4) W[n] , pour n= 1, 2 ;
5) rk = rk 2[ ] pour k=1,..,2 ;
6) l l= [ ]2 ,
performances qu’il est demandé de chercher.
4-8- Etude et simulation
Il est demandé d’étudier le modèle de Jackson, puis de concevoir et
d’implémenter un simulateur écrit en Mathematica permettant de mesurer les
performances d’un système à serveur central.
Données qui seront fournies :
1) Le niveau de multiprogrammation N,
2) La demande de service total Dk (unité de mesure : la seconde).
Le simulateur MVA doit retourner :
1) Le temps de réponse moyen du système W=W[N],
2) La capacité de traitement l l= [ ]N ,
3) Les rk pour k=1,..,K ,
4) Les Lk pour k=1,..,K .
B.A. Ferrif
24/07/01
178
4-9- Exercice : Un système à file d'attente
Des clients se présentent à un guichet tenu par un seul serveur. On fait, sur le
système, les hypothèses suivantes:
H1) Arrivée des clients : les clients peuvent se présenter au guichet aux
seuls instants t n= 0 1, , ..., , ...
A chaque valeur entière du temps, la probabilité pour qu’un client se
présente au guichet est a a0 1< <( ) . On suppose, de plus, que la
probabilité pour que deux clients au moins se présentent au même instant
est nulle.
La population est supposée infinie.
H2) Durée de service et comportement du serveur : les durées des
services effectués sont des variables aléatoires entières (à valeurs dans
N *) indépendantes, de même loi caractérisée par la propriété suivante :
tant qu’un client est pris en charge, à chaque valeur entière du temps, la
probabilité pour que le service se termine est b b0 1< <( ) . Désignons par
S la variable aléatoire représentant la durée d'un service.
Dès que le serveur est libre, il prend en charge le premier client de la file d’attente
; lorsqu’il n’y a pas de file d’attente, il attend l’arrivée du premier client suivant et
le prend immédiatement en charge.
H3) Comportement des clients : ils se placent dans la file d’attente selon
l’ordre d’arrivée et acceptent d’attendre quel que soit leur rang.
La capacité de la file d’attente est infinie.
B.A. Ferrif
24/07/01
179
∑ Quelle est la loi de probabilité de la durée d’un service et quelle est son
espérance mathématique?
∑ Quelle est la loi de probabilité de l’intervalle de temps séparant deux arrivées
consécutives et quelle est son espérance mathématique?
∑ Le système risque-t-il de s’engorger (en d’autres termes la file d’attente peut-
elle devenir infinie)?
A chaque instant t , l’état du système constitué par les clients en attente , ou se
faisant servir, est caractérisé par leur nombre Q t( ) .
Les changements d’état du système ne peuvent se produire qu’aux valeurs
entières du temps ; par conséquent, l’état du système reste le même sur tout
intervalle ouvert n n-] [1, ; on le note Q n _( ) et on parlera abusivement de
« l’instant n _( ) » .
∑ Déterminer la matrice de transition T du système, c’est-à-dire la matrice des
probabilités conditionnelles des états à l’instant n +( )1_ connaissant l’état à
l’instant n _( ). On pose p n P Q n j Q n ii j, ( _) ( _)( ) = + = =( )1 .
∑ Quelle est la distribution stationnaire p p p p p= ( )0 1 2, , ,...., ,....i ?
∑ Quel est, en régime stationnaire, le nombre moyen de clients se trouvant dans
le système ?
∑ Quel est, en régime stationnaire, le nombre moyen de clients se trouvant dans
la file d’attente ?
B.A. Ferrif
24/07/01
180
∑ Quel est, en régime stationnaire, le temps moyen passé dans la file d’attente
par un client ?
5- ETUDE ASSISTEE PAR ORDINATEUR
On se trouve confronté au problème suivant :
Dans une station-service où les automobilistes arrivent suivant un processus de
Poisson non-homogène d’intensité l lt( ) ≥, 0 , il y a un seul pompiste. Lorsqu’un
automobiliste arrive, il est servi immédiatement par celui-ci s’il est libre, dans le
cas contraire, il gagne la file d’attente. Lorsque le pompiste a terminé un service
en cours, il traite le client qui a attendu le plus longtemps dans la file, s’il y a un
client ; s’il n’y a pas de client, le pompiste devient libre jusqu’à l’arrivée du
prochain véhicule. La durée du service d’un client est une variable aléatoire de loi
G. De plus, en fin de journée après l’heure T aucun automobiliste n’est admis
dans la station ; les clients se trouvant déjà dans le système seront servis. Nous
souhaitons maîtriser deux éléments :
-Le temps moyen passé par un client dans le système (afin de savoir s’il y a un
intérêt à avoir un second pompiste) ;
-L’heure moyenne de départ du dernier client, en d’autres termes l’heure de
départ du pompiste.
L’objet du travail est d’étudier ce problème, d’en décrire un modèle, de spécifier le
logiciel permettant de le simuler et d’obtenir la réponse aux questions posées et
B.A. Ferrif
24/07/01
181
éventuellement à d’autres qui n’ont pas été explicitées. Le test de validation sera
fait en prenant pour loi G une loi exponentielle.
B.A. Ferrif
24/07/01
182
Index
B.A. Ferrif
24/07/01
183
A
Accroissement stationnaire á 120,121,150
Accroissements indépendants á 120,121,126,143,150
Analyse et le traitement du signal á 22
Atteignabilité á 74
B
Bernoulli á 18,19,24,25,28,29,36,37,43,46,153
Biologie á 22
Borel á 19
Brown á 20
Bruit blanc á 45,50
C
Calcul Formel á 23
Cardano á 16
Chaîne de Markov á 56,59,85
Commande de processus á 22
Communication á 21,66,67,68
D
de Moivre á 18,19
Décomposition des chaînes á 86
Doob á 20
E
Economie á 22
Einstein á 20
Eléments d'histoire á 15
Equations d'Erlang á 123
Ergodicité á 51,84,93
Etat persistant á 76
Etat transitoire á 76,82,88,89,92
F
Feller á 18,20
Fermat á 17
Files d'attente á
25,32,53,92,131,152,153,154,155,157,158,159,162,16
3,164,165,168,169,170,171,173
Flip-Flop á 30,145,146
Fonction d’autocorrélation á 47,147
G
Galilée á 16
Galton á 19
Graphe á 61,107,108,132
H
Hilbert á 19
B.A. Ferrif
24/07/01
Homogénéité á 58
Huyghens á 17,18
I
Irréductibilité á 74
K
Képler á 16
Kolmogorov á 15,20,63
L
Lagrange á 19
Langevin á 21
Laplace á 19
Leibnitz á 15
Les Réseaux de Jackson á 170
Lévy á 20
Loi initiale á 65
M
Marche aléatoire á 57
Markov á
19,20,25,52,53,54,56,57,58,59,60,61,62,63,64,65,66,
7,68,69,70,71,72,76,78,79,83,84,85,86,87,88,89,90,9
,92,93,94,95,96,97,98,112,117,119,130,156,157
Martingale á 78
Mathématique á 15,17,21,22,23,179
Matrice fondamentale á 83
Modèle du serveur central á 173
184
Modélisation á 20,22,23,25,29,30,47,118,119,154
O
6
1
Optimisation á 33,41
Organisation des entreprises á 21
P
Paciuolo á 16
Parties fermées et parties absorbantes á 68
Pascal á 17,81
Périodicité des états á 72
Philosophie á 15,23,26
Poisson á
19,24,25,116,117,118,119,121,122,124,126,127,128,1
32,135,136,138,140,142,143,144,145,146,149,150,15
1,153,166,180
Probabilité d'atteinte á 71
Probabilité de transition á 58
Processus arborescents á 31
Processus de comptage á 119,127
Processus de Markov á 56
Processus de naissance et de disparition á 131,162
Processus de Poisson á 120
Processus de renouvellement á 116,138
Processus de Wiener á 45
Processus gaussien á 44
Processus homogène á 58
Processus stochastique á 30,34,44,45,120,131
B.A. Ferrif
24/07/01
185
R
Réseaux à commutation de paquets á 168
Réseaux de files d’attente á 168
Réseaux informatiques á 21
S
Santé publique á 21
Simulation á 22,23,25,29,45,47,48,118,150,177
T
Tartaglia á 16
Tchebychev á 19
Temps d’attente á 39,48
Temps d'atteinte á 71
Trajectoire ou réalisation du processus á 36
Transition d'ordre supérieur á 63
W
Wiener á 21,28,45,117
![Evaluation des options américaines [ATTALLAH Sabrina]](https://img.pdfslide.fr/doc/110x75/5571fab0497959916992d754/evaluation-des-options-americaines-attallah-sabrina.jpg)
