Méthode de Monte-Carlo

Supposons qu'il existe une expression de l'espérance mathématique d'une fonction g de la variable aléatoire X, résultant du théorème de transfert, selon lequel

${\displaystyle G=\mathbb {E} (g(X))=\int g(x)f_{X}(x)\,{\mbox{d}}x}$

où f_X est une fonction de densité de X sur le support [a , b]. Il est fréquent de prendre une distribution uniforme sur [a , b] :

${\displaystyle f_{X}(x)={\frac {1}{b-a}}}$

Ceci peut être étendu aux probabilités discrètes en sommant grâce à une mesure ν discrète, de type Dirac.

L'idée est de produire un échantillon (x₁ ,x₂,...,x_N) de la variable aléatoire X (donc d'après la densité f_X si X est continue ou suivant la loi de X si X est discrète) sur le support [a , b], et de calculer un estimateur de G dit de Monte-Carlo, à partir de cet échantillon.

La loi des grands nombres suggère de construire cet estimateur à partir de la moyenne empirique[3] :

${\displaystyle {\tilde {g}}_{N}={\frac {1}{N}}\sum _{i=1}^{N}g(x_{i}),}$

qui se trouve être, par ailleurs, un estimateur sans biais de l'espérance.

Ceci est l'estimateur de Monte-Carlo. Nous voyons qu'en remplaçant l'échantillon par un ensemble de valeurs prises dans le support d'une intégrale, et de la fonction à intégrer, nous pouvons obtenir une approximation de sa valeur, construite statistiquement.

Cette estimation est sans biais, dans le sens où

${\displaystyle \mathbb {E} ({\tilde {g}}_{N})=G=\mathbb {E} (g(X))}$

Il faut aussi quantifier la précision de cette estimation, via la variance de ${\displaystyle {\tilde {g}}_{N}}$ qui s'exprime à l'aide de la variance de ${\displaystyle g(X)}$.

${\displaystyle \sigma _{g}^{2}:=\sigma _{g(X)}^{2}=\mathbb {E} ([g(X)-\mathbb {E} (g(X))]^{2})=\mathbb {E} (g^{2}(X))-\mathbb {E} ^{2}(g(X))=\int _{\Omega }g^{2}(x)f_{X}(x)\,{\mbox{d}}x-G^{2}}$

Si l'échantillon est supposé iid, cette dernière est estimée à l'aide de sa variance empirique

${\displaystyle S_{g(X)}^{2}={\frac {1}{N}}\sum _{i=1}^{N}(g(x_{i})-{\tilde {g}}_{N})^{2}={\frac {1}{N}}\sum _{i=1}^{N}g^{2}(x_{i})-{\tilde {g}}_{N}^{2}\simeq \sigma _{g}^{2}}$

D'après le théorème central limite, on sait que la variable :

${\displaystyle Z:={\frac {{\tilde {g}}_{N}-G}{\sigma _{{\tilde {g}}_{N}}}}={\frac {{\tilde {g}}_{N}-G}{\sigma _{g}/{\sqrt {N}}}}}$

qui est centrée et réduite, suit approximativement la loi normale centrée réduite ${\displaystyle {\mathcal {N}}(0;1)}$, ou loi de Gauss. Il est alors possible de construire des intervalles de confiance, ce qui permet d'encadrer l'erreur commise en remplaçant G par ${\displaystyle {\tilde {g}}_{N}}$. Si cette erreur est dénotée e_N, alors pour un niveau de risque ${\displaystyle \alpha }$ donné, on a :

${\displaystyle |e_{N}|\leq z_{1-\alpha /2}{\frac {\sigma _{g}}{\sqrt {N}}}}$

avec probabilité 1–α. Le réel ${\displaystyle z_{1-\alpha /2}}$ est le quantile de la loi normale centrée réduite. Par exemple, au niveau de risque ${\displaystyle \alpha =5\%}$, on trouve dans les tables ${\displaystyle z_{1-\alpha /2}=1,96}$ et l'erreur est majorée par ${\displaystyle 1,96\,\sigma _{g}/{\sqrt {N}}}$. Cette méthode permet donc de quantifier l'erreur commise, à condition d'estimer σ_g par sa contrepartie empirique

${\displaystyle {\hat {\sigma }}_{g}={\sqrt {S_{g(X)}^{2}}}}$

On voit ainsi que l'erreur est de l'ordre de ${\displaystyle 1/{\sqrt {N}}}$. Par exemple, multiplier la taille de l'échantillon par 100 permet de diviser par 10 l'erreur d'estimation.

Il est à noter qu'en pratique, σ_g n'est pas connu et doit être estimé ; comme précisé plus haut, on peut utiliser sa contrepartie empirique. Diverses méthodes, dites techniques de réduction de la variance, permettent d'améliorer la précision — ou de diminuer le temps de calcul — en remplaçant g(X) par une autre variable aléatoire. Ces techniques entrent en général dans l'une des classes suivantes : l'échantillonnage préférentiel, les variables de contrôle, la variable antithétique, la stratification et le conditionnement.

