Une tarte au pi nommée Monte Carlo

Une active communauté d'étudiants, chercheurs et bidouilleurs célèbrent à Marseille la "journée π" le 3ème mois, 14ème jour de chaque année. Une occasion de rêve pour en apprendre plus sur les mathématiques et la science dans une ambiance conviviale... Mais c'est aussi l'occasion d'un concours de tartes!

J'ai eu l'opportunité d'y participer l'an dernier (soit pour l'édition 2016) avec une tarte appelée "Monte Carlo". Je vais donner ici la "recette" de ma tarte, le lien avec le nombre π et quelques digressions mathématiques (notament par rapport à la présence incongrue d'un éléphant mais aussi par rapport à la démarche scientifique)... Cette page est un "notebook" - vous pouvez donc la télécharger et relancer les analyses et figures (en utilisant python + jupyter). C'est aussi un travail non figé - prière de me suggérer des corrections!

Initialisons d'abord notre notebook:

La tarte ressemble à ceci:

La recette¶

L'idée de cette tarte est de commencer par la forme ronde du moule...

et de tracer le plus grand carré qu'on puisse y inscrire. Pour celà, rien de plus simple, il suffit de tracer les diagonales sur les cardinales (nord-sud et est-ouest):

et de joindre leur extrémités pour obtenir ce carré:

À noter: le disque contenu dans le cercle bleu a un diametre de $2$, sa surface est donc égale à $\pi$. Le carré vert est composé de quatre triangles isocèle rectangle qui peuvent être réarrangés en deux carrés unitaires: sa surface vaut donc $2$. De façon équivalente, la longueur de son coté est $\sqrt{2}$ (c'est la longueur de l'hypothénuse du carré unité car par Pythagore sa longueur vaut $\sqrt{1^2 + 1^2}$) ce qui confirme que la surface est bien $2$.

