[AUDIO_VIDE] Bienvenue dans cette séance où nous continuons notre initiation à la méthode de Monte-Carlo. Nous allons voir que, essentiellement, la méthode de Monte-Carlo se fonde sur la loi forte des grands nombres, ou la loi des grands nombres. La dernière fois nous avions vu un exemple concret, qui était calculer Pi par une pluie aléatoire. Nous verrons que nous pouvons généraliser, vraiment, cet exemple. Le problème fondamental est, comme je l'avais annoncé, l'évaluation d'une intégrale d'une fonction compliquée, je l'ai appelée g. Nous allons commencer par la situation de base qui est évaluer l'intégrale d'une fonction sur l'intervalle [0, 1], g est donnée. Le théorème que nous allons énoncer et étudier, nous explique comment calculer cette intégrale à partir de la loi des grands nombres. Si on se donne une suite (Xn) de variables aléatoires indépendantes, identiquement distribuées, chacune suivant la même loi qu'une variable aléatoire uniforme sur l'intervalle [0, 1]. Si g est une fonction mesurable bornée sur l'intervalle [0,1], penser à une fonction continue, par exemple, sur [0,1]. Alors, l'intégrale de la fonction g sur l'intervalle [0,1], s'obtient comme la limite de cette moyenne. On calcule g(X1), etc, et puis g(Xn), divisé par n. Et cette limite est à prendre au sens de la convergence presque sûre, également au sens de la convergence en probabilité. Donc voilà l'expression d'une intégrale comme une moyenne de variables aléatoires. Faisons la démonstration qui va être une application de la loi forte des grands nombres, ou la loi faible, si on s'intéresse qu'à la convergence en probabilité. On va l'appliquer aux variables aléatoires g(Xi). A cause des hypothèses qu'on a faites, on peut appliquer la loi des grands nombres, g est bornée, on a donc des variables aléatoires qui sont intégrables. Presque sûrement, ou en probabilité, si on calcule la limite de cette moyenne, on trouve l'espérance de g(X). Ça c'est la loi des grands nombres. Dans le cas qui nous intéresse, cette espérance s'écrit comme l'intégrale de g(X) fois la densité de la loi uniforme sur l'intervalle [0,1] fois dx. Et c'est donc simplement l'intégrale 0,1 de g(x)dx. On peut imaginer immédiatement que si on avait une variable aléatoire X, sur, uniforme sur l'intervalle [a,b], on obtiendrait l'intégrale de a à b de g(x)dx, par simple changement de variable. Nous avons envie de généraliser ce que nous allons faire en dimension plus grande que 1. C'est-à-dire calculer l'intégrale de cette forme. Cette fois-ci, g c'est une fonction qui est définie sur R puissance d (R^d) et qui prend des valeurs réelles. On l'a supposée qu'elle est mesurable bornée simplement, qu'on pense à une fonction continue, par exemple. On s'intéresse au calcul de I, qu'on définit comme l'intégrale sur A de g(x)dx. A, pensons à la situation la plus simple, c'est-à-dire un hypercube de côté 2α. En dimension 1, on retrouve bien un intervalle, en dimension 2, ça sera un carré, etc. Donc là, on se place en dimension d quelconque. Comment généraliser ce que nous avons fait précédemment? C'est en fait très simple. On simule une suite de points aléatoires X1, X2,...Xn Cette fois-ci, ce sont plus des nombres mais des points, donc chaque Xi en fait il a plusieurs composantes, il en a d. Et ce qu'on fait c'est que chacune des décomposantes on la prend selon une loi uniforme sur [-α, α]. Et ces, toutes ces variables aléatoires sont indépendantes. On applique à nouveau la loi des grandes nombres, pensons à la version forte, si on s'intéresse à la convergence presque sûre. Si on prend la moyenne des g(Xi), elle converge vers l'espérance de g(X). Maintenant ça, donc ça c'est la loi des grand nombres, donc cette convergence c'est presque sûr. Et écrivons ce que signifie l'espérance de g(X), c'est l'intégrale sur R^d de g(X) par rapport à la densité uniforme sur l'hypercube, et donc on obtient 1 sur 2α puissance d, l'intégrale sur A de g(x)dx. C'est-à-dire ce que nous avons en iii, l'intégrale qui nous intéressait au début. On obtient ça, parce que X c'est un, donc un point qui a des coordonnées, chacune, chaque coordonnée tirée uniformément dans [-α, α]. Et comme c'est des, ces coordonnées sont variables aléatoires independantes, on obtient donc le produit des densités de, des uniformes. On a dx, c'est l'élément de l'intégration dans R^d. Autrement dit, si on définit In comme 2α puissance d fois la moyenne des g(Xi), on vient juste de voir que cette limite quand même tend vers l'infini, elle est égale a l'intégrale qui nous interesse presque sûrement. Je vais donner deux petites illustrations de ce que nous venons de faire. On peut, premièrement, revenir sur l'exemple de Pi que nous avions étudié dans la séance précédente. Dans ce cas-là, si, pour comparer avec ce que nous venons de faire, nous avions d égal 2, α égal 1. A, c'est le carré de cette forme. Et la fonction g c'est l'indicatrice du disque unité. Donc là on retrouve ce que nous avions fait l'autre fois dans un cas particulier. On peut utiliser la méthode de Monte-Carlo pour calculer, par exemple, le volume de la boule unité en dimension 6. Plus généralement, en dimension d quelconque, mais prenons un exemple concret en dimension 6. Si d égal 6 et je prends α égal 1, donc le préfacteur qu'il faut utiliser est 64. A c'est donc cet hypercube. g, simplement l'indicatrice de la boule unité en dimension 6. Ce qui est remarquable c'est que l'algorithme est quasiment le même qu'avant. Au lieu de jeter au hasard 2 points, des points avec 2 coordonnées, il y a simplement, à faire ça avec 6 coordonnées, c'est-à-dire 6 variables aléatoires uniformes sur [-1, 1], indépendantes. Et c'est pareil si on prenait la dimension d, on en aurait d à lancer. Alors dans ce cas-là vous pouvez me dire oui, mais on connait la formule explicite pour le volume d'une boule unité en dimension quelconque. Le point est que c'est donné par une intégrale compliquée, qui est la fonction γ (gamma) de l'air. Et si vous vous intéressez vraiment à la valeur du volume de la boule, si vous faites cette méthode, c'est tres facile à calculer, peu coûteux en temps de calcul. Alors que si vous vouliez utiliser la formule exacte, il faudrait de toute façon évaluer l'intégrale qui apparait dans la fonction γ (gamma) de l'air. Je voudrais faire une remarque sur une amélioration de ce que j'ai dit précédemment, ce qu'on appelle l'échantillonnage préférentiel, que je ne développerai pas. Je vous indique l'idée principale. Donc si on écrit en général, qu'on s'intéresse à l'intégrale de g sur R puissance d (R^d), l'idée c'est est-ce qu'on est capable de composer g, sous la forme d'un produit d'une fonction h fois une fonction f, où f c'est la densité de variables aléatoires (Xi) qu'on sait simuler. L'idée derrière c'est que, au lieu de faire un tirage uniforme, comme on l'a fait précédemment, on peut imaginer tenir compte de certaines informations qu'on a sur la fonction g et rendre bien meilleure la méthode en évitant, par exemple, de jeter des points dans des domaines où on sait que ça sert absolument à rien. Donc ça, c'est tout ce qui s'appelle le domaine de l'échantillonnage préférentiel. La question que vous pouvez vous poser, tout à fait légitimement, est que, pour calculer les intégrales, il existe de nombreuses méthodes, qu'on va, qu'on va appeler déterministes, qui vous permettent, selon la régularité de la fonction g, de, d'avoir un calcul approché d'intégrales qui vous intéressent. Donc, c'est très important de se demander si bien sûr on sait pas intégrer explicitement la fonction qui nous intéresse, est-ce qu'on peut comparer les deux et voir laquelle est avantageuse par rapport à l'autre. Très brièvement, si je reprends l'exemple d'une intégrale sur l'intervalle {0,1], la méthode générale consiste à découper en n segments égaux [0,1]. Et l'approximer sur chaque intervalle de la fonction g et cette approximation va dépendre de la régularité de g. C'est un point important de ces méthodes déterministes. Pour ne citer que deux exemples, que vous connaissez peut-être. Si on utilise la formule dit du trapèze, il faut que g soit au moins 2 fois dérivable. Et vous pouvez montrer que l'erreur que vous commettez par cette approximation c'est 1 sur n carré ,où n, je le rappelle, c'est le nombre de segments que vous utilisez. Si vous voulez faire mieux, faire diminuer l'erreur, vous pouvez faire quelque chose de plus fin. Il y a par exemple la formule de Simpson. La caractéristique de cette méthode c'est qu'elle demande que g soit 4 fois dérivable. Et à ce moment-là, vous avez une erreur 1 sur n^4. Et ensuite il y a toute une série de méthodes que vous pouvez améliorer la précision selon, si vous êtes prêts à avoir des fonctions de plus en plus régulières. Donc ça c'est un premier point. Si vous vous souvenez dans la méthode de Monte-Carlo, nous ne demandons quasiment aucune régularité sur la fonction g. Elle est mesurable bornée, ce qui est quasiment rien à lui demander. Alors, qu'est-ce qui se passe dans la méthode de Monte-Carlo? Ce que nous verrons par la suite c'est que l'erreur, en fait qu'on commet, elle est universelle, elle est en 1 sur racine de n. Mais là, n ce n'est plus le nombre de segments égaux que vous vous donnez pour découper l'intervalle [0,1], c'est le nombre de tirage de la variable uniforme que vous utilisez. Et j'insiste, cette erreur, comme nous le verrons, elle est toujours de cette forme, elle ne dépend absolument pas de la régularité de g, même si elle n'est pas dérivable, vous obtenez la même chose. Bon, ça c'est un premier point. Le deuxième point, c'est que se passe-t-il en dimension plus grande que 1? Puisque y a un autre paramètre important dans ce genre de problème, c'est le fait que, on peut avoir des intégrales dans des espaces de très grandes dimensions. Donc, si on reprend l'exemple de, d'une fonction g qu'on intègre sur l'hypercube de dimension d, qu'est-ce qu'il faut pour employer une méthode déterministe, si vous pensez au cas d égal 2? Il faut un réseau carré de points et il vous faut k puissance 2 points, pour faire la, de la grille sur laquelle vous allez approximer votre fonction. Donc en général il va vous falloir n égal k puissance d points, k points pour chacun des d intervalles [0,1], dans chaque direction. Si vous pensez à la méthode du trapèze, dans chaque intervalle l'erreur va être en 1 sur k carré. C'est ce que nous avons indiqué précédemment. Et on peut se demander maintenant quand est-ce que les deux méthodes vont donner une erreur comparable. Et en particulier, à partir de quel moment la méthode de Monte-Carlo va devenir meilleure. Pour déterminer ça, vous voyez qu'essentiellement on cherche qu'en 1 sur k carré, qu'on peut exprimer en fonction de n, qui est dans ce cas de la méthode du trapèze, 1 sur n puissance 2 divisé par d. On se demande quand ce nombre-là est égal à 1 sur racine de n, qui est l'erreur dans Monte-Carlo. Et on voit que si d égal 4, la méthode de Monte-Carlo devient aussi bonne. Et en particulier, elle devient de mieux en mieux, si la dimension augmente. Donc on a un point capital qui est que en grande dimension et d peut-être des dizaines, voire des milliers, très rapidement, les méthodes déterministes vont donner des erreurs énormes ou correlativement vont demander du temps de calcul énorme. Alors que les méthodes de Monte-Carlo, même si elles ne convergent pas très rapidement, vont être très robustes et vont permettre de calculer des intégrales en dimension très grande. Voilà ce qui termine cette séance, où nous avons vu comment était fondée la méthode de Monte-Carlo. Nous en verrons plus dans les séances prochaines.