Le nombre de simulations ${\displaystyle N}$ nécessaires pour atteindre une marge d'erreur ${\displaystyle e=z_{1-\alpha /2}{\frac {\sigma }{\sqrt {N}}}}$ voulue est parfois trop important avec la méthode Monte-Carlo. En effet lorsqu'on veut atteindre une marge d'erreur ${\displaystyle e}$ faible, il faut que ${\displaystyle N=z_{1-\alpha /2}{\frac {\sigma }{e^{2}}}}$ donc ${\displaystyle N}$ est très grand quand ${\displaystyle e}$ est petit. Pour remédier à ce problème il existe des méthodes dites de "réduction de variance" ou de "Monte-Carlo accélérées" qui demandent moins de simulations pour atteindre le même niveau de précision. Parmi ces méthodes on distingue deux grands types de méthodes : les méthodes d'échantillonnage préférentiel et les méthodes particulaires.

Cette méthode est proche de l'expérience de l'aiguille de Buffon.

Soit un point M de coordonnées (x, y), où 0<x<1 et 0<y<1. On tire aléatoirement les valeurs de x et y entre 0 et 1 suivant une loi uniforme. Le point M appartient au disque de centre (0,0) de rayon R=1 si et seulement si x²+y²≤1. La probabilité que le point M appartienne au disque est π/4, puisque le quart de disque est de surface σ=π R²/4=π/4, et le carré qui le contient est de surface S=R²=1 : si la loi de probabilité du tirage de point est uniforme, la probabilité de tomber dans le quart de disque vaut σ/S=π/4.

En faisant le rapport du nombre de points dans le disque au nombre de tirages, on obtient une approximation du nombre π/4 si le nombre de tirages est grand.

Représentation du calcul de la valeur de π par rapport du nombre de points aléatoires étant contenus dans un quart de cercle, l'ensemble des possibles étant un carré de côté R.

Cet exemple est un classique en vulgarisation de la méthode de Monte-Carlo. Soit une zone rectangulaire ou carrée dont les côtés sont de longueur connue. Au sein de cette aire se trouve un lac dont la superficie est inconnue. Grâce aux mesures des côtés de la zone, on connaît l'aire du rectangle. Pour trouver l'aire du lac, on demande à une armée de tirer X coups de canon de manière aléatoire sur cette zone. On compte ensuite le nombre N de boulets qui sont restés sur le terrain ; on peut ainsi déterminer le nombre de boulets qui sont tombés dans le lac : X−N. Il suffit ensuite d'établir un rapport entre les valeurs :

${\displaystyle {\frac {\mathrm {superficie} _{~\mathrm {terrain} }}{\mathrm {superficie} _{~\mathrm {lac} }}}={\frac {X}{X-N}}}$

${\displaystyle \Longrightarrow \qquad \mathrm {superficie} _{~\mathrm {lac} }={\frac {(X-N)}{X}}\ \times \ \mathrm {superficie} _{~\mathrm {terrain} }}$

Par exemple, si le terrain fait 1 000 m², que l'armée tire 500 boulets et que 100 projectiles sont tombés dans le lac, alors une estimation de la superficie du plan d'eau est de : 1000×100÷500 = 200 m².

Estimation de la surface du lac grâce à des tirs d'artillerie aléatoires

La qualité de l'estimation s'améliore (lentement) en augmentant le nombre de tirs et en s'assurant que les artilleurs ne visent pas toujours le même endroit mais couvrent bien la zone, de manière uniforme. Cette dernière remarque est à mettre en parallèle avec la qualité du générateur aléatoire qui est primordiale pour avoir de bons résultats dans la méthode de Monte-Carlo. Un générateur biaisé est comme un canon qui tire toujours au même endroit : les informations qu'il apporte sont réduites.

Méthode contrainte-résistance : la fréquence de défaillance correspond à l'aire sous l'intersection des courbes rouge et bleue (haut).

La méthode de Monte-Carlo peut être utilisée pour déterminer l'aire sous l'intersection de deux courbes, qui n'est qu'une surface particulière.

Les courbes peuvent être les courbes représentatrices des densités de probabilité de deux lois. C'est par exemple utilisé dans la méthode contrainte-résistance :

• un système est soumis à une contrainte — une sollicitation quelle qu'elle soit (effort mécanique, variation de température, passage de courant électrique, …) — dont l'intensité est une variable aléatoire S ;
• le système est conçu pour résister à cette contrainte, sa résistance est exprimée par une valeur, une variable aléatoire R ;
• le système est validé si la résistance est supérieure à la contrainte — R > S — dans un certain nombre de cas (typiquement 99 % ou 99,9 %).

La probabilité complémentaire — les cas de défaillance, celle pour laquelle R ≤ S — est l'aire sous l'intersection des deux courbes représentant les lois.

