← Tous les textes du Grand Oral
MathsNSIPCSESHGGSP
Calculer une aire, un volume ou une intégrale en tirant des points au hasard : l'idée paraît naïve, presque paresseuse. Elle est pourtant devenue l'une des méthodes de calcul les plus utilisées au monde, de la physique des particules aux images de synthèse. Ce texte présente son histoire, son principe, le moyen de mesurer sa précision (un intervalle de confiance, dont le cours complet est donné ici) et la raison profonde de son succès. À chacun d'y choisir une direction et d'y construire sa question.
La méthode porte le nom du célèbre casino de Monaco, symbole du hasard. Le nom naît à la fin des années 1940 au laboratoire de Los Alamos, aux États-Unis, celui qui a conçu la bombe atomique pendant le projet Manhattan.
En 1946, le mathématicien Stanislaw Ulam, convalescent après une maladie, joue au solitaire. Il se demande quelle est la probabilité de réussir une partie. Le calcul exact est inextricable ; il lui vient alors l'idée qu'il serait plus simple de jouer un grand nombre de parties et de compter les réussites. Il comprend aussitôt que la même idée peut servir à des problèmes de physique qu'aucun calcul ne permet de résoudre, comme le parcours des neutrons dans la matière. Il en parle à John von Neumann, qui fait programmer ces simulations sur l'ENIAC, l'un des premiers ordinateurs électroniques.
Ces travaux sont secrets et il leur faut un nom de code. Leur collègue Nicholas Metropolis propose « Monte-Carlo », en clin d'œil à un oncle d'Ulam qui empruntait de l'argent à sa famille pour aller jouer au casino de Monte-Carlo. En 1949, Metropolis et Ulam publient un article intitulé The Monte Carlo Method : le nom est resté.
L'idée a des ancêtres. En 1733, Buffon montre qu'en lançant des aiguilles sur un parquet, la proportion d'aiguilles qui chevauchent une rainure permet d'approcher $\pi$. Mais c'est l'ordinateur qui a rendu la méthode efficace : il peut « lancer » des millions de points par seconde.
On veut l'aire $A$ d'une région du plan, par exemple sous la courbe d'une fonction positive. On l'enferme dans un rectangle d'aire connue $R$. On tire au hasard $n$ points, uniformément dans le rectangle, et l'on compte ceux qui tombent dans la région. La probabilité qu'un point y tombe est $p = \dfrac{A}{R}$. Si $f_n$ est la fréquence des points tombés dans la région, la loi des grands nombres ne dit pas que $f_n$ se rapproche forcément de $p$ quand $n$ grandit (une série de tirages malchanceux reste toujours possible), mais que, plus $n$ est grand, plus il est probable que $f_n$ soit proche de $p$ : pour tout écart fixé, la probabilité que la fréquence s'écarte de $p$ de plus de cet écart tend vers $0$. On prend donc, en sachant qu'on peut se tromper,
$$A \approx R \times f_n.$$Le cas le plus célèbre est celui de $\pi$. On tire des points dans le carré $[0\,;1]^2$, d'aire $1$, et l'on compte ceux qui vérifient $x^2 + y^2 \leqslant 1$, c'est-à-dire qui tombent dans le quart de disque de rayon $1$, d'aire $\dfrac{\pi}{4}$. Pour $n$ grand, la fréquence est très probablement proche de $\dfrac{\pi}{4}$, et quatre fois la fréquence très probablement proche de $\pi$ ; la partie suivante dit avec quelle probabilité et à quelle distance près.
Le même principe donne une intégrale : $\displaystyle\int_0^2 x^2\,\mathrm{d}x = \dfrac{8}{3}$ est l'aire sous la parabole, contenue dans le rectangle $[0\,;2]\times[0\,;4]$ d'aire $8$. Avec $10\,000$ points, une simulation donne $8 \times f_n \approx 2{,}663$. Et il fonctionne de la même façon en dimension 3 : pour le volume d'un solide, on tire des points dans un pavé qui le contient et l'on compte ceux qui tombent dans le solide.
Une méthode de calcul approché n'a de valeur que si l'on sait quelle confiance accorder au résultat. Avec le hasard, on ne peut jamais être certain ; on peut en revanche dire avec quelle probabilité on se trompe de moins d'une certaine quantité. C'est l'objet de l'intervalle de confiance.
Pour $k$ de $1$ à $n$, notons $X_k$ la variable aléatoire qui vaut $1$ si le $k$-ième point tombe dans la région, $0$ sinon. Les tirages étant indépendants, les $X_k$ sont des variables de Bernoulli indépendantes de paramètre $p$. Leur somme $S_n = X_1 + \cdots + X_n$ suit la loi binomiale $\mathcal{B}(n\,;p)$ et la fréquence est $F_n = \dfrac{S_n}{n}$.
On ne connaît pas $p$, mais on peut majorer $p(1-p)$ : la fonction $p \mapsto p(1-p)$ est un polynôme du second degré dont le maximum est atteint en $p = \dfrac{1}{2}$ et vaut $\dfrac{1}{4}$. Donc $V(F_n) \leqslant \dfrac{1}{4n}$.
Appliquée à $F_n$, elle donne $P\big(|F_n - p| \geqslant \delta\big) \leqslant \dfrac{1}{4n\delta^2}$. Choisissons $\delta = \dfrac{a}{\sqrt n}$ : la majoration devient $\dfrac{1}{4a^2}$, qui vaut $0{,}05$ pour $a = \sqrt5 \approx 2{,}24$. Ainsi, avec une probabilité d'au moins $95\,\%$, on a $|F_n - p| < \dfrac{2{,}24}{\sqrt n}$.
L'étape décisive consiste à « retourner » cette inégalité. Dire que $F_n$ est proche de $p$, c'est dire que $p$ est proche de $F_n$ :
$$|F_n - p| < \delta \iff F_n - \delta < p < F_n + \delta.$$On ne connaît pas $p$, mais on connaît $F_n$ après la simulation : on obtient un intervalle qui contient $p$ avec une probabilité d'au moins $95\,\%$.
L'inégalité de Bienaymé-Tchebychev est valable pour toutes les lois ; elle est donc prudente, et l'intervalle obtenu est large. Un résultat plus fin, le théorème de Moivre-Laplace (au-delà du programme), affirme que pour $n$ grand, la loi de $F_n$ est proche d'une loi normale. On en déduit qu'avec une probabilité proche de $95\,\%$, $|F_n - p| \leqslant 1{,}96\sqrt{\dfrac{p(1-p)}{n}}$, et comme $\sqrt{p(1-p)} \leqslant \dfrac{1}{2}$, cet écart est au plus $\dfrac{0{,}98}{\sqrt n}$. On arrondit à $\dfrac{1}{\sqrt n}$.
Pour $\pi$, on multiplie par $4$ : $\left[4f - \dfrac{4}{\sqrt n}\,;\,4f + \dfrac{4}{\sqrt n}\right]$. Une simulation donne :
| $n$ | $4f$ | intervalle de confiance |
|---|---|---|
| $100$ | $3{,}08$ | $[2{,}68\,;3{,}48]$ |
| $10\,000$ | $3{,}154$ | $[3{,}114\,;3{,}194]$ |
| $100\,000$ | $3{,}1535$ | $[3{,}1409\,;3{,}1662]$ |
| $1\,000\,000$ | $3{,}1457$ | $[3{,}1417\,;3{,}1497]$ |
Dans le tableau, le dernier intervalle ne contient pas $\pi \approx 3{,}14159$. Ce n'est pas une erreur de calcul : c'est ce que le niveau de confiance autorise. Le nombre $p$ n'est pas aléatoire ; c'est l'intervalle qui l'est, puisqu'il dépend des points tirés. Dire « au niveau $95\,\%$ », c'est dire que si l'on refaisait l'expérience un grand nombre de fois, au moins $95\,\%$ des intervalles obtenus contiendraient $p$. En refaisant $1\,000$ fois la simulation avec $1\,000$ points, on trouve $985$ intervalles qui contiennent $\pi$ : l'intervalle usuel est un peu prudent.
La largeur de l'intervalle est $\dfrac{2}{\sqrt n}$ : pour la diviser par $2$, il faut $4$ fois plus de points ; pour gagner une décimale, $100$ fois plus. Avec un million de points, on n'obtient que deux ou trois décimales de $\pi$. Pour calculer $\pi$, la méthode est donc très mauvaise. Mais l'intervalle de confiance a une propriété remarquable : sa largeur ne dépend que de $n$, et pas du nombre de variables du problème.
C'est la même mathématique que celle des sondages. Interroger $1\,000$ personnes donne une marge d'erreur d'environ $\dfrac{1}{\sqrt{1000}} \approx 0{,}03$, soit trois points de pourcentage, quelle que soit la taille de la population.
Le mathématicien John Hubbard racontait à ses étudiants qu'il ne voyait pas l'intérêt d'une méthode aussi lente, jusqu'à ce qu'un collègue lui réponde : en dimension 12, par exemple, c'est la seule méthode que l'on sache mettre en œuvre pour approcher un volume. Voici pourquoi.
Les méthodes déterministes, comme la méthode des rectangles, découpent le domaine en une grille. En dimension 1, avec $m$ points, la méthode du point milieu fait une erreur de l'ordre de $\dfrac{1}{m^2}$ : c'est excellent. En dimension 2, il faut une grille de $m\times m = m^2$ points ; en dimension 3, de $m^3$ points ; en dimension $d$, de $m^d$ points. Avec un budget de $N$ points, chaque axe n'en reçoit que $N^{1/d}$, et l'erreur est de l'ordre de $N^{-2/d}$.
L'erreur de Monte-Carlo, elle, est de l'ordre de $\dfrac{1}{\sqrt N} = N^{-1/2}$, quelle que soit la dimension. Les deux sont égales pour $d = 4$ ; au-delà, Monte-Carlo gagne, et de plus en plus nettement.
| dimension | grille : erreur | Monte-Carlo : erreur |
|---|---|---|
| $1$ | $N^{-2}$ | $N^{-1/2}$ |
| $4$ | $N^{-1/2}$ | $N^{-1/2}$ |
| $12$ | $N^{-1/6}$ | $N^{-1/2}$ |
Concrètement, en dimension $12$, un million de points répartis en grille ne font qu'environ $3$ points par axe : la grille ne voit presque rien. Avec le même million de points tirés au hasard, une simulation estime le volume de la boule de rayon $1$ (dont la valeur exacte est $\dfrac{\pi^6}{720} \approx 1{,}335$) à $1{,}32$, avec un intervalle de confiance d'environ $\pm\,0{,}14$.
Or les problèmes en grande dimension sont partout : une particule a $3$ coordonnées de position et $3$ de vitesse, deux particules en ont déjà $12$ ; le prix d'un produit financier peut dépendre de dizaines d'actions ; l'éclairage d'un point d'une image de synthèse dépend de tous les chemins que la lumière peut suivre.
Un ordinateur exécute des instructions déterministes : il ne peut pas, à lui seul, produire du vrai hasard. Il produit des nombres pseudo-aléatoires : une suite calculée par une formule, qui ne présente aucune régularité visible et réussit les tests statistiques du hasard. Le modèle le plus simple est la suite
$$x_{k+1} = (a\,x_k + c) \bmod m,$$où « $\bmod\,m$ » désigne le reste de la division par $m$ ; les nombres $\dfrac{x_k}{m}$ sont dans $[0\,;1[$. La figure ci-dessus utilise une suite de ce type, avec $a = 16\,807$, $c = 0$ et $m = 2^{31} - 1$ : c'est le générateur « standard minimal » popularisé par Stephen Park et Keith Miller en 1988. Le premier terme, la graine, détermine toute la suite : avec la même graine, on retrouve exactement les mêmes « tirages », ce qui est très utile pour vérifier un calcul.
John von Neumann proposa dès 1946 une méthode simple (élever un nombre au carré et garder les chiffres du milieu), tout en notant avec humour que quiconque prétend produire du hasard par des calculs « est en état de péché ». Python utilise aujourd'hui un algorithme bien plus élaboré, le Mersenne Twister, dont la suite ne se répète qu'après $2^{19937} - 1$ termes. Pour la cryptographie, où le hasard doit être imprévisible, on utilise des générateurs spéciaux.
Le premier programme approche $\pi$ et donne l'intervalle de confiance ; le second estime le volume de la boule de rayon $1$ en dimension $d$. On peut changer $n$ et $d$ et les exécuter (dans le navigateur, mieux vaut ne pas dépasser quelques dizaines de milliers de points).
random.seed(…) fixe la graine, et donc toute la suite des tirages.Ce texte n'est pas un Grand Oral. Il rassemble des connaissances dans lesquelles chacun peut choisir une direction, la creuser et formuler sa propre question. Quelques directions possibles :
Le jury peut interroger sur les chapitres de spécialité mobilisés, et la question de l'origine du nom « Monte-Carlo » est presque certaine. Avec ce thème, il est utile de connaître parfaitement : les variables aléatoires, l'espérance et la variance, la loi de Bernoulli et la loi binomiale ; la somme de variables aléatoires indépendantes ; l'inégalité de Bienaymé-Tchebychev et la loi des grands nombres ; l'intégrale et son lien avec l'aire ; la méthode des rectangles ; les volumes usuels.
Pour réviser ces chapitres, l'application Maths FlashBac reprend tout le cours de spécialité en cartes.