[SON] [AUDIO_VIDE] Bienvenue dans cette séance, dans laquelle nous allons introduire la méthode de Monte Carlo! Et pour ce faire, nous allons utiliser un exemple concret. Avant de commencer, je vais vous décrire le principe de base qu'il y a derrière ce qu'on appelle la méthode de Monte Carlo. L'idée générale est qu'on souhaite évaluer une quantité déterministe en utilisant des tirages aléatoires. Et le problème fondamental qui se pose est celui d'estimer une intégrale, une fonction compliquée. Il y a deux situations qui se présentent, soit que la fonction elle-même soit compliquée, soit qu'on l'intègre sur un domaine compliqué et on peut, bien sûr, avoir la combinaison des deux problèmes. C'est la problématique de base. Je précise tout de suite que la méthode de Monte Carlo est utilisée dans pratiquement tous les domaines fondamentaux et appliqués, que ce soit la physique ou l'économie, la finance, l'ingénierie etc. C'est utilisé très couramment et c'est une méthode extrêmement utile et souple. Je ne dirai qu'un petit mot d'histoire, qui est que cette méthode a été fondé par Metropolis et Ulam en 1949, c'est la date officielle de cette méthode. Et je mentionne aussi que le nom de Monte Carlo fait explicitement référence au Casino de Monte Carlo, là où il y a des jeux de hasard. Je mentionne aussi que ce qui a beaucoup stimulé le développement de cette méthode, c'est le projet Manhattan, le projet qui a vu la naissance de la bombe atomique, et l'idée, c'était de pouvoir simuler des réactions en chaîne avec cet algorithme au lieu de faire des essais avec des vraies bombes. Alors schématiquement, quelle est l'idée derrière la méthode Monte Carlo? C'est d'interpréter une intégrale comme une espérance, que je note un peu symboliquement, le signe d'intégrale, vous le voyez comme une espérance par rapport à une certaine probabilité. Et l'idée, c'est de calculer cette espérance comme une moyenne et ce qu'il y a derrière, c'est la loi des grands nombres. C'est ce que nous verrons. Avant de développer ça de façon générale, nous allons donc étudier, comme je l'annonçais, un exemple concret pour vous montrer comment ça marche. Cet exemple est l'évaluation de pi avec une pluie aléatoire. Voici comment ça se présente. Imaginez un carré dont le côté est de longueur 2, qui est centré en 0, carré rouge. Dedans, il y a un disque de rayon 1 qui est inscrit. On tire au hasard des points dans ce carré, ce qui signifie plus précisément qu'on tire l'abscisse selon une loi uniforme dans le moins 1, 1, leurs données selon une loi uniforme dans moins 1, 1 et X et Y sont indépendants. Donc on jette des points comme ça, au hasard, dans ce sens-là sur le carré. Quelle est la probabilité qu'un point tombe dans le disque? Comme on a des lois uniformes, c'est le rapport entre la surface du disque et la surface du carré. Si on veut l'écrire précisément, donc c'est cette intégrale double sur ce domaine divisé par cette intégrale et c'est tout simplement donc l'aire du disque de rayon 1, donc pi, divisé par l'aire du carré de côté 2, donc ça fait 4. Voilà, la probabilité qu'on tombe dans le disque, c'est pi sur 4. L'idée, c'est juste d'écrire ça d'une autre manière, d'écrire que pi, c'est 4 fois la probabilité qu'un point lancé au hasard dans le carré, comme on l'a décrit, tombe dans le disque. Je vais appeler, pour faciliter les notations, cette probabilité thêta et je vais introduire le nombre de points qui tombent dans le disque quand je fais n tirages de points comme ça, je vais appeler ça Z n. Plus formellement donc, on ajoute les indicatrices de ces événements, chaque événement, c'est le ième point que j'ai lancé est dans le disque. Donc ça, ça vaut 1 si c'est dans le disque, o si c'est dans le carré, mais pas dans le disque. Ces variables donc qui prennent les valeurs 0 ou 1 font que cette somme Z n suit une loi binomiale de paramètres n, thêta. On a n tirages et thêta est bien la probabilité de succès qui, dans cet exemple, est la probabilité de tomber dans le disque. L'étape suivante est d'utiliser la loi des grands nombres, puisque la loi des grands nombres nous affirme que si je divise Z n par n, je regarde quelle est la fréquence, le nombre de fois où mes points sont effectivement tombés dans le disque pendant mes n tirages, j'appelle cet estimateur thêta chapeau n. Thêta chapeau n tend en probabilité et presque sûrement vers thêta, c'est la probabilité qu'on tombe dans le disque, le paramètre de la loi binomiale. Donc on estime pi par 4 fois thêta chapeau n. Il faut bien prendre garde que thêta chapeau n, c'est une variable aléatoire. Donc si on refaisait un autre tirage de ces n points qu'on lance, on obtiendrait une valeur qui pourrait être différente, la question se pose de savoir si on peut donc estimer, donner un sens à la qualité de cet estimateur. C'est ce que nous allons maintenant étudier. Est-ce qu'on peut contrôler la qualité de cet estimateur, oubliant le 4 pour l'instant, qu'on remettra à la fin? Comment on peut décrire les fluctuations de thêta chapeau n? Nous allons utiliser une inégalité que vous avez vu en cours, qui est l'inégalité de Bienaymé-Chebyshev. Je la rappelle sous sa forme générale. Si X est une variable aléatoire réelle, delta est un nombre strictement positif quelconque, alors la probabilité que X moins son espérance soit plus grand en valeur absolue que delta, c'est borné par la variance de X divisé par delta au carré. On va l'appliquer à thêta chapeau n. Faisons-le par étapes. Rappelons que Z n suit une binomiale de paramètres n, thêta. L'espérance de thêta chapeau n, par linéarité, ça va être, donc c'est l'espérance de Z n sur n et par linéarité, ça fait n fois thêta divisé par n, ça fait thêta. Quant à la variance de Z n, puisqu'on a une binomiale, c'est n fois thêta fois 1 moins thêta. Autrement dit, la variance qui m'intéresse étant celle de thêta chapeau n, il y a le 1 sur n qui vient du fait qu'on divise par n, il est élevé au carré, puisque quand on fait une variance, on élève au carré les choses. Ensuite on a n fois et ensuite on a la variance de Z n. On retrouve donc thêta fois 1 moins thêta divisé par n pour la variance de thêta chapeau n. Si j'applique l'inégalité de Bienaymé-Chebyshev à X égal thêta chapeau n, j'obtiens tout de suite que la probabilité que thêta chapeau n moins thêta en valeur absolue dépasse delta, c'est plus petit que thêta fois 1 moins thêta divisé par n delta carré. On va réarranger un peu les choses, de la manière suivante. Je peux prendre n'importe quel delta positif, donc je le prends de cette forme, vous allez voir dans un instant pourquoi, je le prends de la forme lambda fois la racine carrée de ça. Lambda est un nouveau paramètre, strictement positif. On va pouvoir choisir par la suite. Si je réécris cette probabilité juste au-dessous, j'obtiens simplement que, là j'ai remplacé delta par sa valeur, et on a choisi delta de telle sorte qu'ici, cette quantité donne exactement 1 sur lambda carré. Ce qui nous intéresse, en fait, c'est d'estimer la probabilité que thêta chapeau n moins thêta soit plus petit que quelque chose, et voir comment se comporte cette probabilité. Pour ce faire, donc si je prends n'importe quel lambda positif, cette probabilité, c'est 1 moins la probabilité que nous venons d'écrire, et c'est donc plus grand strictement que 1 moins 1 sur lambda carré. On a donc une borne générale pour la probabilité que notre estimateur moins la valeur espérée en valeur absolue soit plus petit que cette échelle-là, que cette probabilité soit plus grande que ce nombre. Prenons, par exemple, lambda égal 3, ça fait que 1 moins 1 sur lambda carré fait à peu près 0.888. Si on lie l'inégalité précédente, elle nous dit qu'avec probabilité supérieure à 0.888, donc une probabilité assez proche de 1 finalement, l'événement qui est que l'écart entre mon estimateur et thêta, sa valeur espérée, est plus petit que 3 fois la racine de thêta 1 moins thêta divisé par n. On a une estimation de la probabilité de cet événement. Cet événement va advenir avec une probabilité au moins égale à 0.888. Le petit ennui dans ce que je viens d'écrire, c'est que thêta, c'est inconnu. On s'en sort facilement en remarquant que thêta fois 1 moins thêta, c'est plus petit que 1/4. Thêta, n'oublions pas que c'est une probabilité, c'est un nombre entre 0 et 1. Donc cette fonction de thêta atteint son maximum, qui est 1/4. Si je réécris ce que j'ai dit là en formule, j'ai donc la probabilité que thêta chapeau n moins thêta en valeur absolue soit plus petit que 3/2 fois 1 sur racine de n, c'est plus grand, c'est au moins cette probabilité de 0.888. Donc on a obtenu une façon de contrôler la probabilité que l'erreur soit de cette forme-là en fonction de n, du nombre de tirages de points. Au final, rappelons-nous que pi, c'était 4 fois thêta, on obtient un encadrement pour pi. On obtient que, juste en réécrivant ce qu'on vient de voir, la probabilité que pi soit plus grand que 4 fois thêta chapeau n moins 6 sur racine de n et soit plus petit que 4 thêta chapeau n plus 6 sur racine de n, cette probabilité est plus grande que 0.888. On a donc, qu'on appellera par la suite un intervalle de confiance, qui nous dit quelle valeur attribuer à ce qu'on va estimer et la seule façon de donner un sens, c'est effectivement, d'estimer la probabilité d'un encadrement de cette forme pour pi. Remarquez que si n augmente, cet intervalle rétrécit autour de pi comme 1 sur racine de n, donc c'est assez lent. Il se trouve que c'est la vitesse correcte, quand nous verrons plus loin que grâce au théorème limite central, c'est cette échelle qui caractérise ces fluctuations en général. Nous allons maintenant voir une expérience numérique qui illustre ce que je viens de dire. Vous pourrez donc vous-mêmes manipuler cette expérience numérique que je vous présente brièvement. Ici, nous avons le disque dans lequel nous allons jeter petit à petit des points au hasard, comme nous l'avons décrit avant. Ici, on a déjà jeté dix points au hasard. Par exemple, pour ce tirage, on en a un qui n'est pas tombé dans le disque. Et on peut augmenter le nombre de tirages. Là, par exemple, si vous en avez déjà 210, je continue, je les ajoute à 1 maintenant, je continue la pluie aléatoire de points. Et là en dessous, j'ai représenté l'estimateur et autour, l'intervalle que nous avons calculé avec l'inégalité de Bienaymé-Chebyshev, qui était en 6 sur racine de n. Plus ou poins 6 sur racine de n. Vous voyez que cet intervalle se rétrécit lentement autour de la bonne valeur et, pour illustrer le fait que si vous tiriez 294 autres points au hasard, vous n'obtenez pas la même chose. Ҫa y ressemble, mais il y a des fluctuations légèrement différentes. On est néanmoins toujours dans le tube qui contient bien pi. Donc on peut accorder une bonne confiance à cet estimateur. Évidemment, dans cet estimateur, pi, sa valeur est connue par avance, c'est la difficulté dans les problèmes où on ne connaît pas ce qu'on calcule, c'est rendre crucial le fait qu'on estime cette enveloppe, cet intervalle de confiance. Voilà ce qui termine cette première séance consacrée à la méthode de Monte Carlo.