La simulation de Monte Carlo
274 pages
Français

La simulation de Monte Carlo

-

Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus
274 pages
Français
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Description

La simulation de Monte Carlo est un outil statistique puissant pour résoudre des problèmes mathématiques complexes ou plus exactement pour approcher leur solution aussi précisément que souhaité.
Cet ouvrage décrit les principaux problèmes auxquels s'attaque la simulation de Monte Carlo : calcul de sommes ou d'intégrales, d'espérances mathématiques, de problèmes d'optimisation, de résolution d'équations linéaires, intégrales ou différentielles. La simulation de Monte Carlo est illustré de nombreux exemples d'application issus de domaines aussi variés que les télécommunications, la finance, la fiabilité, la physique, etc. Il expose comment les solutions peuvent être approchées et l'erreur analysée via un intervalle de confiance contenant la solution avec une probabilité donnée.
Ce livre présente également les différentes techniques d'accélération réduisant l'intervalle de confiance pour un temps de simulation donné. D'autres questions fondamentales sont traitées comme la génération du hasard et des variables aléatoires ou la méthode de simulation de quasi-Monte Carlo qui utilise des suites non aléatoires mais mieux réparties sur le domaine d'échantillonnage, permettant une convergence plus rapide.
Avant-propos. Chapitre 1. Introduction et concepts de base. Chapitre 2. Génération de variables aléatoires. Chapitre 3. Transformation sous forme d'espérance mathématique. Chapitre 4. Analyse des résultats de simulation. Chapitre 5. Techniques de réduction de la variance. Chapitre 6. Simulation de Monte Carlo en optimisation. Chapitre 7. Méthodes de quasi-Monte Carlo. Annexes. Bibliographie. Index.

Sujets

Informations

Publié par
Date de parution 05 février 2010
Nombre de lectures 29
EAN13 9782746240841
Langue Français
Poids de l'ouvrage 3 Mo

Informations légales : prix de location à la page 0,06€. Cette information est donnée uniquement à titre indicatif conformément à la législation en vigueur.

Exrait




















La simulation de Monte Carlo



































' LAVOISIER, 2010
LAVOISIER
11, rue Lavoisier
75008 Paris

www.hermes-science.com
www.lavoisier.fr

ISBN 978-2-7462-2521-3
ISSN 1956-6808


Le Code de la propriØtØ intellectuelle n’autorisant, aux termes de l’article L. 122-5, d’une part,
que les "copies ou reproductions strictement rØservØes l’usage privØ du copiste et non
destinØes une utilisation collective" et, d’autre part, que les analyses et les courtes citations
dans un but d’exemple et d’illustration, "toute reprØsentation ou reproduction intØgrale, ou
partielle, faite sans le consentement de l’auteur ou de ses ayants droit ou ayants cause, est
illicite" (article L. 122-4). Cette reprØsentation ou reproduction, par quelque procØdØ que ce
soit, constituerait donc une contrefa on sanctio nnØe par les articles L. 335-2 et suivants du
Code de la propriØtØ intellectuelle.
Tous les noms de sociØtØs ou de produits citØs dans cet ouvrage sont utilisØs des fins
d identification et sont des marque s de leurs dØtenteurs respectifs.


Printed and bound in England by Antony Rowe Ltd, Chippenham, March 2010.





La simulation


de Monte Carlo












Bruno Tuffin















Collection MØthodes stochastiques appliquØes
SOUS LA DIRECTION DE NIKOLAOS LIMNIOS ET JACQUES JANSSEN


Fran ois B RUCKER et Jean-Pierre BARTH LEMY , ElØments de classification, 2007.

Thierry CHAUVEAU, L Øquilibre dun modŁle financier, 2004.

Arnaud CL MENT -GRANDCOURT et Jacques JANSSEN, MØthodes quantitatives en
gestion des risques financiers et papillons noirs, 2010.

Arnaud CL MENT -GRANDCOURT et Jacques JANSSEN, Gestion des risques financiers
et papillons noirs, 2010.

Olivier GAUDOUIN et James LEDOUX, ModØlisation alØatoire en fiabilitØ des
logiciels, 2007.

Faris HAMZA et Jacques JANSSEN, Choix optimal des actifs financiers et gestion
de portefeuille, 2008.

Marius IOSIFESCU, Nikolaos LIMNIOS et Gheorghe OPRISAN, ModŁles stochastiques,
2007.

Jacques JANSSEN et Raimondo MANCA, Outils de construction de modŁles internes
pour les assurances et les banques, 2009.

Mikhail NIKULIN, LØo GERVILLE-R ACHE et Vincent COUALLIER, Statistique des
essais accØlØrØs, 2007.

Odile PONS, Statistique de processus de renouvellement et markoviens, 2008.

