Ceci est une traduction automatique ; le texte original est en anglais. Consulter l'article original
Le hasard achète la précision à un taux de change désastreux
Dix fois plus d'échantillons apportent environ trois fois plus de précision. Pas dix. Ce taux de change est fixe, et aucune astuce ne permet de le renégocier.
Lancer des fléchettes sur un carré pour mesurer π constitue la première démonstration classique des méthodes de Monte-Carlo. Il suffit de compter la proportion de fléchettes tombant à l'intérieur du quart de cercle, de la multiplier par quatre, et l'on obtient une estimation.
Ce que la démonstration passe généralement sous silence, c'est à quel point elle fonctionne mal.
Trois préréglages, et ce qu'ils coûtent
Monte Carlo π propose trois tailles d'échantillon : 200, 2000 et 20000. Elles s'exécutent avec une graine fixe, de sorte qu'il ne s'agit pas d'anecdotes, mais bien des trois mêmes nombres chaque fois que l'on ouvre la page.
- 200 points donnent 3,040000, soit un écart de 1,02 × 10⁻¹
- 2000 points donnent 3,122000, soit un écart de 1,96 × 10⁻²
- 20000 points donnent 3,127800, soit un écart de 1,38 × 10⁻²
Entre la première et la dernière ligne, la quantité de travail est multipliée par cent, et le résultat est encore faux dès la deuxième décimale. Il n'a pas encore gagné le "3,14" que tout écolier sait réciter.
Le taux varie comme l'inverse de la racine carrée
Chaque lancer de fléchette est une épreuve indépendante de type oui/non, et l'erreur-type d'une proportion mesurée sur n épreuves diminue comme 1/√n. Pour cet estimateur particulier, l'erreur typique s'élève à 0,116 pour 200 échantillons, 0,0367 pour 2000 et 0,0116 pour 20000.
Ainsi, dix fois plus d'échantillons apportent environ 3,16 fois plus de précision, car 3,16 est la racine carrée de dix. Pour gagner un chiffre décimal, soit un facteur dix en précision, il faut multiplier le nombre d'échantillons par cent. Pour passer de l'erreur associée à 2000 échantillons, d'environ 0,037, à 0,0037, il faut 200 000 fléchettes.
Ce résultat mérite d'être retenu, car il ne s'agit pas d'une propriété de π, des fléchettes ou de cette implémentation particulière. C'est le théorème central limite à l'œuvre : l'erreur de la moyenne de grandeurs indépendantes diminue comme la racine carrée du nombre d'éléments moyennés, quelle que soit leur nature. La même arithmétique régit les sondages d'opinion, le comptage d'événements en physique des particules et toutes les simulations que l'on peut exécuter.
Ce qu'une seule graine ne peut pas révéler
Examinez à présent de nouveau l'erreur de ces trois préréglages, car elle ne se comporte pas comme la règle vient de le prédire. En passant de 200 à 2000, l'erreur a été divisée par 5,19. En passant de 2000 à 20000, elle n'a été divisée que par 1,42. Aucun de ces rapports ne vaut 3,16.
Rien n'est anormal. La loi de la racine carrée décrit l'erreur typique, c'est-à-dire la largeur de la distribution dont l'estimation est issue, et une exécution unique n'est qu'un tirage au sort dans cette distribution. L'exécution à 2000 points s'est trouvée tomber plus près que son erreur typique, à environ un demi-écart-type. L'exécution à 20000 points s'est trouvée tomber plus loin. Leur rapport ne prouve presque rien.
C'est l'erreur d'interprétation la plus fréquente concernant une simulation. Une exécution qui donne un bon résultat n'est pas la preuve d'une bonne méthode, et une exécution qui donne un mauvais résultat ne prouve pas que la méthode est mauvaise. On ne peut pas observer ce taux à partir d'une seule graine ; on ne peut l'observer qu'en répétant l'expérience et en analysant la dispersion, ce que montre Normal Distribution lorsqu'elle trace cette dispersion sous la forme d'une courbe.
Pourquoi on s'en contente malgré tout
Une méthode nécessitant de multiplier le travail par cent pour chaque chiffre gagné semble indéfendable, et pour les problèmes à une dimension, elle l'est effectivement. Une intégration numérique classique sur grille fait bien mieux sans difficulté.
La raison pour laquelle la méthode de Monte-Carlo domine le calcul numérique réel est que 1/√n ne fait aucune mention de la dimension. Appliquez une grille à un problème en 20 dimensions avec 10 points par axe, et vous aurez besoin de 10²⁰ évaluations. La méthode aléatoire n'exige toujours que ce que 1/√n impose pour la précision souhaitée, sans se soucier du fait qu'il y ait 20 axes.
Le taux de change est donc désastreux, mais il est également constant. En faible dimension, mieux vaut le refuser. En grande dimension, c'est fréquemment la seule option envisageable, ce qui explique pourquoi la physique, la finance et le rendu graphique s'en acquittent tous.
Poisson correspond à la même arithmétique abordée sous l'angle du comptage : lorsque l'on compte des événements rares, la variance est égale à la moyenne, si bien que l'erreur relative diminue à nouveau comme l'inverse de la racine carrée du comptage. Doubler la confiance dans la mesure d'un taux exige toujours de quadrupler la durée d'observation.