Stratification (Monte-Carlo)

Modèle:Article à sourcer Modèle:Voir homonymes En analyse, la stratification est une méthode de réduction de la variance qui peut être utilisée dans la méthode de Monte-Carlo. L'idée sous-jacente à la stratification est de décomposer le domaine d'intégration en sous-domaines, auxquels on associe une probabilité selon la fonction qu'on souhaite estimer.

Théorie

En Monte-Carlo

On souhaite estimer une quantité G, qui s'exprime sous la forme d'une intégrale :

$G=\underset{a}{\overset{b}{\int }}g(x)\text{d}x$

On considère ici une intégration en dimension 1, mais on peut généraliser à une dimension quelconque.

Le principe de base des méthodes de Monte-Carlo est de voir l'intégrale précédente comme

$G=(b-a)\underset{a}{\overset{b}{\int }}g(x)f_X(x)\text{d}x=(b-a)𝔼(g(X))$

où X est une variable aléatoire uniformément distribuée sur [a ; b] et $f_X(\cdot )=\frac{1}{b-a}$ sa densité.

Si on dispose d'un échantillon $(x_1,x_2,\cdots ,x_N)$, indépendant et identiquement distribué (i.i.d.) selon $𝒰([a;b])$, on peut estimer G par :

${\hat{g}}_N=\frac{(b-a)}{N}\sum _{i=1}^{N}g(x_i)$

Il s'agit d'un estimateur de G non-biaisé (c'est-à-dire que $𝔼({\hat{g}}_N)=G$) et consistant (d'après la loi des grands nombres). Sa variance est :

${\sigma }_{{\hat{g}}_N}^2=\frac{(b-a{)}^2{\sigma }_g^2}{N}$

avec ${\sigma }_g^2$ la variance de la variable aléatoire $g(X)$

${\sigma }_g^2=\frac{1}{(b-a)}\underset{a}{\overset{b}{\int }}{g}^2(x)\text{d}x-{(\frac{1}{b-a}\underset{a}{\overset{b}{\int }}g(x)\text{d}x)}^2$

L'erreur commise est alors une valeur aléatoire, suivant approximativement une loi normale centrée et de variance $\mathrm{V}\mathrm{a}\mathrm{r}(g(X))=\frac{{\sigma }_g^2}{N}$.

Principe de la stratification

L'idée principale de la stratification est de calculer l'intégrale sur une partition de l'intervalle [a ; b], qu'on précisera plus tard :

$G=\underset{a}{\overset{b}{\int }}g(x)\text{d}x=\sum _{k=0}^m\underset{a_k}{\overset{a_{k+1}}{\int }}g(x)\text{d}x,a=a_0<a_1<\dots <a_m<a_{m+1}=b.$

Ainsi, l'intégrale se réécrit comme une somme de probabilités conditionnelles :

$G=(b-a)𝔼(g(X))=(b-a)\sum _{k=0}^m𝔼(g(X\mid X\in [a_k,a_{k+1}]))\mathbb{P}(X\in [a_k,a_{k+1}]).$

En supposant que chaque loi conditionnelle de X soit simulable, et que chaque valeur $p_k=\mathbb{P}(X\in [a_k,a_{k+1}])$ soit connue, on peut donc calculer chaque sous-intégrale par une méthode de Monte-Carlo à NModèle:Ind tirages, soit :

$\mathrm{\forall }k\in \{0;m\},G_k=𝔼(g(X\mid X\in [a_k,a_{k+1}]))\approx \widehat{G_k}=\frac{1}{N_k}\sum _{j=0}^{N_k}g(X_j^{(i)}).$

Estimation de l'erreur

On a ainsi une erreur égale à

$e=G-\sum _{k=0}^m{p}_k\widehat{G_k}=\sum _{k=0}^m{p}_k(G_k-\widehat{G_k}).$

Pour de grands tirages, chaque terme de l'erreur peut être approchée par une loi normale centrée. En observant que :

$\begin{array}{cc}\mathrm{V}\mathrm{a}\mathrm{r}(g(X)\mid X\in [a_k,a_{k+1}])& =𝔼({[g(X)-𝔼(g(X)\mid X\in [a_k,a_{k+1}])]}^2\mid X\in [a_k,a_{k+1}])\\ & =\frac{1}{p_k}𝔼({[g(X)-𝔼(g(X)\mid X\in [a_k,a_{k+1}])]}^{2}11_{[a_k,a_{k+1}]}(X))\\ & =\frac{1}{p_k}𝔼[g(X{)}^{2}11_{[a_k,a_{k+1}]}(X)]-\frac{1}{p_k^2}𝔼{[g(X)11_{[a_k,a_{k+1}]}(X)]}^2,\end{array}$

on peut en déduire que la variance de l'erreur approche ${\sum }_{k=0}^m\frac{p_k^2{\sigma }_k^2}{N_k}$.

Il suffit de vérifier qu'on a bien l'inégalité $\mathrm{V}\mathrm{a}\mathrm{r}(g(X))⩾\mathrm{V}\mathrm{a}\mathrm{r}(\hat{G})$ pour conclure à l'efficacité de la technique de réduction de la variance.

Méthodes de stratification

L'objectif est de réduire le nombre de tirages $N=N_0+\dots +N_m$.

Une méthode simple est la stratification uniforme, réalisée en s'assurant que $p_0=p_1=\dots =p_m$.

On peut également chercher à optimiser la stratification en minimisant la variance conditionnelle. Une étude de la variance montre qu'elle atteint son minimum pour

$\mathrm{\forall }k\in \{0;m\},N_k=N\frac{p_k{\sigma }_k}{\sum _{l=0}^m{p}_l{\sigma }_l}$

soit un minimum égal à ${\sigma }^2=\sum _{k=0}^m{p}_k^2{\sigma }_k^2\frac{\sum _{l=0}^m{p}_l{\sigma }_l}{n{p}_k{\sigma }_k}=\frac{1}{n}{\left(\sum _{k=0}^m{p}_k{\sigma }_k\right)}^2$

Voir aussi

Liens internes

• Méthode de Monte-Carlo

Références

• Modèle:Ouvrage