Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.
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.
On souhaite estimer une quantité G , qui s'exprime sous la forme d'une intégrale :
G
=
∫
a
b
g
(
x
)
d
x
{\displaystyle 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
)
∫
a
b
g
(
x
)
f
X
(
x
)
d
x
=
(
b
−
a
)
E
(
g
(
X
)
)
{\displaystyle 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
(
⋅
)
=
1
b
−
a
{\displaystyle f_{X}(\cdot )={\frac {1}{b-a}}}
sa densité.
Si on dispose d'un échantillon
(
x
1
,
x
2
,
⋯
,
x
N
)
{\displaystyle (x_{1},x_{2},\cdots ,x_{N})}
, indépendant et identiquement distribué (i.i.d.) selon
U
(
[
a
;
b
]
)
{\displaystyle {\mathcal {U}}([a;b])}
, on peut estimer G par :
g
^
N
=
(
b
−
a
)
N
∑
i
=
1
N
g
(
x
i
)
{\displaystyle {\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
E
(
g
^
N
)
=
G
{\displaystyle \mathbb {E} ({\hat {g}}_{N})=G}
) et consistant (d'après la loi des grands nombres). Sa variance est :
σ しぐま
g
^
N
2
=
(
b
−
a
)
2
σ しぐま
g
2
N
{\displaystyle \sigma _{{\hat {g}}_{N}}^{2}={\frac {(b-a)^{2}\sigma _{g}^{2}}{N}}}
avec
σ しぐま
g
2
{\displaystyle \sigma _{g}^{2}}
la variance de la variable aléatoire
g
(
X
)
{\displaystyle g(X)}
σ しぐま
g
2
=
1
(
b
−
a
)
∫
a
b
g
2
(
x
)
d
x
−
(
1
b
−
a
∫
a
b
g
(
x
)
d
x
)
2
{\displaystyle \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
V
a
r
(
g
(
X
)
)
=
σ しぐま
g
2
N
{\textstyle \mathrm {Var} (g(X))={\frac {\sigma _{g}^{2}}{N}}}
.
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
=
∫
a
b
g
(
x
)
d
x
=
∑
k
=
0
m
∫
a
k
a
k
+
1
g
(
x
)
d
x
,
a
=
a
0
<
a
1
<
…
<
a
m
<
a
m
+
1
=
b
.
{\displaystyle 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
)
E
(
g
(
X
)
)
=
(
b
−
a
)
∑
k
=
0
m
E
(
g
(
X
∣
X
∈
[
a
k
,
a
k
+
1
]
)
)
P
(
X
∈
[
a
k
,
a
k
+
1
]
)
.
{\displaystyle 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 à Nk tirages, soit :
∀
k
∈
{
0
;
m
}
,
G
k
=
E
(
g
(
X
∣
X
∈
[
a
k
,
a
k
+
1
]
)
)
≈
G
k
^
=
1
N
k
∑
j
=
0
N
k
g
(
X
j
(
i
)
)
.
{\displaystyle \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)}).}
On a ainsi une erreur égale à
e
=
G
−
∑
k
=
0
m
p
k
G
k
^
=
∑
k
=
0
m
p
k
(
G
k
−
G
k
^
)
.
{\displaystyle 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 :
V
a
r
(
g
(
X
)
∣
X
∈
[
a
k
,
a
k
+
1
]
)
=
E
(
[
g
(
X
)
−
E
(
g
(
X
)
∣
X
∈
[
a
k
,
a
k
+
1
]
)
]
2
∣
X
∈
[
a
k
,
a
k
+
1
]
)
=
1
p
k
E
(
[
g
(
X
)
−
E
(
g
(
X
)
∣
X
∈
[
a
k
,
a
k
+
1
]
)
]
2
1
1
[
a
k
,
a
k
+
1
]
(
X
)
)
=
1
p
k
E
[
g
(
X
)
2
1
1
[
a
k
,
a
k
+
1
]
(
X
)
]
−
1
p
k
2
E
[
g
(
X
)
1
1
[
a
k
,
a
k
+
1
]
(
X
)
]
2
,
{\displaystyle {\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é
V
a
r
(
g
(
X
)
)
⩾
V
a
r
(
G
^
)
{\displaystyle \mathrm {Var} (g(X))\geqslant \mathrm {Var} ({\widehat {G}})}
pour conclure à l'efficacité de la technique de réduction de la variance.
L'objectif est de réduire le nombre de tirages
N
=
N
0
+
…
+
N
m
{\displaystyle 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
=
…
=
p
m
{\displaystyle 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
∀
k
∈
{
0
;
m
}
,
N
k
=
N
p
k
σ しぐま
k
∑
l
=
0
m
p
l
σ しぐま
l
{\displaystyle \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 à
σ しぐま
2
=
∑
k
=
0
m
p
k
2
σ しぐま
k
2
∑
l
=
0
m
p
l
σ しぐま
l
n
p
k
σ しぐま
k
=
1
n
(
∑
k
=
0
m
p
k
σ しぐま
k
)
2
{\displaystyle \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}}
(en) Paul Glasserman, Monte-Carlo Methods in Financial Engineering , Springer, 2004 (lire en ligne [PDF] ) , « 4.3: Stratified Sampling »