Méthode de Monte-Carlo

On nomme méthode de Monte-Carlo toute méthode visant à calculer une valeur numérique, et utilisant des procédés aléatoires, c'est-à-dire des techniques probabilistes.



Catégories :

Analyse numérique - Algorithme numérique - Probabilités - Physique statistique

Recherche sur Google Images :


Source image : xlase.free.fr
Cette image est un résultat de recherche de Google Image. Elle est peut-être réduite par rapport à l'originale et/ou protégée par des droits d'auteur.

Page(s) en rapport avec ce sujet :

  • par méthode de Monte - Carlo. Voici une autre façon assez simple, quoique sans doute pas la plus efficace, de calculer le nombre... (source : www-sop.inria)
  • Je présenterai le "nested sampling", une nouvelle méthode de Monte Carlo pour..... Bernard Lapeyre : méthodes de Monte Carlo pour l'ingéniérie financière.... (source : perso.telecom-paristech)

On nomme méthode de Monte-Carlo toute méthode visant à calculer une valeur numérique, et utilisant des procédés aléatoires, c'est-à-dire des techniques probabilistes. Le nom de ces méthodes, qui fait allusion aux jeux de hasard pratiqués à Monte-Carlo, a été découvert en 1947 par Nicholas Metropolis [1], et publié pour la première fois en 1949 dans un article co-écrit avec Stanislas Ulam[2].

Les méthodes de Monte-Carlo sont spécifiquement utilisées pour calculer des intégrales en dimensions plus grandes que 1 (en particulier, pour calculer des surfaces, des volumes, etc. ).

La méthode de simulation de Monte-Carlo permet aussi d'introduire une approche statistique du risque dans une décision financière. Elle consiste à isoler un certain nombre de variables-clés du projet telles que le chiffre d'affaires ou la marge... ainsi qu'à leur affecter une distribution de probabilités. Pour chacun de ces facteurs, on effectue la plupart de tirages aléatoires dans les distributions de probabilité déterminées auparavant, pour déterminer la probabilité d'occurrence de chacun des résultats.

Le véritable développement des méthodes de Monte-Carlo s'est effectué, sous l'impulsion de John von Neumann et Stanislas Ulam surtout, lors de la Deuxième Guerre mondiale et des recherches sur la fabrication de la bombe atomique. Surtout, ils ont utilisé ces méthodes probabilistes pour résoudre des équations aux dérivées partielles dans le cadre de la Monte-Carlo N-Particle transport.

Théorie

Nous disposons de l'expression de l'espérance mathématique d'une fonction g de variable aléatoire X, résultant du théorème de transfert, selon lequel

G = E(g(X))=\int_aˆb g(x)f_X(x) \, \mbox{d}x

fX est une fonction de densité sur le support [a;b]. Il est habituel de prendre une distribution uniforme sur [a;b] :

f_X(x) = \frac{1}{b-a}

Ceci peut être étendu aux probabilités discrètes en sommant grâce à une mesure ν discrète, de type Dirac.

L'idée est de produire un échantillon (x1, x2, ..., xN) de la loi X (donc selon la densité fX) sur le support [a;b], et de calculer un nouvel estimateur dit de Monte-Carlo, à partir de cet échantillon.

La loi des grands nombres suggère de construire cet estimateur à partir de la moyenne empirique :

\tilde{g_N} = \frac{1}{N} \sum_{i=1}ˆ{N} g(x_i),

qui se trouve être, d'autre part, un estimateur sans biais de l'espérance.

Ceci est l'estimateur de Monte-Carlo. Nous voyons quoiqu'en remplaçant l'échantillon par un ensemble de valeurs prises dans le support d'une intégrale, et de la fonction à intégrer, nous pouvons par conséquent construire une approximation de sa valeur, construite statistiquement.

Cette estimation est sans-biais, dans le sens où

E(\tilde{g_N})= G = E(g(X))

Il faut aussi quantifier la précision de cette estimation, via la variance de \tilde{g_N}. Si l'échantillon est supposé iid, cette variance est estimée avec la variance empirique

 Sˆ2_{g(X)} = \frac{1}{N} \sum_{i=1}ˆN (g(x_i) - \tilde{g_N})ˆ2 \simeq \sigma_gˆ2

avec

\sigma_gˆ2= E(gˆ2(X)) - E(g(X))ˆ2 = \int_{\Omega} gˆ2(x) f_X(x) \,\mbox{d} x - Gˆ2


Par le théorème de la limite centrale, on sait que la variable :

Z := \frac{\tilde{g_N}-G}{\sigma_g / \sqrt{N}} \equiv \sqrt{N} \; \left(\frac{\tilde{g_N}-G}{\sigma_g}\right)

qui est centrée et réduite, suit approximativement la loi normale centrée réduite, ou loi de Gauss. Il est alors envisageable de construire des intervalles de confiance, ce qui permet d'encadrer l'erreur commise en remplaçant G par \tilde{g_N}. Si cette erreur est dénotée en, alors pour un niveau de risque α donné, on a :