Table des matières
Avant-propos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Chapitre1.Introductionetconceptsdebase . . . . . . . . . . . . . . . . . . 11
1.1. Modélisation mathématique et probabiliste . . . . . . . . . . . . . . . . 11
1.2. Simulation : définition et algorithme de base . . . . . . . . . . . . . . . 12
1.3. Pourquoi et quand utiliser la simulation de Monte Carlo ? . . . . . . . . 20
1.4. Exemples simples et illustratifs . . . . . . . . . . . . . . . . . . . . . . . 22
1.4.1. Aiguille de Buffon . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.4.2. Calcul d’une surface . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.4.3. Intégrale d’une fonction unidimensionnelle . . . . . . . . . . . . . 27
1.4.4. Simulation d’une file d’attente simple . . . . . . . . . . . . . . . . 30
1.5. Quelques exemples spécifiques dans des domaines d’application
importants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
1.5.1. Application en ingéniérie financière . . . . . . . . . . . . . . . . . 33
1.5.2. Application en télécommunications/fiabilité . . . . . . . . . . . . 34
1.5.3. Application en physique . . . . . . . . . . . . . . . . . . . . . . . 36
1.5.4. Application en biologie . . . . . . . . . . . . . . . . . . . . . . . . 36
1.6. Source d’aléatoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
Chapitre2.Générationdevariablesaléatoires . . . . . . . . . . . . . . . . . 39
2.1. Philosophie et objectifs . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.2. Génération d’une suite i.i.d. uniforme sur [0,1] . . . . . . . . . . . . . . 42
2.2.1. Générateurs congruentiels linéaires . . . . . . . . . . . . . . . . . 42
2.2.2. Problèmes rencontrés par les générateurs congruentiels linéaires . 44
2.2.3. Générateur MRG32k3a . . . . . . . . . . . . . . . . . . . . . . . . 46
2.2.4. Le générateur Mersenne-Twister . . . . . . . . . . . . . . . . . . . 47
2.2.5. Un générateur de flots . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.3. Génération de lois non uniformes . . . . . . . . . . . . . . . . . . . . . 50
56 La simulation de Monte Carlo
2.3.1. Génération d’une loi discrète . . . . . . . . . . . . . . . . . . . . . 50
2.3.2. Méthode d’alias . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.3.3. Transformation inverse pour une loi continue . . . . . . . . . . . . 54
2.3.4. Méthode de composition . . . . . . . . . . . . . . . . . . . . . . . 57
2.3.5. Méthode de la convolution . . . . . . . . . . . . . . . . . . . . . . 58
2.3.6. Méthode de rejet . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
2.3.7. Quelques méthodes pour des lois spécifiques . . . . . . . . . . . . 59
2.3.8. Génération de variables aléatoires dépendantes . . . . . . . . . . . 61
2.3.8.1. Echantillonnage conditionnel . . . . . . . . . . . . . . . . . . 61
2.3.8.2. Transformation linéaire . . . . . . . . . . . . . . . . . . . . . 62
2.3.8.3. Copules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
2.3.9. Algorithme de Metropolis . . . . . . . . . . . . . . . . . . . . . . . 64
2.4. Tests des générateurs pseudo-aléatoires . . . . . . . . . . . . . . . . . . 67
2.4.1. Test spectral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
22.4.2. Test duχ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
2.4.3. Test de Kolmogorov-Smirnov . . . . . . . . . . . . . . . . . . . . 73
Chapitre3.Transformationsousformed’espérancemathématique . . . . 77
3.1. Calcul de sommes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
3.1.1. Calcul d’une espérance mathématique sur une loi discrète . . . . 79
3.1.2. Calcul de sommes discrètes en général . . . . . . . . . . . . . . . 80
3.1.3. Illustration : estimation de constantes de normalisation dans les
réseaux de files d’attente . . . . . . . . . . . . . . . . . . . . . . . . 82
3.1.4. Illustration : tableaux de contingence . . . . . . . . . . . . . . . . 85
3.2. Calcul d’intégrales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.2.1. Calcul d’espérance mathématique de variable aléatoire de loi
continue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.2.2. Calcul d’intégrales . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
3.2.3. Calcul de surfaces ou volumes . . . . . . . . . . . . . . . . . . . . 89
3.3. Simulation d’une chaîne de Markov à temps discret . . . . . . . . . . . 91
3.4. Simulation d’une chaîne de Markov à temps continu . . . . . . . . . . 95
3.5. Méthode de Monte Carlo par chaîne de Markov (MCMC) . . . . . . . 101
3.6. Simulation d’un processus stochastique et des systèmes à événements
discrets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
3.7. Résolution d’un système d’équations linéaires . . . . . . . . . . . . . . 108
3.8. Résolution d’équations intégrales . . . . . . . . . . . . . . . . . . . . . 112
3.9. Résolution d’équations différentielles . . . . . . . . . . . . . . . . . . . 114
Chapitre4.Analysedesrésultatsdesimulation . . . . . . . . . . . . . . . . 117
4.1. Sur la vitesse de convergence du théorème central limite . . . . . . . . 119
4.2. Analyse des résultats pour une erreur absolue ou relative donnée . . . . 120
4.3. Intervalle de confiance pour un quotient ou une autre fonction régulière
d’estimateurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122Table des matières 7
4.4. Analyse des résultats pour les chaînes de Markov . . . . . . . . . . . . 128
4.4.1. Analyse des résultats pour les mesures transitoires . . . . . . . . . 129
4.4.2. Théorèmes limites centraux pour les chaînes de Markov . . . . . 130
4.4.3. Méthode de réplication/délétion . . . . . . . . . . . . . . . . . . . 132
4.4.4. Méthode régénérative . . . . . . . . . . . . . . . . . . . . . . . . . 132
4.4.5. Méthode Batch Means . . . . . . . . . . . . . . . . . . . . . . . . . 136
4.4.5.1. Nombre fixe de blocs . . . . . . . . . . . . . . . . . . . . . . 138
4.4.5.2. Règle SQRT (racine carrée) . . . . . . . . . . . . . . . . . . 138
4.4.5.3. Règle LBatch . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
4.4.5.4. Règle ABatch . . . . . . . . . . . . . . . . . . . . . . . . . . 140
4.4.5.5. Règle Skart . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
4.4.6. Méthode basée sur les séries temporelles . . . . . . . . . . . . . . 142
4.5. Méthode du bootstrap . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
4.6. Compromis variance/biais . . . . . . . . . . . . . . . . . . . . . . . . . . 144
4.7. Réduction du biais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
4.8. Simulation avec budget fini . . . . . . . . . . . . . . . . . . . . . . . . . 149
Chapitre5.Techniques deréductiondelavariance . . . . . . . . . . . . . . 151
5.1. Un cadre à l’accélération est nécessaire : simulation d’événements rares 151
5.2. Efficacité relative . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
5.3. Stratification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
5.4. Monte Carlo et espérance conditionnelle . . . . . . . . . . . . . . . . . 164
5.5. Variables antithétiques et corrélation négative . . . . . . . . . . . . . . 170
5.6. Variables de contrôle . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
5.7. Echantillonnage préférentiel . . . . . . . . . . . . . . . . . . . . . . . . 182
5.7.1. Formalisme général pour l’échantillonnage préférentiel . . . . . . 183
5.7.2. Changement de mesure optimal : estimateur à variance nulle et
approximations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
5.7.3. Echantillonnage préférentiel et chaînes de Markov à temps discret . 188
5.7.4. Echantillonnage préférentiel et chaînes de Markov à temps continu 193
Chapitre6.SimulationdeMonteCarloenoptimisation . . . . . . . . . . . 195
6.1. Introduction et classification des méthodes . . . . . . . . . . . . . . . . 195
6.2. Approximation stochastique . . . . . . . . . . . . . . . . . . . . . . . . 198
6.2.1. Estimationvia un échantillon de chemins . . . . . . . . . . . . . . 198
6.2.2. Méthodes itératives : description générale . . . . . . . . . . . . . . 199
6.2.3. Estimation du gradient . . . . . . . . . . . . . . . . . . . . . . . . 199
6.2.3.1. Différences finies . . . . . . . . . . . . . . . . . . . . . . . . 199
6.2.3.2. Analyse par perturbations infinitésimales . . . . . . . . . . . 201
6.2.3.3. Méthode du quotient de vraisemblance . . . . . . . . . . . . 202
6.2.4. Différents algorithmes d’approximation stochastique itérative . . 2038 La simulation de Monte Carlo
6.3. Méthodes d’exploration . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
6.3.1. Recuit simulé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
6.3.2. Algorithme génétique . . . . . . . . . . . . . . . . . . . . . . . . . 207
Chapitre7.Méthodesdequasi-MonteCarlo . . . . . . . . . . . . . . . . . . 211
7.1. Peut-on battre Monte Carlo ? . . . . . . . . . . . . . . . . . . . . . . . . 211
7.2. Mesures d’équidistribution, discrépance . . . . . . . . . . . . . . . . . . 213
7.3. Suites à discrépance faible . . . . . . . . . . . . . . . . . . . . . . . . . 216
7.3.1. Suites de Halton . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
7.3.2. Suites de Weyl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
7.3.3. (t,s)-suites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
7.3.4. Règles de quadrillage . . . . . . . . . . . . . . . . . . . . . . . . . 221
7.4. Borne de l’erreur et vitesse de convergence . . . . . . . . . . . . . . . . 222
7.5. Méthodes de quasi-Monte Carlo randomisées . . . . . . . . . . . . . . 234
7.5.1. Intérêt pratique des bornes de l’erreur pour les méthodes de
quasiMonte Carlo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
7.5.2. Différentes randomisations et convergence . . . . . . . . . . . . . 236
7.5.2.1. Suites à discrépance faible shiftées (aussi dites translatées) . 236
7.5.2.2. (t,s)-suites brouillées . . . . . . . . . . . . . . . . . . . . . . 242
7.5.2.3. Départ aléatoire des suites de Halton . . . . . . . . . . . . . 244
Annexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
A. Eléments de base en probabilité et statistiques . . . . . . . . . . . . . . . 247
A.1. Résultats généraux . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
A.2. Variables aléatoires discrètes . . . . . . . . . . . . . . . . . . . . . . 250
A.3. Variables aléatoires continues . . . . . . . . . . . . . . . . . . . . . 252
A.4. Convergences et théorèmes limites . . . . . . . . . . . . . . . . . . 254
A.5. Chaînes de Markov à temps discret . . . . . . . . . . . . . . . . . . 255
A.6. Chaînes de Markov à temps continu . . . . . . . . . . . . . . . . . 258
A.7. Mouvement Brownien . . . . . . . . . . . . . . . . . . . . . . . . . 260
B. Liste des principales notations mathématiques . . . . . . . . . . . . . . . 261
Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269Avant-propos
Simulation est un mot utilisé dans de nombreux cadres. Sa définition littérale est
donnée par « action de faire paraître comme réelle une chose qui ne l’est pas », ou
« imitation artificielle d’un dispositif ou d’un système ». La simulation d’un modèle
mathématique consiste à représenter un problème par un modèle abstrait que l’on
pourra ensuite analyser, sans devoir travailler sur un (coûteux) système réel.
L’objectif de ce livre est d’introduire la simulation dite de Monte Carlo qui
utilise des nombres aléatoires pour l’analyse du système considéré. Les modèles
probabilistes sont en effet souvent les rares, voire les seuls permettant de résoudre des
problèmes complexes. Le nom « Monte Carlo » a été introduit par Ulam et von
Neumann à Los Alamos pendant la seconde guerre mondiale, en référence aux jeux de
hasard dans les casinos. Les méthodes de Monte Carlo nécessitent en général une
grosse capacité de calcul et ont connu un développement important avec l’avènement
de l’informatique, mais sont d’un grande simplicité d’utilisation, tout du moins quand
elles sont mises en œuvre dans leur formulation la plus simple. Les différentes
questions que nous aborderons sont alors : comment générer des nombres aléatoires selon
des lois de probabilités spécifiées sur un ordinateur au comportement déterministe par
définition ? Comment analyser la validité de résultats différents pour différentes
réalisations aléatoires ? Comment obtenir une simulation plus efficace, c’est-à-dire
demandant moins de temps de calcul pour obtenir une précision donnée ? Notre objectif est
d’apporter des premières réponses à ces questions.
Ce livre s’adresse à un public souhaitant connaître les bases de la simulation de
Monte Carlo. Il requiert un minimum de connaissances (de niveau premier cycle
universitaire) en probabilité et statistique, même si l’on pourra trouver en annexes de
brefs rappels sur les bases nécessaires à sa compréhension. Il est un outil adapté pour
un cours de second cycle universitaire ou pour toute personne issue d’un des
nombreux domaines d’application, en physique, chimie, biologie, transport, finance,
informatique et télécommunications, souhaitant assimiler les méthodes de Monte Carlo
pour les appliquer.
910 La simulation de Monte Carlo
L’organisation du livre est la suivante : le chapitre 1 décrit les éléments de base
et les enjeux de la simulation de Monte Carlo. Les points importants y sont
abordés, notamment par l’intermédiaire d’exemples, pour inciter le lecteur à se référer aux
chapitres suivants pour plus de précision. Le chapitre 2 décrit comment le hasard est
généré (ou plutôt imité) sur un ordinateur, pour une loi uniforme tout d’abord, puis
pour n’importe quelle loi. Le chapitre 3 présente la méthode de calcul d’une
espérance mathématique, autrement dit d’une somme ou d’une intégrale. De nombreux
problèmes s’expriment sous cette forme, comme dans le cas de la simulation à
événements discrets, où l’on peut chercher à connaître le comportement moyen sur les
trajectoires possibles d’un processus. Nous décrirons également comment transformer, et
résoudre, des problèmes exprimés sous forme d’équations linéaires, intégrales ou
différentielles. Le chapitre 4 est l’un des plus importants, il expose comment certifier la
validité des résultats, en construisant un intervalle de confiance (probabiliste) pour la
valeur cherchée. Cela permet de quantifier l’erreur due à l’approximation. Nous
introduisons au chapitre 5 les techniques dites de réduction de la variance, qui permettent
une meilleure précision pour une taille d’échantillon (ou temps de simulation)
donnée, et donc une simulation plus efficace. L’optimisation est un type de problème qui
nécessite des mécanismes particuliers et sera traité au chapitre 6. Enfin, le chapitre 7
introduit les méthodes dites de quasi-Monte Carlo, analogue déterministe de Monte
Carlo permettant une convergence plus rapide par un positionnement approprié des
points de l’échantillon. Ce livre permettra donc d’aborder, ne serait-ce que
subrepticement, tous les aspects et tous les types d’application de la simulation de Monte
Carlo.
Je ne saurais terminer sans remercier Nikolaos Limnios, éditeur de la série pour
Hermès, pour sa confiance, ainsi que les relecteurs Patrick Maillé et Firmin Tuffin
pour leur travail et leur aide. Toute erreur restante est cependant mienne !
Bruno TuffinChapitre 1
Introduction et concepts de base
1.1. Modélisationmathématiqueetprobabiliste
L’évaluation des systèmes est un problème primordial, dans tous les domaines
scientifiques, qu’il s’agisse de calculer des sommes, des intégrales, ou encore de
résoudre des équations ou des problèmes d’optimisation. Une analyse fine des
problèmes permet en effet de comprendre, et par conséquent d’agir, pour améliorer le
fonctionnement des systèmes et mieux les contrôler. Ce type de démarche se retrouve
dans tous les domaines scientifiques, ainsi que dans la vie quotidienne. Une évaluation
peut permettre des gains financiers, voire même des gains en termes de vies humaines.
Ainsi, pour citer quelques exemples, en finance, où il est important de déterminer
quand lever une option sur un bien financier ; en assurance, où il faut déterminer les
risques pour évaluer le montant de la prime ; en biologie, pour étudier les dynamiques
intra et intercellulaires ; en physique nucléaire pour connaître la probabilité qu’une
particule traverse un écran ; en télécommunications pour déterminer la qualité de
service ; ou enfin en fiabilité pour déterminer la disponibilité d’un système ou son temps
moyen d’atteinte de la défaillance.
Une évaluation peut donc avoir plusieurs objectifs : comprendre le comportement
moyen du système ou dans le pire des cas, deux problèmes de nature différente qui,
mathématiquement, reviennent respectivement à étudier une moyenne mathématique
ou un maximum. On peut aussi s’intéresser à un quantile d’une distribution,
c’està-dire le seuil en dessous duquel, statistiquement, un certain pourcentage de valeurs
d’un échantillon se retrouvera.
Pour réaliser cette évaluation, on peut (parfois) construire le système réel et le
faire fonctionner. Cependant ceci s’avère la plupart du temps extrêmement coûteux.
Par exemple, quand un constructeur aérien met au point un nouvel avion, il revient
1112 La simulation de Monte Carlo
beaucoup trop cher de construire de multiples prototypes pour tester toutes les
configurations et innovations. La démarche à l’autre extrême est de se fier à l’intuition,
mais ceci peut s’avérer très dangereux car les systèmes sont trop complexes pour en
assimiler toutes les subtilités. Une solution intermédiaire est de construire un
modèle abstrait que l’on pourra étudier mathématiquement, sur un ordinateur lorsque le
nombre d’opérations à réaliser est très important. Le coût associé est donc dès lors
limité et mieux contrôlé.
Une nouvelle question est alors le niveau de détail du modèle représentant le
système. Une représentation très fine permet une adéquation très précise entre le modèle
et le système réel, mais la complexité du modèle est alors bien souvent telle que peu
de méthodes existent pour son analyse, et ces méthodes requièrent un temps de calcul
très important. D’un autre côté, une représentation grossière permet une analyse très
simple et rapide, mais livre des résultats qui peuvent être très éloignés de la réalité. Il
faut donc faire un compromis entre modélisation fine et facilité d’analyse.
Réaliser une telle analyse est pertinent à plusieurs moments : à la création du
système afin d’être le plus performant possible, mais aussi au cours de sa vie, pour le
faire évoluer et l’améliorer. Les contraintes de coût sont alors différentes car il faut
tenir compte de l’existant, mais aussi de la connaissance de l’évolution de
l’environnement.
La méthode la plus développée est certainement la simulation de Monte Carlo
en raison de sa facilité de mise en œuvre et du peu de contraintes nécessaires sur le
modèle représenté. Cependant, les utilisateurs se plaignent souvent de sa lenteur, mais
ceci provient souvent d’une application très (trop) basique alors qu’il est possible d’en
améliorer l’efficacité comme nous le verrons au cours de ce livre.
1.2. Simulation:définitionetalgorithmedebase
La simulation en général représente le fait de faire des calculs sur un modèle
représentant un système réel, sans avoir à faire fonctionner celui-ci. La notion decalcul
numérique est ici importante, même s’il n’existe pas de consensus sur la définiton de
la simulation.
DÉFINITION 1.1.–
UnesimulationutilisantdesnombresaléatoiresestappeléesimulationdeMonteCarlo.
La simulation de Monte Carlo peut donc être vue comme une méthode
d’approximation statistique par opposition à l’analyse numérique classique, qui n’utilise pas le
hasard. On peut aussi remarquer que des méthodes utilisant le hasard permettent aussi
de résoudre d’autres types de problèmes, mais qui ne sont pas focalisés sur le principe
du calcul numérique, comme par exemple le tri d’un vecteur. Nous ne traiterons pasIntroduction et concepts de base 13
ce type de problème, plutôt appelé algorithme probabiliste que simulation de Monte
Carlo.
On peut aussi différencier deux types de modèles de simulation :
a) la simulation statique, pour laquelle il s’agit de représenter un système à un
instant particulier, cas relativement rare qui nécessite de supposer connus tous les
phénomènes relatifs à cet instant donné ;
b) la simulationdynamique, pour laquelle il s’agit d’étudier l’évolution au cours du
temps d’un modèle.
Pour situer le problème, considérons le cas où l’on cherche à estimer l’espérance
mathématique E[X] (inconnue) d’une variable aléatoire X représentant une mesure
sur un système évoluant selon une loi de probabilité P. Le principe de base de la
simulation de Monte Carlo consiste à considérern réalisations deX, que nous noterons
X pour 1≤i≤n, et estimerµ =E[X] par la moyenne desn observationsi
n1
¯X = X.n i∑
n i=1
Nous supposerons ici que lesX sont des variables aléatoires indépendantes, le casi
¯de variables dépendantes sera traité plus tard (voir chapitre 4). L’estimateurX vérifien
une propriété importante, il est dit sansbiais.
¯DÉFINITION 1.2.– Un estimateur X d’une quantitéµ est dit sans biais si son espé-n
¯ranceE[X ] estµ.Il est ditbiaisésinon. En effetn
" #
n1¯E[X ] = E Xn i∑n
i=1
n1
= E[X]i∑
n i=1
n1
= E[X]∑
n i=1
= E[X].
En pratique, il est important de noter qu’il suffit d’effectuer une boucle de 1 à
n sur les différentes estimations sans retenir les valeurs successives obtenues, mais
uniquement leur somme, X , mise à jour à chaque itération.∑i i14 La simulation de Monte Carlo
Le principe de la simulation de Monte Carlo est d’utiliser une taillen d’échantillon
suffisament grande pour avoir une estimation satisfaisante. En effet, selon la loi forte
des grands nombres (voir l’annexe pour des rappels de probabilités et statistiques),
nous savons que
¯X →µ quandn→∞.n
Cependant, du fait de la nature aléatoire de la méthode, deux réalisations
indépendantes vont produire deux échantillons différents et donc deux résultats différents. Il
est donc nécessaire et important de caractériser l’erreur d’approximation. Cette
caractérisation se fait en général via le théorème central limite ou ses variantes. Nous
rappelons ici ce théorème qui est la clé principale des méthodes de Monte Carlo et
expliquons ensuite son utilisation.
THÉORÈME 1.1.– Soit (X) une suite de variables aléatoires indépendantes eti i≥1
1 n2 ¯identiquement distribuées (i.i.d.) d’espéranceµ et de varianceσ , et X = X∑n ii=1n
unestimateurdeµ.Alorsla variablealéatoire
¯X −µn