On peut déterminer la probabilité P(R > S) en faisant des tirages aléatoires sur R et S et en dénombrant les cas pour lesquels « R > S » est vrai.

Aux échecs, comme dans beaucoup de jeux de plateau, il est possible de mesurer la valeur d'une position, et donc des coups y conduisant, en évaluant quantitativement la position obtenue : nombre de pièces sur l'échiquier, valeurs des pièces (1 point par pion, 5 par tour...), position relative des pièces entre elles, et en pondérant la valeur trouvée par les libertés, les protections des pièces, etc. Cette évaluation basée sur l'analyse et l'expertise est d'autant plus rapide à mesurer qu'on avance dans la partie, car le nombre de pièces diminue.

Dans le jeu de go, l'évaluation d'une position globale reste très difficile avec des méthodes d'analyses classiques du fait de l’enchevêtrement et de la complexité des positions locales et du nombre quasi infini de suites de coups possibles. En 2006, le mathématicien Rémi Coulom a fait progresser de manière très sensible cette fonction d'évaluation et l’efficience des logiciels de jeu de go en utilisant la méthode de Monte-Carlo : on joue "au hasard" un grand nombre de fins de parties réalistes à partir de la position "en cours d'évaluation" et on comptabilise la proportion de parties gagnantes/perdantes. Cette estimation statistique s'affine en biaisant le hasard par élimination de coups a priori stupides. Cette méthode s'avère très efficace[4] - [5]. Elle est utilisée en particulier par les programmes AlphaGo et AlphaZero[6].

Parfois, pour savoir si un coup ambigu doit être fait (échange de pièces par exemple), lorsqu'on manque d'information , ou pour choisir entre plusieurs coups menant tous à des pertes de matériel, il est possible de lancer plusieurs parties rapides au hasard, pour savoir quelle est la moins mauvaise ou la meilleure des solutions.

Selon l'hypothèse des marchés efficients, les performances boursières sont aléatoires et suivent une loi normale. Dans ces conditions, il est possible de réaliser des milliers de tirages aléatoires pour déterminer les probabilités d'atteindre certaines performances boursières dans le futur[7]. Cette caractéristique des marchés financiers permet d'utiliser la méthode de Monte-Carlo pour valoriser des options, ou encore des SPAC.

• Emmanuel Gobet, Méthodes de Monte-Carlo et processus stochastiques - du linéaire au non linéaire, Éditions de l'École polytechnique, 2013
• Carl Graham, Denis Talay, Simulation stochastique et méthodes de Monte-Carlo, Éditions de l'École polytechnique, 2011
• (en) Introduction to Monte Carlo Algorithm Werner Krauth - CNRS, Laboratoire de Physique Statistique, École Normale Supérieure
• (en) Michael Mascagni, Advanced Monte Carlo Methods I & II, Cours du ETH de Zurich (2005/2006). [PDF] Notes de cours. On pourra également consulter la page de présentation du cours, qui contient de nombreuses références disponibles au format en pdf.
• Simon Léger, Monte Carlo pour les nuls, 2006 [PDF] [lire en ligne]
• Une explication de la méthode de Monte-Carlo par le physicien Pierre Auger
• J. Morio et M. Balesdent, Estimation of Rare Event Probabilities in Complex Aerospace and Other Systems : A Practical Approach, Cambridge, Elsevier Science, 2015, 216 p. (ISBN 978-0-08-100091-5)
• (en) Cours de problèmes inverses par méthode de Monte Carlo - A. Tarantola, Institut de Physique du Globe de Paris
• (en) Christian Robert et George Casella, Monte Carlo Statistical Methods, Springer-Verlag, coll. « Springer Texts in Statistics », 2010
• (en) Christian Robert (statisticien) et George Casella, Introducing Monte Carlo Methods with R, Springer-Verlag, coll. « Use R! Series », 2007, 283 p. (ISBN 978-1-4419-1575-7, lire en ligne)

• Simulation informatique,
• Simuler des processus se produisant à des taux connus : Méthode de Monte-Carlo cinétique.
• les techniques les plus efficaces de planification de mouvement utilisent des algorithmes probabilistes.
• Méthodes de réduction de la variance de l'estimateur de Monte Carlo : Importance sampling
• Physique statistique
• Filtre particulaire
• Algorithme probabiliste
• Algorithme de Las Vegas
• Algorithme de Monte-Carlo
• Méthode de Monte-Carlo par chaînes de Markov
• Prévision d'ensembles en météorologie
• Recherche arborescente Monte-Carlo

Codes de simulation utilisant des méthodes de Monte-Carlo

• Geant4
• MCNP et MCNPX
• Tripoli-4

• (en) Un exemple de simulation Monte-Carlo clair et didactique L'exemple se base sur la fabrication d'une pièce mécanique à partir de ses composants.
• (en) MATLAB Monte-Carlo simulator with several examples