Probabilités et statistiques · Méthode de Monte-Carlo

Méthode de Monte-Carlo

La méthode de Monte-Carlo estime un nombre par échantillonnage aléatoire. Placez N points indépendamment et uniformément dans le carré unité : la proportion qui tombe dans une région estime son aire, avec une erreur-type proportionnelle à 1/√N. Observez comment l’estimation de π se stabilise et comment évolue son incertitude.

La méthode de Monte-Carlo sur ce graphique

Une méthode de Monte-Carlo estime un nombre fixe par échantillonnage aléatoire. Il s’agit ici d’une aire : on place NN points uniformément au hasard dans le carré unité. Si HH d’entre eux tombent dans une région, H/NH/N estime son aire aa. Le quart de disque a pour aire π/4\pi/4 : 4H/N4H/N estime donc π\pi. Pour la région sous y=e−x2y = e^{-x^2}, une intégrale sans primitive élémentaire se ramène au même comptage. Le graphique du bas suit l’estimation lorsque NN augmente jusqu’à un million, avec l’intervalle dans lequel elle devrait tomber dans 95 % des cas.

Pourquoi la proportion estime-t-elle l’aire ?

Un point réparti uniformément sur un carré d’aire 1 tombe dans une région avec une probabilité égale à son aire. Chaque point constitue un essai indépendant de même probabilité. D’après la loi des grands nombres, la proportion de points dans la cible se rapproche de aa. La forme de la région importe peu, pourvu qu’on sache déterminer si un point lui appartient.

Quelle précision peut-on attendre ?

Le nombre de points dans la cible suit une loi binomiale, donc la proportion H/NH/N a pour écart-type a(1−a)/N\sqrt{a(1-a)/N}. L’erreur typique décroît comme 1/N1/\sqrt{N} : dix fois plus de points la divisent par environ 10≈3.16\sqrt{10} \approx 3.16. Pour la diviser par dix, il en faut environ cent fois plus. Même un million de points laisse sur π une marge d’environ ±0.003. Pour estimer cette marge, il n’est pas nécessaire de connaître l’aire exacte : remplacer aa par la proportion observée p^=H/N\hat p = H/N donne la marge ±1.96p^(1−p^)/N\pm 1.96\sqrt{\hat p(1-\hat p)/N} d’un intervalle de confiance approché à 95 %. Ici on l’utilise à partir de dix points dans la cible et dix en dehors. Si l’on répétait l’expérience avec le même NN, environ un intervalle sur vingt manquerait la valeur exacte. Le fuseau bleu est tracé autour de la valeur exacte pour chaque NN pris séparément. Une trajectoire entière n’est pas tenue d’y rester et une réalisation peut s’éloigner temporairement de la valeur exacte quand on ajoute des points. C’est la marge qui se resserre de façon prévisible.

Quand la méthode est-elle avantageuse ?

Pour une fonction lisse d’une seule variable, une règle déterministe comme celle de Simpson (voir Intégration numérique) est bien plus précise à nombre d’évaluations égal. L’intérêt de Monte-Carlo est que l’exposant de son taux de convergence 1/N1/\sqrt{N} ne change pas avec le nombre de dimensions. À l’inverse, une grille de mm points par côté en demande mdm^d en dimension dd : Monte-Carlo peut ainsi devenir préférable en grande dimension. Les petites cibles révèlent sa faiblesse : l’erreur-type rapportée à l’aire vaut (1−a)/(aN)\sqrt{(1-a)/(aN)}. Une région couvrant un centième du carré exige donc bien plus de points pour une même précision relative.

À observer

  • Des points aléatoires ne sont pas régulièrement espacés : avec quelques centaines de points, il est normal d’observer des amas et des vides.
  • Les points proviennent d’un générateur pseudo-aléatoire à graine numérique. Un lien partagé restitue donc les mêmes points. Une fois le million atteint, « Placer des points » recommence avec la graine suivante.

À voir aussi