# 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 Var(g(X))=σ$_g$$^2$/N {\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 p$_k$=P(X∈[a$_k$, a$_{k+1}$]){\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 ∑$_{k=0}$$^m$ p$_k$$^2$σ$_k$$^2$/N$_k$ {\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}$