σ/ n
convergeenloi versuneloinormalecentréeréduite,c’est-à-diredemoyennenulleet
variance1,N(0,1), quandntendversl’infini.
Comment utiliser ce théorème pour estimer l’erreur ? La loi normale (d’une
variable aléatoire N) est une loi connue et très étudiée. Il n’existe cependant pas de
formule explicite pour sa fonction de répartition, c’est-à-dire la probabilité
Z u 1 2−x /2√P[N≤u]= e dx.
∞ 2π
Les valeurs sont soit disponibles dans des bibliothèques de la plupart des logiciels
scientifiques ou via des tables dans tout livre de base en statistique. Le tableau 1.1
donne les différentes valeurs de la fonction de répartition. Pour lire une valeur dans
le tableau, on regarde séparément la valeur des unités et première décimale de u, qui
détermine la ligne, de la seconde décimale qui détermine la colonne. La valeur de
P[N≤ u] est déterminée par la case correspondant à cette ligne et cette colonne. A
titre d’exemple, pour u = 2,94= 2,9+ 0,04, on regarde la valeur correspondant à la
ligne 2,9 et colonne 0,04, ce qui donne 0,99836. Pour une valeur intermédiaire à plus
de deux décimales, on peut considérer comme première approximation le barycentre
correspondant entre deux valeurs deP[N≤u].
Pour les valeurs négatives de u, on utilise la symétrie de la loi normale, de sorte
que
P[N≤−u]=P[N≥u]= 1−P[N≤u]. (1.1)Introduction et concepts de base 15
u 0,00 0,01 0,02 0,03 0,04 0,05 0,06 0,07 0,08 0,09
0,0 0,50000 0,50399 0,50798 0,51197 0,51595 0,51994 0,52392 0,52790 0,53188 0,53586
0,1 0,53983 0,54380 0,54776 0,55172 0,55567 0,55962 0,56356 0,56749 0,57142 0,57535
0,2 0,57926 0,58317 0,58706 0,59095 0,59483 0,59871 0,60257 0,60642 0,61026 0,61409
0,3 0,61791 0,62172 0,62552 0,62930 0,63307 0,63683 0,64058 0,64431 0,64803 0,65173
0,4 0,65542 0,65910 0,66276 0,66640 0,67003 0,67364 0,67724 0,68082 0,68439 0,68793
0,5 0,69146 0,69497 0,69847 0,70194 0,70540 0,70884 0,71226 0,71566 0,71904 0,72240
0,6 0,72575 0,72907 0,73237 0,73565 0,73891 0,74215 0,74537 0,74857 0,75175 0,75490
0,7 0,75804 0,76115 0,76424 0,76730 0,77035 0,77337 0,77637 0,77935 0,78230 0,78524
0,8 0,78814 0,79103 0,79389 0,79673 0,79955 0,80234 0,80511 0,80785 0,81057 0,81327
0,9 0,81594 0,81859 0,82121 0,82381 0,82639 0,82894 0,85543 0,85769 0,85993 0,86214
1,1 0,86433 0,86650 0,86864 0,87076 0,87286 0,87493 0,87698 0,87900 0,88100 0,88298
1,2 0,88493 0,88686 0,88877 0,89065 0,89251 0,89435 0,89617 0,89796 0,89973 0,90147
1,3 0,90320 0,90490 0,90658 0,90824 0,90988 0,91149 0,91309 0,91466 0,91621 0,91774
1,4 0,91924 0,92073 0,92220 0,92364 0,92507 0,92647 0,92785 0,92922 0,93056 0,93189
1,5 0,93319 0,93448 0,93574 0,93699 0,93822 0,93943 0,94062 0,94179 0,94295 0,94408
1,6 0,94520 0,94630 0,94738 0,94845 0,94950 0,95053 0,95154 0,95254 0,95352 0,95449
1,7 0,95543 0,95637 0,95728 0,95818 0,95907 0,95994 0,96080 0,96164 0,96246 0,96327
1,8 0,96407 0,96485 0,96562 0,96638 0,96712 0,96784 0,96856 0,96926 0,96995 0,97062
1,9 0,97128 0,97193 0,97257 0,97320 0,97381 0,97441 0,97500 0,97558 0,97615 0,97670
2,0 0,97725 0,97778 0,97831 0,97882 0,97932 0,97982 0,98030 0,98077 0,98124 0,98169
2,1 0,98214 0,98257 0,98300 0,98341 0,98382 0,98422 0,98461 0,98500 0,98537 0,98574
2,2 0,98610 0,98645 0,98679 0,98713 0,98745 0,98778 0,98809 0,98840 0,98870 0,98899
2,3 0,98928 0,98956 0,98983 0,99010 0,99036 0,99061 0,99086 0,99111 0,99134 0,99158
2,4 0,99180 0,99202 0,99224 0,99245 0,99266 0,99286 0,99305 0,99324 0,99343 0,99361
2,5 0,99379 0,99396 0,99413 0,99430 0,99446 0,99461 0,99477 0,99492 0,99506 0,99520
2,6 0,99534 0,99547 0,99560 0,99573 0,99585 0,99598 0,99609 0,99621 0,99632 0,99643
2,7 0,99653 0,99664 0,99674 0,99683 0,99693 0,99702 0,99711 0,99720 0,99728 0,99736
2,8 0,99744 0,99752 0,99760 0,99767 0,99774 0,99781 0,99788 0,99795 0,99801 0,99807
2,9 0,99813 0,99819 0,99825 0,99831 0,99836 0,99841 0,99846 0,99851 0,99856 0,99861
3,0 0,99865 0,99869 0,99874 0,99878 0,99882 0,99886 0,99889 0,99893 0,99896 0,99900
3,1 0,99903 0,99906 0,99910 0,99913 0,99916 0,99918 0,99921 0,99924 0,99926 0,99929
3,2 0,99931 0,99934 0,99936 0,99938 0,99940 0,99942 0,99944 0,99946 0,99948 0,99950
3,3 0,99952 0,99953 0,99955 0,99957 0,99958 0,99960 0,99961 0,99962 0,99964 0,99965
3,4 0,99966 0,99968 0,99969 0,99970 0,99971 0,99972 0,99973 0,99974 0,99975 0,99976
3,5 0,99977 0,99978 0,99978 0,99979 0,99980 0,99981 0,99981 0,99982 0,99983 0,99983
3,6 0,99984 0,99985 0,99985 0,99986 0,99986 0,99987 0,99987 0,99988 0,99988 0,99989
3,7 0,99989 0,99990 0,99990 0,99990 0,99991 0,99991 0,99992 0,99992 0,99992 0,99992
3,8 0,99993 0,99993 0,99993 0,99994 0,99994 0,99994 0,99994 0,99995 0,99995 0,99995
3,9 0,99995 0,99995 0,99996 0,99996 0,99996 0,99996 0,99996 0,99996 0,99997 0,99997
Tableau1.1. Fonction de répartitionde laloi normale centrée réduite :
probabilité de trouver une valeur inférieure àu, oùuest lasomme des valeurs
ligne plus colonne16 La simulation de Monte Carlo
Réciproquement, pour une valeur de la fonction de répartition, on peut déterminer
la valeur de u correspondante; il suffit de trouver la valeur dans le tableau et sommer
les valeurs correspondantes de la ligne et de la colonne. Par exemple P[N≤ u] =
0,62172 se retrouve à la ligne 0,3 et colonne 0,01 et correspond donc à u= 0,31.
On peut aussi connaître la valeur du réelc tel queP[|N|≤c ]= 1−α en utilisantα α
la symétrie de la loi normale. Ainsi
P[|N|≤c ] = P[−c ≤N≤c ]α α α
= P[N≤c ]−P[N≤−c ]α α
= 2P[N≤c ]− 1,α
où la dernière égalité est obtenue grâce à (1.1). Une valeur couramment utilisée est
1−α = 95 %. Nous avons alors 0,95= 2P[N≤c ]− 1, c’est-à-direP[N≤c ]=0,05 0,05
0,975, qui donne c = 1,96 dans le tableau 1.1. Toute autre valeur peut être déter-0,05
minée de manière similaire.
Le théorème central limite nous donne
" #
¯X −µn
P −c ≤ ≤c ≈P[|N|≤c ]α α ασ√
n
c’est-à-dire
σ σ
¯ ¯P X −c √ ≤µ≤X +c √ ≈ 1−α.n α n α
n n
On a donc un intervalle de confiance pourµ au niveau de confiance 1−α (pourn
assez grand, afin de vérifier l’approximation de la loi normale dans le théorème de la
limite centrale)
σ σ
¯ ¯X −c √ ,X +c √ . (1.2)n α n α
n n
Nous avons décrit ici comment obtenir un intervalle de confiance centré. En
général, une méthode de Monte Carlo fournira donc systématiquement une réponse
statistique du type « la valeur cherchée µ se trouve avec une certaine probabilité dans
un intervalle (dit de confiance) [I , I ] ». Nous n’avons donc pas la certitude d’être1 2
dans l’intervalle : si l’on réalise de manière indépendante m telles expériences
(chacune avec un échantillon de taillen), dansmα cas en moyenne la valeurµ ne sera pas
inclue dans l’intervalle. On peut augmenter 1−α pour réduire le problème, mais ceci
augmente également c et donc la taille de l’intervalle. Ceci est d’ailleurs logique :α
pour augmenter la confiance, il faut prendre un intervalle plus grand.6
Introduction et concepts de base 17
Dans la formule (1.2) de l’intervalle de confiance, n et c sont des données alorsα
2¯queX est obtenu par estimation. Cependant, la varianceσ est dans la plupart des casn
inconnue. Ainsi, pour obtenir en pratique un intervalle de confiance, il faut l’estimer.
Or, un estimateur sans biais de la variance est
n n1 1 n2 2 2 2¯ ¯S = (X−X ) = X − (X ) . (1.3)i n nn ∑ ∑ i
n− 1 n− 1 n− 1i=1 i=1
Cet estimateur a un coût négligeable, car pour l’obtenir, il suffit de maintenir deux
2compteurs, celui de X et celui de X , mis à jour à chaque étape, sans nécessité∑ ∑i i ii
donc de mémoriser l’historique des valeurs(X) . Le fait de diviser parn− 1 au lieui i≥1
¯de n vient de l’estimation deµ par X , qui fait perdre un degré de liberté. On peut enn
effet montrer l’absence de biais :
n1 n2 2 2¯E[S ] = E[X ]− E[(X ) ]nn ∑ i
n− 1 n− 1i=1
" !#
n nn n 12 2= E[X ]− E X + XXi j∑ i ∑∑2n− 1 n− 1 n
i=1 i=1 j=i
n 12 2 2= E[X ]− (nE[X ]+n(n− 1)E[X] )
n− 1 n(n− 1)
2 2= E[X ]−E[X] .
2On retrouve bien la définition de la varianceσ .
On peut également montrer que la loi de la variable
¯√ X −µn
n
Sn
converge vers une loi normale centrée réduite. Les mêmes techniques que dans le cas
où la variance est connue peuvent ainsi être utilisées pour obtenir un intervalle de
confiance
S Sn n¯ ¯√ √X −c ,X +c (1.4)n α n α
n n
au niveau de confiance 1−α, en remplaçant cette variance par son estimation.
Quand la taille n de l’échantillon est petite, on utilise une version plus
conservative (avec une meilleure couverture de l’intervalle de confiance) du théorème central
limite. On peut en effet prouver le résultat classique statistique suivant.18 La simulation de Monte Carlo
THÉORÈME 1.2.– Si lesX sont indépendantset normalementdistribués, la variablei
√ ¯X−µnn suit uneloideStudentàn− 1degrésdeliberté.Sn
Ce résultat n’est pas en contradiction avec le théorème central limite, car quand
→∞, la loi de Student à n− 1 degrés de liberté correspond à une loi normale
centrée réduite. Il est cependant conseillé pour n petit ou de taille modérée de remplacer
l’intervalle de confiance (1.4) par

