Qu'est-ce que la méthode de Monte Carlo ?
La méthode de Monte-Carlo est une méthode pour estimer une espérance par simulation.
1) Qu'est-ce que la méthode de Monte Carlo précisément ?
Soit une fonction et une variable aléatoire telle que existe, i.e. telle que la variable aléatoire est intégrable.
La méthode de Monte Carlo consiste à simuler un grand nombre de fois, de manière indépendante, X, fournissant une liste de valeur . Alors l'espérance , inconnue, est approximativement égale à
2) Pourquoi est-ce que cela converge ?
Pour justifier proprement la méthode il faut voir chacun des N tirages comme une variable aléatoire de même loi que X. Ainsi j'appelle le premier tirage, le second...
Il s'agit bien ici de variables aléatoires et non de valeurs : peut prendre toutes les valeurs possible de , de même pour ...
La liste étant une réalisation possible de mon échantillon (plus de détails ici)
La loi des grands nombre garantit que la moyenne empirique
converge presque sûrement vers l'espérance inconnue .
"Converge presque sûrement" signifie que, toutes les simulations possibles donnerons une moyenne qui tends vers la valeur voulue sauf un ensemble négligeable (au sens mathématique du terme.
3) Quelle est l'erreur commise ?
La convergence de la méthode de Monte Carlo est garantie par la loi des grands nombre. Mais on peut aller plus loin et avoir une estimation de l'erreur commise. Comment ? Grâce au Théorème Central Limite !
Nous avons vu que les sont des variables aléatoires indépendantes et identiquement distribuées. Supposons qu'elles soit de variance finie. Ainsi le TCL nous garantit que "ressemble" à une loi normale.
Plus précisément converge en loi vers une loi Normale centrée de variance celle de que l'on note .
Cela signifie que, quand N tends vers l'infini, où est la fonction de répartition d'une loi normale centrée réduite.
En conséquence, pour N grand, on a
Cela est très classiquement utilisé de la manière suivante :
En clair, pour N grand, pour environ 95% des tirages possible, on aura la moyenne empirique qui à moins de de l'espérance voulue.
Reste une difficulté : est une valeur généralement non connue. On peut cependant l'estimer par l'écart-type des . Les résultats évoqués ci dessus reste vrais grâce au lemme de Slutsky.
4) Exemples d'utilisation
4.1) estimation de valeur d'une politique de gestion
Supposons que je gère un stock de produit face à une demande aléatoire, sur un an, au pas de temps hebdomadaire. Si j'ai de la demande et du stock je la sers, si je n'ai plus de stock la demande est supposée perdu.
Avoir des produits en stock a un coût (assurance, casse, cash immobilisé...), ne pas servir une demande a un coût (mécontentement client), passer une commande de renouvellement a un coût...
J'ai décidé d'une politique de gestion a priori (typiquement : passer commande d'une quantité fixe quand j'atteint un certain stock minimum) et je voudrais évaluer le coût de cette stratégie.
Supposons la demande indépendantes d'une semaine à l'autre, et pouvant prendre 10 valeurs par semaine.
Alors calculer l'espérance exacte de mon coût nécessite de faire la moyenne de 10^52 valeurs ! Ce nombre est titanesque (largement supérieur au nombre d'atome dans l'univers). Donc même dans un cas purement discret calculer l'espérance exacte est numériquement hors d'atteinte.
Heureusement on va pouvoir utiliser Monte Carlo pour estimer l'espérance du coût. Et ce de manière très simple :
- simuler une année et calculer le coût cumulé sur l'année, qu'on note
- recommencer fois.
- calculer la moyenne des N couts ainsi que leur écart-type
- Il y a environ 95% de chance que la vraie espérance, inconnue, soit dans
4.2) Calcul d'intégrale par Monte Carlo
L'une des grandes réussite de la méthode de Monte Carlo est la calcul d'intégrale en grande dimension.
En effet, si est une variable aléatoire de densité alors l'espérance
est donnée par .
Pour calculer ce genre d'intégrale, quand une formule analytique n'existe pas, on peut utiliser des méthodes d'intégration numériques qui discrétise l'espace et approxime "l'aire sous la courbe" par des rectangle, trapèze ou autres approche plus compliquées. Malheureusement toutes les méthodes d'intégration numériques sont sensible à la dimension : pour atteindre une erreur voulue le nombre de point de discrétisation augmente (dramatiquement) avec le nombre de dimension. Au contraire Monte Carlo est insensible à la dimension, et est donc la méthode numérique par défaut dès qu'on dépasse la dimension 4 ou 5...
Exemple pratique : calculer le volume d'une boule en dimension n.
a) initialiser un compteur à count 0
b) tirer n valeurs uniforme sur [0,1], lnoté ce qui nous donne un vecteur de dimension n tiré uniformément dans .
c) calculer la norme au carré du vecteur : , si elle est inférieure à 1 ajouter 1 au compteur
d) répéter b) et c) N fois (au moins 1000).
p=Count/N nous donne l'approximation du volume du quartier de boule ayant des coordonnées positive
et il y a 95% de chance que cette approximation soit à moins de du vrai volume
(on peut améliorer par ).
Le volume total estimé de la sphère étant naturellement
Un petit code qui simule cela https://repl.it/repls/WhichDeafeningPro ... ro#main.py
On peut y observer :
1) que l'estimation est proche de la valeur réelle
2) que l'estimation est aléatoire (à chaque fois que je relance une simulation j'ai une valeur différente)
3) que la vraie valeur peut être hors de l'intervalle d'incertitude (cela arrive en gros 5% du temps). Si on veut moins d'incertitude il suffit de prendre un intervalle plus grand, par exemple 3 écarts-type donnerons 1% environ (voire la section 2 plus haut).
P.S: si toute cette explication est de mon cru elle est néanmoins fort classique. Si quelqu'un voit une erreur qu'il n'hésite pas à la signaler.