Prenons donc maintenant une bonne poignée de smarties (disons $22$) et jetons les sur la tarte. (On dit que si l'un tombe de la tarte -comme sur la photo ci-dessus- on le jette à nouveau au hasard sur la tarte.)

La tarte, avec son carré et ses smarties, est prète!

Monte Carlo?¶

Maintenant, pourquoi "Monte Carlo"? Parce que cette cité balnéaire du sud de la France est bien connue pour ses casinos, et que là, le hasard est loi (souvent en faveur des opérateurs de ces casinos mais c'est une autre histoire). Par jeu, des mathématiciens ont utilisé ce topnyme pour désigner les algorithmes qui utilisent des méthodes aléatoires pour effectuer des calculs. En particulier ces méthodes sont utilisées pour calculer l'aire de certaines surfaces, les fameuses "integrales" (dont le symbole est $\int$). D'innombrables applications pratiques en mathématiques et physique pour lesquelles les variables résident dans des espaces à hautes dimensions (par exemple une image pour laquelle chaque pixel constitue une dimension) dépendent de ces solutions. Pour le moment, restons dans l'espace bidimensionnel de notre tarte...

En effet, quel lien entre Monte Carlo et notre tarte?

Tout d'abord, on peut facilement compter le nombre de smarties qui sont tombés dans le carré:

et les peindre d'une couleur différente:

Aussi, nous avons jeté les smarties au hasard: leur probabilité d'attérir n'importe où sur la tarte est uniforme. Par conséquent, la probabilité d'attérir dans le carré est le ratio de sa surface relative à celle du cercle, soit $\frac{2}{\pi}\approx 63\%$. Voyons voir ce que celà donne:

des résultats proches! On note alors le but de notre calcul: le nombre relatif de smarties donne une approximation de $\pi$ comme

$$ \pi \approx 2 * \frac {N}{n} $$

où $N$ est le nombre total de smarties et $n$ le nombre de smarties tombés dans le carré. J'ai trouvé la possibilité d'approcher un nombre aussi respecté que π par un simple jet aléatoire de sucreries suffisant pour inscrire cette tarte au concours...

Pour cette tarte en particulier (donc cette instance particulière de l'expérience de Monte Carlo):

MAGNIFIQUE! On obtient avec seulement $22$ smarties une estimée de l'ordre de $0.04 \%$!

une évaluation quantitative¶

On peut résumer notre algorithme à la fonction suivante dans laquelle nous généralisons pour un nombre arbitraire de smarties:

Evaluons cette méthode ave 10, 100, ..., un million de smarties (quelle tarte!):

On voit que l'estimation devient progressivement meilleure.

Quand nous n'avons pas autant de smarties, une autre solution est de répéter l'expérience plusieurs fois. Pour celà, nous utilisons un aspect important des générateurs de nombres aléatoires: ils sont pseudo-aléatoires. En effet, si ces méthodes donnent par défaut des valeurs aléatoires et indépendentes, elles n'en restent pas moins des algorithmes déterministes. En particulier, si on spécifie la vealur initiale de l'algorithm (la "graine"), on obtient alors toujours la même série de nombres aléatoires. On dit alors que le bruit est gelé. C'est utile ici pour répéter la même expérience avec des séquences différentes mais reproducibles:

Etrange? La méthode est précise pour certaines instances, pas pour d'autres... Pourquoi et qu'apprenons nous de cette observation?

Imaginons que nous avons $N=1000$ et beaucoup ($10000$) de répétitions de notre estimation:

On peut alors tracer l'histogramme, c'est-à-dire le diagramme montrant la distribution des différentes valeurs obtenues pour des répétitions indépendentes de notre méthode:

Un tel comportement est fréquent en sciences: En essayant d'éstimer une valeur inconnue (on dit alors que c'est une variable cachée ou latente), ici $\pi$, nous obtenons une mesure approchée. Elle est approchée par l'intermédiaire de différente sources de bruit, comme l'alea dans notre algorithme de Monte Carlo mais ce peut être le bruit de mesure d'un appareil de mesure imparfait, le bruit inhérent dans un telescope qui essaie de détecter une source très distante, un neurone qui s'active de façon imprédictible, ... L'évaluation de la variabilité de la méthode est par conséquent une étape essentielle du processus scientifique.

Les mathématiques offrent alors des outils qui nous permettent de généraliser cette variabilité. Premièrement, on reconnait la forme de cet histogramme, c'est une Gaussienne (ou loi normale, ou courbe en cloche) dqui est simplement caractérisée par deux paramètres (que les statisticiens appellent les deux premiers moments):

Ce résultat est la conséquence du theorème central limite. Celui-ci montre que quand l'on collecte indépendamment des valeurs autour d'une certaine moyenne et avec une certaine valeur de bruit, alors la distribution est une Gaussienne.

Un résultat important de ce théorème est de montrer que quand on augmente le nombre d'échantillons (ici, c'est le nombre de smarties qui nous servent à estimer π), alors la précision (c'est à dire l'inverse du carré de la déviation standard) augmente proportionnellement avec ce nombre:

Remémorons nous la hiérarchie de notre procédure:

• nous testons des distributions à différents nombre d'échantillons,
• à chaque niveau, nous effectuons différents essais,
• pour chaque essai, nous faisons une tarte avec beaucoup de smarties et comptons leur nombre relatif dans le carré.

Ce semble compliqué mais prend seulement quelques secondes sur un ordianteur moderne --- ce qui explique la popularité de telles méthodes de nos jours.

Mais ça explique aussi pourquoi les scientifiques sont précautionneux avant de clamer sur tous les toits un résultat qui n'est pas encore validé statistiquement! En particulier, une valeur estimée est souvent donnée autour d'une valeur médiane et dans un intervale de confidence correpondant à 95% des cas:

Notre exploration de cette tarte bien spéciale est presque terminée: d'une tarte, nous avons déduit un algorithme qui calcule une valeur approchée de π. Nous avons alors observé que ce résultat variait et avons tiré parti d'outils mathématiques pour quantifier cette variabilité. Maintenant, nous savons que π vaut environ $3.15$ et presque surement entre $3.05$ et $3.25$. Très bien.

un éléphant dans la salle?¶

Mais attendez, ce résultat est en désaccord avec le résultat triomphal obtenu avec la tarte à $22$ smarties avec une erreur de l'ordre de $0.04 \%$! C'est bien mieux que le résultat avec $10000$ tartes de $1000$ smarties... Que c'est-il passé?

Nous avons vu en haut que les résultats dépendent de l'instance (graine) du générateur de nombre aléatoires:

Si on répète de nombreuses fois l'expérience, on obtient:

On peut alors tracer l'histogramme, c'est-à-dire le diagramme montrant la distribution des différentes valeurs obtenues pour des répétitions indépendentes de notre méthode:

Comme maintenant nous avons utilisé un nombre limité de smarties, la distribution a toujours une envelope Gaussienne, mais n'est non-nulle que pour certaines valeurs précises (qui correspondent aux valeurs possibles de type $\frac k {22}$). Parmi ces différentes valeurs, la plus probable est celle qui donne une excellente approximation de π:

Cette approximation de π est connue depuis longtemps, mais deux questions émergent:

• le cuistot a menti?
• pourquoi cette approximation est bonne?

Pour la première question, on peut répondre en estimant le ratio de tartes à $22$ smarties qui n'aurait pas donné $7$ smarties:

J'admets que j'ai "aidé" le hasard.... Encore un rappel de faire attention à toute déclaration trop optimiste à apartir de résultats scientifiques préliminaires...

Pire que ça, un autre biais est la connaissance que le nombre $22$ donne une bonne estimation. Quoi? Mais, pourquoi $22$ et pas $42$? A priori, il n'y a pas de raison qu'une approximation de π soit meilleure qu'une autre.

Examinons les erruers obtenues quand on change le dénominateur d'une approximation de π par un nombre rationnel:

$$ \pi \approx \frac n d $$

tel que $$ n = I( \pi \cdot d) $$ où $I(x)$ est la valeur entière de $x$.

Traçons la valeur de l'erreur en fonction du dénominateur:

Interessant, l'envelope de cette courbe suit une tendance décroissante qui est encore liée au théorème central limite: comme le dénominateur augmente, la précision aussi. C'est la ligne pointillée en $1/d$, qui est une ligne droite car nous sommes en coordonnées logarithmiques sur les deux axes.

Comparée à cette ligne de base, il est surprenant d'observer que l'erreur décroit puis on observe un pic. Le premier pic est à $7 / 22 $ (notre tarte) et ainsi de suite pour les $16$ prochains pics:

On pouvait s'y attendre car le même comportement se répète simplement pour des approximations égales:

$$ \frac {22} {7} = \frac {22*2} {7*2} =\frac {44} {14} = \frac {22*3} {7*3} = \frac {66} {21} = \ldots $$

Aussi, le pic peut s'estimer qualitativement comme une approximation rogressive du rapport 22 / 7 (ligne verte):