S Sn n¯ ¯X −t √ ,X +t √ (1.5)n nα,n−1 α,n−1
n n
au niveau de confiance 1−α, où t est le 1−α/2 quantile de la loi de Studentα,n−1
à n− 1 degrés de liberté. Pour déterminer le quantile de la loi de Student, on peut
également utiliser le tableau 1.2, où la ligne correspond au nombre m de degrés de
liberté et la colonne à la probabilité 1−α/2 souhaitée pour le quantile. Pour des
valeurs grandes dem, ceci revient à se reporter à la table de la loi normale. Les valeurs
sont plus conservatives, dans le sens où le quantile pour une même probabilité est
plus grand pour la loi de Student, résultant également en un intervalle de confiance
plus grand. Pour un intervalle à 95 %, on cherche le 1−α/2= 97,5 % quantile. Pour
m =∞, on retrouve par exemple la valeur 1,96 de la loi normale (dernière ligne du
tableau).
La simulation de Monte Carlo basique peut donc être résumée par l’algorithme
suivant :
Initialisation :
—– sum← 0
—– sum2← 0
Pouri de 1 àn :
—– GénérerXi
—– sum = sum + Xi
—– sum2 = sum2 + X×Xi i
Estimation de la moyenne : sum/n
Estimation de la variance : sum2/(n− 1)- (sum/n)*sum/(n− 1)
Sortie de l’intervalle de confiance selon (1.4) ou (1.5).
On peut remarquer que siX est une fonction indicatrice,X =1(·) etP[X = 1]= p,i
n¯nX = X est une somme de variables de Bernoulli indépendantes et de paramètre∑n ii=1
¯p, suit donc une loi binomiale de paramètre (n,p). Alors la variance de X est p(1−n
¯ ¯p)/n et peut être estimée parX (1−X )/(n− 1) sans nécessité d’utiliser un compteurn n
n 2pour calculer la somme des carrés X . En effet, cette variance est estimée par∑i=1 iIntroduction et concepts de base 19
1−α/2 75 % 80 % 85 % 90 % 95 % 97,5 % 99 % 99,5 % 99,75 % 99,9 % 99,95 %
1 1,000 1,376 1,963 3,078 6,314 12,71 31,82 63,66 127,3 318,3 636,6
2 0,816 1,061 1,386 1,886 2,920 4,303 6,965 9,925 14,09 22,33 31,60
3 0,765 0,978 1,250 1,638 2,353 3,182 4,541 5,841 7,453 10,21 12,92
4 0,741 0,941 1,190 1,533 2,132 2,776 3,747 4,604 5,598 7,173 8,610
5 0,727 0,920 1,156 1,476 2,015 2,571 3,365 4,032 4,773 5,893 6,869
6 0,718 0,906 1,134 1,440 1,943 2,447 3,143 3,707 4,317 5,208 5,959
7 0,711 0,896 1,119 1,415 1,895 2,365 2,998 3,499 4,029 4,785 5,408
8 0,706 0,889 1,108 1,397 1,860 2,306 2,896 3,355 3,833 4,501 5,041
9 0,703 0,883 1,100 1,383 1,833 2,262 2,821 3,250 3,690 4,297 4,781
10 0,700 0,879 1,093 1,372 1,812 2,228 2,764 3,169 3,581 4,144 4,587
11 0,697 0,876 1,088 1,363 1,796 2,201 2,718 3,106 3,497 4,025 4,437
12 0,695 0,873 1,083 1,356 1,782 2,179 2,681 3,055 3,428 3,930 4,318
13 0,694 0,870 1,079 1,350 1,771 2,160 2,650 3,012 3,372 3,852 4,221
14 0,692 0,868 1,076 1,345 1,761 2,145 2,624 2,977 3,326 3,787 4,140
15 0,691 0,866 1,074 1,341 1,753 2,131 2,602 2,947 3,286 3,733 4,073
16 0,690 0,865 1,071 1,337 1,746 2,120 2,583 2,921 3,252 3,686 4,015
17 0,689 0,863 1,069 1,333 1,740 2,110 2,567 2,898 3,222 3,646 3,965
18 0,688 0,862 1,067 1,330 1,734 2,101 2,552 2,878 3,197 3,610 3,922
19 0,688 0,861 1,066 1,328 1,729 2,093 2,539 2,861 3,174 3,579 3,883
20 0,687 0,860 1,064 1,325 1,725 2,086 2,528 2,845 3,153 3,552 3,850
21 0,686 0,859 1,063 1,323 1,721 2,080 2,518 2,831 3,135 3,527 3,819
22 0,686 0,858 1,061 1,321 1,717 2,074 2,508 2,819 3,119 3,505 3,792
23 0,685 0,858 1,060 1,319 1,714 2,069 2,500 2,807 3,104 3,485 3,767
24 0,685 0,857 1,059 1,318 1,711 2,064 2,492 2,797 3,091 3,467 3,745
25 0,684 0,856 1,058 1,316 1,708 2,060 2,485 2,787 3,078 3,450 3,725
26 0,684 0,856 1,058 1,315 1,706 2,056 2,479 2,779 3,067 3,435 3,707
27 0,684 0,855 1,057 1,314 1,703 2,052 2,473 2,771 3,057 3,421 3,690
28 0,683 0,855 1,056 1,313 1,701 2,048 2,467 2,763 3,047 3,408 3,674
29 0,683 0,854 1,055 1,311 1,699 2,045 2,462 2,756 3,038 3,396 3,659
30 0,683 0,854 1,055 1,310 1,697 2,042 2,457 2,750 3,030 3,385 3,646
40 0,681 0,851 1,050 1,303 1,684 2,021 2,423 2,704 2,971 3,307 3,551
50 0,679 0,849 1,047 1,299 1,676 2,009 2,403 2,678 2,937 3,261 3,496
60 0,679 0,848 1,045 1,296 1,671 2,000 2,390 2,660 2,915 3,232 3,460
80 0,678 0,846 1,043 1,292 1,664 1,990 2,374 2,639 2,887 3,195 3,416
100 0,677 0,845 1,042 1,290 1,660 1,984 2,364 2,626 2,871 3,174 3,390
120 0,677 0,845 1,041 1,289 1,658 1,980 2,358 2,617 2,860 3,160 3,373
∞ 0,674 0,842 1,036 1,282 1,645 1,960 2,326 2,576 2,807 3,090 3,291
Tableau1.2. Table pour laloi de Student. Laligne correspond au nombre m
de degrés de liberté,lacolonne àlaprobabilitéβ = 1−α/220 La simulation de Monte Carlo
2S /n, maisn
n1 n2 2 2¯S = X − (X )nn ∑ i
n− 1 n− 1i=1
n1 n 2¯= X− (X )i n∑
n− 1 n− 1i=1
n n 2¯ ¯= X − (X )n n
n− 1 n− 1
¯ ¯nX (1−X )n n
= (1.6)
n− 1
2où l’on a utilisé X = X car X ∈{0,1}. Un intervalle de confiance au niveau dei ii
confiance 1−α pourµ est donc
 s s