|e_n| \leq z_{\alpha/2}\frac{\sigma_g}{\sqrt{N}}

avec probabilité 1 − α. Le réel zα / 2 est le quantile de la loi normale centrée réduite. A titre d'exemple, au niveau de risque \alpha = 5 \%, on trouve dans les tables zα / 2 = 1, 96 et l'erreur est majorée par 1,96 \sigma_g/\sqrt{N}. Cette méthode permet par conséquent de quantifier l'erreur commise, à condition d'estimer σg par sa contre-partie empirique

\hat{\sigma}_g = \sqrt{Sˆ2_{g(X)}}.

On voit mais aussi l'erreur est de l'ordre de N − 1 / 2 : par exemple, multiplier la taille de l'échantillon par 100 sert à diviser par 10 l'erreur d'estimation.

Il est à noter qu'en pratique, \hat{\sigma}_g n'est pas connu et doit être estimé ; comme précisé plus-haut, on peut utiliser sa contre-partie empirique. Diverses méthodes, dites techniques de réduction de la variance, permettent de perfectionner la précision — ou de diminuer le temps de calcul — en remplaçant g (X) par une autre variable aléatoire. Ces techniques rentrent généralement dans l'une des classes suivantes : l'échantillonnage préférentiel, les variable de contrôle, la variable antithétique, la stratification (Monte-Carlo) et le conditionnement (Monte-Carlo).

Exemples

Résolution du Problème du voyageur de commerce

La résolution du problème du voyageur de commerce est complexe, du fait de la complexité du problème, l'emploi de méthodes d'optimisation probabilistes peut s'avérer efficace pour obtenir une approximation de la meilleure solution, en un temps plus court que pour des méthodes déterministes.

Détermination de la valeur de π (pi)

Cette méthode est proche de l'expérience de l'aiguille de Buffon.

Soit un point de coordonnées, où et.

On tire aléatoirement les valeurs de et.

Si alors le point appartient au disque de centre de rayon 1.

La probabilité que le point appartienne au disque est π/4.

En faisant le rapport du nombre de points dans le disque comparé au nombre de tirages on obtient une approximation du nombre π/4 si le nombre de tirages est grand.

représentation du calcul de la valeur de pi par rapport du nombre de points aléatoires étant contenus dans un quart de cercle, l'ensemble des possible étant un carré de côté R

Détermination de la superficie d'un lac

Cet exemple est un classique en vulgarisation de la méthode de Monte-Carlo. Soit une zone rectangulaire ou carrée dont les côtés sont de longueur connue. Au sein de cette aire se trouve un lac dont la superficie est inconnue. Grâce aux mesures des côtés de la zone, on connaît l'aire du rectangle. Pour trouver l'aire du lac, on demande à une armée de tirer X coups de canon de manière aléatoire sur cette zone. On compte ensuite le nombre N de boulets qui sont restés sur le terrain ; on peut ainsi déterminer le nombre de boulets qui sont tombés dans le lac : X-N. Il suffit ensuite d'établir un rapport entre les valeurs :

\frac{\mathrm{superficie}_{∼\mathrm{terrain}}}{\mathrm{superficie}_{∼\mathrm{lac}}} = \frac{X}{X-N}
\Longrightarrow \qquad \mathrm{superficie}_{∼\mathrm{lac}} = \frac{(X-N)}{X} \ \times \ \mathrm{superficie}_{∼\mathrm{terrain}}

A titre d'exemple, si le terrain fait 1000 m2, que l'armée tire 500 boulets et que 100 projectiles sont tombés dans le lac, alors une estimation de la superficie du plan d'eau est de : 100*1000/500 = 200 m2.

Estimation de la surface du lac grâce à des tirs d'artillerie aléatoires

La qualité de l'estimation se perfectionne en augmentant le nombre de tirs et en s'assurant que les artilleurs ne visent pas forcément le même lieu mais couvrent bien la zone. Cette dernière remarque est à mettre en parallèle avec la qualité du générateur aléatoire qui est essentielle pour avoir de bons résultats dans la méthode de Monte-Carlo. Un générateur biaisé est comme un canon qui tire toujours au même lieu : les informations qu'il apporte sont réduites.

Application au modèle d'Ising

Article détaillé : Modèle d'Ising.

Notes et références

  1. Nicholas Metropolis, «The Beginning of the Monte Carlo Method», dans Los Alamos Science, no 15, 1987, p.  125-130 [texte intégral] 
  2. Nicholas Metropolis et Stanislas Ulam, «The Monte Carlo Method», dans Journal of the American Statistical Association, vol.  44, no 247, septembre 1949, p.  335-341 [texte intégral] .

Voir aussi

Codes de simulation utilisant des méthodes de Monte-Carlo

Bibliographie

Liens externes

Recherche sur Amazone (livres) :



Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/M%C3%A9thode_de_Monte-Carlo.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 10/03/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu