Monte-Carlo  (Simulation par méthode de)

L'expression "Simulation de Monte-Carlo" recouvre une série de techniques destinées à résoudre des problèmes complexes mais le plus souvent déterministes par l'introduction d'échantillonnages aléatoires.

On a recours à une simulation de Monte-Carlo lorsque le problème :

• Est trop complexe pour qu'une résolution par voie purement mathématique soit envisageable.
• Est trop volumineux (en particulier, contient un trop grand nombre de variables) pour que les techniques d'approximation numérique puissent conduire à un résultat précis dans un temps acceptable.

Ce genre de situation est très commun dans tous les domaines ayant recours aux mathématiques appliquées : physique, chimie, biologie, economie, finance, sociologie etc...

Intégration unidimensionnelle

A titre d'exemple, nous décrivons ici une des applications les plus simples de simulation de Monte-Carlo : l'intégration d'une fonction dans une région bornée.

Comment calculer l'intégrale entre a et b de la fonction représentée dans l'illustration ci-dessous ?

Si aucune primitive de f(x) n'est connue, l'intégrale ne peut pas être calculée analytiquement. Mais si f(x) peut être facilement calculée en tout point de l'intervalle [a, b], on peut obtenir une bonne approximation de la valeur de cette intégrale par des méthodes numériques.

Il exite de nombreuses méthodes d'intégration numérique. La plus simple (et aussi la moins efficace !) consiste à diviser l'intervalle [a, b] par N rectangles adjacents (image inférieure de l'illustration ci-dessus). La hauteur de chaque rectangle est égale à la valeur de f(x) pour x pris au milieu de la base du rectangle. La somme (algébrique) des aires de ces rectangles est une approximation de l'aire (algébrique) sous la courbe représentant f(x), c'est à dire l'intégrale I recherchée.

Si  f(x) a un comportement suffisamment régulier, et si les rectangles sont suffisamment étroits, alors l'aire ainsi calculée sera une bonne approximation de la valeur de l'intégrale.

-----

Notez que cette approximation de l'intégrale est, à un facteur géometrique de normalisation près, la somme des valeurs de f(x) prises sur des points régulièrement répartis dans la région d'intégration.

Intégrale multiple

Que se passe-t-il si nous utilisons la même approche dans le cas d'une intégrale multiple ? Nous rencontrons deux difficultés :

1. D'abord, la région d'intégration n'est plus définie par une paire de nombres comme précédemment, mais pas une (hyper-) surface fermée dont la forme peut être très compliquée même pour des problèmes simples (voir animation), et impossible à décrire analytiquement.
    
2. La deuxième difficulté est encore plus grave. Revenons un instant à l'intégrale simple, et supposons que nous ayons décidé d'utiliser 100 rectangles. Puis envisageons une intégrale multiple à 100 variables (un nombre très modeste au regard des standards contemporains), et décidons de conserver sur chaque axe la même résolution que dans le cas de l'intégrale simple. Nous devrons alors définir 100¹⁰⁰ hyper-rectangles, un nombre au-delà des capacités des ordinateurs les plus rapides.
   Cette difficulté est absolument universelle, et se retrouve dans toute technique locale, qu'elle soit déterministe ou probabiliste. Elle porte le nom facétieux de "malédiction de la dimensionalité".
   Notez que le nombre de rectangles est choisi essentiellement sur la base considérations portant sur la rapidité avec laquelle la fonction varie dans la région d'intégration. Il n'est donc pas possible de réduire arbitrairement le nombre de rectangles jusqu'à une valeur compatible avec des temps de calcul raisonnables, sous peine de perdre tellement d'information sur la fonction que l'approximation obtenue devienne grossièrement fausse.

Integration par simulation de Monte-Carlo

C'est alors qu'intervient une idée à la fois simple et efficace.

Nous avons remarqué qu'une intégrale n'est, à peu de chose près, que la somme des valeurs de la fonctions prises sur des points régulièrement répartis dans la région d'intégration. Dans cette phrase, remplaçons "régulièrement répartis" par "répartis selon une distribution de probabilité uniforme", et nous avons notre première simulation de Monte-Carlo.

Donc, dans sa version la plus simple, le calcul d'une intégrale :

par simulation de Monte-Carlo procède ainsi :

• Se servir d'une distribution uniforme à n dimensions pour tirer N points dans la région d'intégration (dont nous notons le volume V).
• Additionner tous les f(p_i), multiplier le résultat par V/N.
• Le résultat est une estimation de la valeur de l'intégrale I :
   

Avantages de l'intégration par simulation de Monte-Carlo

Malgré sa simplicité, cette approche atténue les conséquences des deux difficultés précedemment mentionnées.

1. Nous n'avons plus besoin de connaître la forme mathématique de la région d'intégration, mais seulement son volume, qui peut être estimé si nous avons une procédure nous permettant de savoir si un point donné est à l'intérieur de, ou bien à l'extérieur de la région d'intégration, un problème beaucoup plus simple que le précédent (voir animation).
    
2. Mais l'intérêt principal de la l'intégration par simulation de Monte-Carlo réside dans son comportement en grande dimension. Cette question est difficile mais la réponse est simple.
   Considérons une méthode quelconque d'intégration numérique déterministe reposant sur le calcul de valeurs de la fonction sur les nœuds d'une grille dans la région d'intégration. Si nous comparons les performances de cette méthode et de celle de la méthode de Monte-Carlo pour des dimensions de plus en plus grandes, il se trouvera une dimension d au-delà de laquelle la méthode de Monte-Carlo sera plus efficace que la méthode déterministe pour un nombre N donné de tirages. Ceci veut-dire que les valeurs de l'intégrale trouvées par la méthode de MC seront, le plus souvent, plus proches de la valeur vraie de l'intégrale que celle trouvée par l'approximation déterministe.

-----

Quel est le prix à payer pour ces avantages ?

En raison de la nature aléatoire de l'échantillonnage de f(x), la valeur obtenue à la fin d'une simulation est la réalisation d'une variable aléatoire. En d'autres termes, deux simulations de MC sur un même problème, toutes choses égales par ailleurs, produiront deux valeurs différentes. Ces valeurs suivent une distribution de probabilité ayant une certaine variance.

Alors qu'une méthode déterministe d'intégration numérique produit une approximation de la valeur d'une intégrale, une simulation de MC produit une estimation de cette valeur. La différence peut paraître subtile, mais elle est importante : il est souvent possible de trouver une borne supérieure à l'erreur d'une approximation, mais il n'y a en général pas de limite supérieure à l'erreur sur une estimation. Tout ce que nous savons, c'est que pour un ε donné, la probabilité pour que cette erreur soit supérieure à ε peut être rendue aussi petite que l'on veut en augmentant le nombre de tirages (ceci est une conséquence de la Loi des Grands Nombres). Bien sûr, une conséquence pratique de ceci est que les simulations de Monte-Carlo sont toujours très longues.

Animation

Nous illustrons ici le concept d'intégration par simulation de Monte-Carlo sur deux problèmes :

• Estimation de l'aire d'une région irrégulière définie par l'utilisateur dans le carré [0, 1]². Bien que ce problème paraisse très simple, il n'a pas de solution analytique, et même une simulation simple comme celle-ci amène une solution utilisable en pratique.
• Calcul de π. Ce calcul s'accomplit en estimant l'aire d'un disque inscrit dans le carré [0, 1]². Cette approche ne doit bien entendu pas être considérée comme une méthode pratique de calcul de π, mais seulement comme une illustration pédagogique du concept "d'intégration par la méthode de Monte-Carlo".

____________________________________________________________

Voir aussi :