¯ ¯ ¯ ¯X (1−X ) X (1−X )n n n n ¯ ¯ X −c ,X +c .n α n α
n− 1 n− 1
1.3. PourquoietquandutiliserlasimulationdeMonteCarlo?
La question qui se pose est donc pourquoi et quand utiliser la simulation de Monte
Carlo par rapport à l’éventail existant de techniques d’analyse numérique classique.
Le premier avantage de Monte Carlo est le petit nombre d’hypothèses nécessaires
pour son application. La loi forte des grands nombres implique la convergence de la
méthode (sous la condition que l’espérance mathématique cherchée est finie). D’un
autre côté, les techniques d’analyse numérique classiques requièrent des hypothèses
fortes sur le modèle, en termes de régularité, qui ne sont souvent pas vérifiées. La
raison d’être de la simulation vient donc de notre incapacité à traiter analytiquement
une multitude de modèles.
Un autre avantage est la simplicité d’obtention d’une estimation de l’erreur, via
un intervalle de confiance (1.4), alors que l’analyse numérique produit difficilement et
rarement une borne utilisable. Pour obtenir une borne de l’erreur, le théorème central
limite demande juste à avoir un second moment fini (bien que cette hypothèse et
l’utilisation du théorème central limite puissent être relaxées par des techniques de type
bootstrap ; voir le chapitre 4).
Enfin, pour beaucoup de problèmes complexes, nous devons considérer des
fonctions à plusieurs dizaines ou plusieurs centaines de variables. Dans ce cas, la
simulation de Monte Carlo devient le seul outil capable de donner une réponse en un tempsIntroduction et concepts de base 21
raisonnable. En effet, étudions la vitesse de convergence de la méthode de Monte
Carlo. L’intervalle de confiance (1.2) (ou sa variante (1.4)) a une demi-largeur
σ
c √ ,α
n
¯correspondant à l’écart entre l’estimationX et une borne extrême de l’intervalle. Cetten
demi-largeur mesure la valeur pour laquelle l’erreur absolue est plus petite avec une

probabilité 1−α. On a donc une décroissance en 1/ n en considérant un échantillon
den points. La vitesse de convergence est donc indépendante de la dimension
mathématique du problème considéré, c’est-à-dire du nombre de variables nécessaires pour
générer un des points de l’échantillon. La dimension peut se retrouver dans
l’expres√
sion de la constanteσ, mais pas la vitesse 1/ n.
Cette propriété est particulièrement remarquable comparée aux techniques
classiques d’analyse numérique. Ces techniques sont connues pour converger plus
rapidement, mais uniquement pour des dimensions relativement petites. On peut par exemple
donner les vitesses de convergence pour les règles de quadrature connues pour le cal-R
cul d’intégrales en dimension d, f(x)dx. Le tableau 1.3 décrit ces vitesses. Ond[0,1]
peut noter en dimension 1 la convergence bien plus rapide de la règle de Simpson par
−4 −1/2exemple (enO(n ) comparé àO(n ) pour la simulation de Monte Carlo).
Cependant, dès que la dimension augmente autour de la dizaine, ces règles deviennent très
lentes et la méthode de Monte Carlo devient clairement la plus efficace.
Méthode Vitesse
−2/dRègle trapézoïdale n
−4/dRègle de Simpson n
−(2m−1)/dRègle de Gauss (à m points) n
−1/2Monte Carlo n
Tableau1.3. Vitessede convergence pour diverses règles de quadrature et
pour laméthode de Monte Carlo, endimension d eten utilisantnpoints
Notre but n’est pas ici d’expliquer ces méthodes d’analyse numérique, le lecteur
peut se référer entre autres à [SCH 91, THE 89]. Nous pouvons cependant donner
quelques éléments sur les raisons de la dégradation de la vitesse avec la dimension d
R
pour le calcul d’une intégrale multidimensionnelle f , f(x)dx. Si l’on considèred[0,1]
un quadrillage régulier avec uniquement deux valeurs, disons 1/4 et 3/4, pour chaque
d dcoordonnéex dex=(x ,...,x )∈[0,1] , on doit alors considérer 2 points pour obte-i 1 d
nir le quadrillage complet, ce qui est difficilement réalisable pour des problèmes dont
50 15la dimension est grande. Par exemple sid= 50, cela donne 2 ≥ 10 points, rarement
envisageable. On voit ici que le nombre de points augmente exponentiellement avec la
dimension. Deux valeurs par coordonnée est de plus particulièrement peu, et prendre22 La simulation de Monte Carlo
Figure1.1. Quadrillage régulier àhuit points endimension d = 3
une valeur supérieure augmente encore considérablement le nombre de points. Une
autre explication intuitive de l’inefficacité de ce quadrillage est la suivante.
Considédrons encore un quadrillage à 2 points considérant les valeurs 1/4 et 3/4 pour chaque
coordonnée. La figure 1.1 illustre ce quadrillage en dimensiond= 3. Si l’on considère
la projection de ce quadrillage sur un groupe de deux coordonnées sur la figure 1.2,
2on peut s’apercevoir que cela ramène à 2 points car il existe toujours deux points qui
ont la même projection. La même chose se produit à chaque fois que l’on projette sur
une dimension inférieure. Ici, quatre des huit points ont la projection 1/4 sur chaque
coordonnée, et quatre la projection 3/4. Cela signifie que l’on échantillonne peu les
projections sur les différentes coordonnées ou groupes de coordonnées, introduisant
une certaine inefficacité. Remarquons cependant que des règles déterministes plus
efficaces pour l’analyse numérique (et pour le quadrillage) seront décrites au chapitre 7,
et sont appelées les méthodes de quasi-Monte Carlo.
1.4. Exemplessimplesetillustratifs
Au cours de cette section, nous illustrons la simulation de Monte Carlo sur trois
exemples différents : le problème historique de l’aiguille de Buffon, un problème
d’intégration unidimensionnelle (mais le calcul d’intégrales multiples peut être
réalisé exactement de la même manière) et la simulation d’un processus, ici d’une file
d’attente.Introduction et concepts de base 23
Figure1.2. Quadrillage régulier endimension d = 2
Y
AngleΘ
Figure1.3. Problème de l’aiguille de Buffon
1.4.1. AiguilledeBuffon
Le problème de l’aiguille de Buffon est un problème historique des méthodes de
Monte Carlo. Il date de 1777, bien avant l’avènement des ordinateurs. L’objectif est de
donner (de manière pratique) une valeur approchée deπ : on jette plusieurs fois une
aiguille de longueur 2l sur un sol (parquet) formé de lattes parallèles qui créent des
bandes de largeur 2a avec l≤a. La figure 1.3 illustre le problème. L’aiguille est
lancée aléatoirement sur le sol. SoitY la variable aléatoire donnant la distance du milieu
de l’aiguille à la rainure la plus proche. Si l’aiguille est lancée uniformément,Y est
une variable aléatoire uniforme sur l’intervalle[0,a]. De même,Θ, définissant l’angle
formé entre la rainure et l’aiguille, est aussi une variable aléatoire uniforme sur
l’intervalle [0,π], indépendante deY car si le jet est bien réalisé, l’angle est indépendant
de la distance à la rainure.
L’aiguille coupe une rainure siY <l sinΘ. On pose donc
X =1(Y <l sinΘ),6
24 La simulation de Monte Carlo
la fonction 1(·) étant la fonction indicatrice valant 1 si l’événement est vérifié, et 0
sinon. On a
E[X]=P[X = 1] = P[Y <l sinΘ]
Z π 1
= P[Y <l sinθ] dθ
π0
Z Zπ a 1 1
= 1(y<l sinθ) dy dθ
a π0 0
Z π l 1
= sinθ dθ
a π0
2l
= .

On considère doncn expériences indépendantesX (1≤i≤n), à partir desquellesi
n∑ Xi 2li=1¯ ¯on calculeX = . CommeE[X ]= , un estimateur deπ estn nn aπ
2l
.
¯aXn
Malheureusement cet estimateur deπ présente quelques complications :
2l– il est tout d’abord biaisé, c’est-à-direE[ ]=π : en général, pour une fonction¯aXn
g et une variable aléatoireX d’espéranceµ,g(X) n’a pas pour espéranceg(µ) ;
– obtenir un intervalle de confiance est aussi plus compliqué. On ne peut ici utiliser
¯ ¯la formule (1.4) car l’estimateur est une fonction de X et non X lui-même. On peutn n
cependant obtenir un intervalle de confiance pour un quotient, nous décrirons une telle
méthode au chapitre 4. On pourra y voir qu’un intervalle de confiance pour π (sans
tenir compte du biais) au niveau de confiance 1−α est

2l 2l S 2l 2l Sn n
−c √ ; +c √ ,α α2 2¯ ¯ ¯ ¯aX a (X ) n aX a (X ) nn n n n
S étant l’estimateur de l’écart-type desX .n i
Pour illustrer numériquement la convergence, nous donnons dans le tableau 1.4
une idée de la convergence de l’algorithme pour différentes tailles d’échantillon (testé
informatiquement) avec 2l=a. On peut observer qu’il faut un nombre important
d’essais pour avoir une estimation précise.
Estimerπ peut cependant être réalisé autrement, en estimant la surface d’un cercle
de rayon unité. Plus généralement, on peut calculer n’importe quelle surface par Monte
Carlo comme décrit dans ce qui suit.Introduction et concepts de base 25
n estimation intervalle de confiance
210 3,0303 [2,1797 ; 3,8809]
310 3,2258 [2.9274 ; 3,5242]
410 3,1046 [3,0163 ; 3,1929]
610 3,1414 [3,1324 ; 3,1504]
Tableau1.4. Estimationdeπ par l’aiguillede Buffon. Intervalle de confiance
à95% pour différentes taillesnd’échantillon
1.4.2. Calculd’unesurface
Les méthodes de Monte Carlo permettent d’estimer une surface. De manière
équivalente, on peut estimer un volume, en considérant un espace à trois dimensions au
lieu de deux.
Le domaine bidimensionnelS considéré est supposé être borné, c’est-à-dire qu’il
existe des réelsa,b,c,d tels queS⊂[a,b]×[c,d]. Comment estimer sa surface|S| ?
On échantillonne deux variables aléatoires indépendantesY etY , selon des lois uni-1 2
formes sur respectivement[a,b] et[c,d]. Le pointY =(Y ,Y ) est donc un point suivant1 2
une loi uniforme sur[a,b]×[c,d]. On définit alorsX =1(Y∈S) la variable aléatoire
valant 1 si le pointY est dans la surface et 0 sinon.
L’algorithme d’estimation consiste donc à considérer un échantillon de n valeurs
n¯X indépendantes. La proportion de points dans la surfaceS ,X =( X)/n est un∑i n ii=1
estimateur sans biais de
Z Zb d dy dy |S|2 1
E[X]= 1((y ,y )∈S) = .1 2
d−cb−a (b−a)(d−c)a c
E[X] est donc le rapport entre la surface deS et la surface du domaine
d’échantillonnage considéré[a,b]×[c,d]. Un estimateur de la surface est donc
n X∑ ii=1¯(b−a)(d−c)X =(b−a)(d−c) . (1.7)n
n
On peut donc obtenir un intervalle de confiance via (1.4), en prenant garde à ne
pas oublier de multiplier chaque terme (ou pour plus d’efficacité juste le résultat final)
par (b−a)(d−c) comme décrit en (1.7).
EXEMPLE 1.1.– A titre d’exemple illustratif, considérons encore l’estimation de π
2via la surface d’un cercle de rayon R = 1 (dont on rappelle que la surface est πR
2quand le rayon est R). Ce cercle est compris dans le carré [−1,1] . La figure 1.4
décrit le domaine d’échantillonnage et quelques points échantillonnés. Le tableau 1.5

  • Accueil Accueil
  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • BD BD
  • Documents Documents