Stratification (Monte-Carlo)

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=\int _{a}^{b}g(x)\,{\mbox{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)\int _{a}^{b}g(x)f_{X}(x)\,{\mbox{d}}x=(b-a)\,\mathbb {E} (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 ${\mathcal {U}}([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 $\mathbb {E} ({\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)}}\int _{a}^{b}g^{2}(x)\,{\mbox{d}}x-\left({\frac {1}{b-a}}\int _{a}^{b}g(x)\,{\mbox{d}}x\right)^{2}$

L'erreur commise est alors une valeur aléatoire, suivant approximativement une loi normale centrée et de variance ${\textstyle \mathrm {Var} (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=\int _{a}^{b}g(x)\,{\mbox{d}}x=\sum _{k=0}^{m}\int _{a_{k}}^{a_{k+1}}g(x)\,{\mbox{d}}x,\quad a=a_{0}<a_{1}<\ldots <a_{m}<a_{m+1}=b.$

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

$G=(b-a)\,\mathbb {E} (g(X))=(b-a)\,\sum _{k=0}^{m}\mathbb {E} (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 ${\textstyle 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 à N_k tirages, soit :

$\forall k\in \{0;m\},G_{k}=\mathbb {E} (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{aligned}\mathrm {Var} (g(X)\mid X\in [a_{k},a_{k+1}])&=\mathbb {E} \left(\left[g(X)-\mathbb {E} \left(g(X)\mid X\in [a_{k},a_{k+1}]\right)\right]^{2}\mid X\in [a_{k},a_{k+1}]\right)\\&={\frac {1}{p_{k}}}\mathbb {E} \left(\left[g(X)-\mathbb {E} \left(g(X)\mid X\in [a_{k},a_{k+1}]\right)\right]^{2}1\!\!1_{[a_{k},a_{k+1}]}(X)\right)\\&={\frac {1}{p_{k}}}\mathbb {E} \left[g(X)^{2}1\!\!1_{[a_{k},a_{k+1}]}(X)\right]-{\frac {1}{p_{k}^{2}}}\mathbb {E} \left[g(X)1\!\!1_{[a_{k},a_{k+1}]}(X)\right]^{2},\end{aligned}}$

on peut en déduire que la variance de l'erreur approche ${\textstyle \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 {Var} (g(X))\geqslant \mathrm {Var} ({\widehat {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}+\ldots +N_{m}$.

Une méthode simple est la stratification uniforme, réalisée en s'assurant que $p_{0}=p_{1}=\ldots =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

$\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}}{np_{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

• (en) Paul Glasserman, Monte-Carlo Methods in Financial Engineering, Springer, 2004 (lire en ligne [PDF]), « 4.3: Stratified Sampling »