Rappel sur la méthode de Monte-Carlo

Section 1.2 Rappel sur la méthode de Monte-Carlo

Le terme méthodes de Monte-Carlo, désigne un ensemble de méthodes visant à calculer une valeur numérique approchée en utilisant des procédés aléatoires, c'est-à-dire des techniques probabilistes. Ces méthodes sont très utilisées pour approcher ces intégrales, approcher des équations issues de la physique des particules, etc.

La méthode de Monte-Carlo est une application direct de la loi des grands nombres Théorème 1.8 La méthode de Monte Carlo permet d'approcher des intégrales. En effet

\begin{equation*} \int_{\Omega}f(x)dx = \int_{\Omega}f(x)u_{\Omega}(x)dx \end{equation*}

avec $u_{\Omega}(x)$ la densité de la loi uniforme sur $\Omega$ et donc

\begin{equation*} \int_{\Omega}f(x)dx = \mathbb{E}_{u}[f(X)] \end{equation*}

avec $X$ une variable aléatoire uniforme. Cette espérance peut être approchée par une moyenne empirique en suivant le résultat de la loi des grands nombres Théorème 1.8. On obtient donc:

\begin{equation*} \int_{\Omega}f(x)dx \approx \frac{1}{n}\sum_{i=1}^nf(x_i) \end{equation*}

avec $x_i$ des points tirés selon une loi uniforme. Approcher notre intégrale par une somme de points tirés aléatoirement selon une loi uniforme correspond à la méthode de Monte-Carlo pour l'estimation d'intégral.

L'estimation d'erreur de la méthode de Monte-Carlo est obtenue par Théorème 1.9.

Proposition 1.16.

Soit une variable aléatoire $X$ de loi $p$ tel que $\mathbb{E}[\mid X\mid^2]\lt \infty$ . On se donne $(X_n)_{n\in \N^*}$ une suite de v.a.r. i.i.d. On note $\sigma^2$ la variance de $X$ alors on a

\begin{equation*} \mathbb{E}[(\bar{X}_n-\mathbb{E}[X])^2]=\frac{\sigma^2}{n} \end{equation*}

Preuve.

En construction

La méthode de Monte-Carlo sous la forme précédente demande donc de stocker l'ensemble des échantillons pour calculer l'espérance empirique. La méthode de Monte-Carlo permet naturellement d'intégrer une fonction. On peut aussi utiliser une formule de récurrence:

\begin{equation*} \bar{E}_{n+1}= \bar{E}_{n}+\frac{1}{n+1}(g(X_{n+1})- \bar{E}_{n}) \end{equation*}

Cette formule est utilisée pour limiter le stockage. On en tire un algorithme plus général.

Proposition 1.17.

Soit une variable aléatoire $X$ de moyenne $E =\mathbb{E}[X]$ inconnu que l'on souhaite estimer. Soit $(X_1,...,X_n)$ des réalisations indépendantes suivant la loi de $X\text{.}$ On peut construire un estimateur par un algorithme itératif

\begin{equation*} \bar{E}_{n+1}= (1-\alpha_n)\bar{E}_{n}+\alpha_n g(X_{n+1}) \end{equation*}

ou $\alpha_n$ est appelé un pas d'apprentissage. La convergence presque sûrement est assuré si

$\alpha_n \geq 0\text{,}$
$\sum_{i\geq 0} X_i = +\infty\text{,}$
$\sum_{i\geq 0} X_i^2 \leq +\infty\text{,}$

Preuve.

Admis.

On remarque que si $\alpha_n=\frac{1}{n+1}$ on retombe sur la moyenne empirique et la méthode de Monte-Carlo. La convergence est donc assurée par la loi des grands nombres dans ce cas précis.

On a vu que l'erreur commise dépend de la variance de notre variable aléatoire. Afin d'améliorer la méthode, il faut réduire la variance. On peut citer deux méthodes classiques de réduction de variance. La méthode de d'échantillonnage préférentiel et celle de variable de contrôle. On va se concentrer sur la première. On se propose d'écrire la méthode en discret, mais elle s'écrit naturellement pour des variables aléatoires continues. On commence par écrire l'espérance qu'on souhaite calculer avec $X$ une variable aléatoire suivant une loi de probabilité $p\text{:}$

\begin{equation*} \mathbb{E}[g(X)] = \sum_{i=1}^m g(x_i)p(x_i) = \sum_{i=1}^m \frac{g(x_i)p(x_i)}{\tilde{p}(x_i)} \tilde{p}(x_i) =\mathbb{E}\left[ \frac{g(Y)p(Y)}{\tilde{p}(Y)}\right] \end{equation*}

avec $Y$ une variable aléatoire suivant une loi de probabilité $\tilde{p}\text{.}$ Une fois cette égalité écrire il y a deux possibilités: appliquer la méthode de Monte-Carlo sur la 1ère espérance (avec la loi $X$) ou sur la dernière (avec la loi $Y$). Si on arrive à construire une probabilité $\tilde{p}$ tel que

\begin{equation*} \mathbb{V}\left[\frac{g(Y)p(Y)}{\tilde{p}(Y)} \right] \leq \mathbb{V}[g(X)] \end{equation*}

alors appliquer la méthode de Monte-Carlo à la seconde espérance permettra une convergence plus rapide. La loi de probabilité $\tilde{p}$ s'appelle la loi/fonction d'importance. Trouver cette loi de probabilité est l'enjeu de la méthode et dépend souvent du problème. On propose un exemple dans le cas continu. On veut calculer:

\begin{equation*} \int_0^1 cos\left(\frac{x}{2}\pi\right) dx \end{equation*}

L'approche classique propose d'utiliser $g(x)=cos\left(\frac{x}{2}\pi\right)$ et une loi uniforme de densité de probabilité $f(x)=1\text{.}$ La fonction d'importance est notée $\tilde{f}$ et elle correspond la densité de probabilité de la nouvelle variable aléatoire. Un choix intéressant serait de prendre $\tilde{f}(x)=2(1-x)$ qui correspond au développement limité de la fonction $g(x)\text{.}$ Si $X$ est donnée par une loi uniforme:

\begin{equation*} Y = 1 -\sqrt{X} \end{equation*}

suit la loi $\tilde{f}(x)\text{.}$ En pratique cela permet de diminuer un facteur $10$ la variance.