From b2ef5772372a85717f0eb5d79576fd035bf15adb Mon Sep 17 00:00:00 2001 From: Bertrand Date: Fri, 15 Apr 2016 13:23:27 +0200 Subject: explication algo stratified sampling --- doc/rapport.tex | 20 ++++++++++++++++++++ 1 file changed, 20 insertions(+) (limited to 'doc') diff --git a/doc/rapport.tex b/doc/rapport.tex index d6b0d8d..9246662 100644 --- a/doc/rapport.tex +++ b/doc/rapport.tex @@ -95,6 +95,26 @@ Tandis qu'avec un estimateur usuel de Monte-Carlo $\frac{1}{N}\sum_{j=1}^{N}f(X^ \end{equation*} On peut donc constater que si on décide de poser $q_i = p_i$, $\mathrm{Var}(\mu_{strat})$ atteindra la borne inférieure trouvée pour $\mathrm{Var}(\mu_{mc})$. Mais on peut trouver un choix de $q_i$ plus optimal en terme de réduction de variance. +En effet : +\begin{equation*} +\mathrm{Var}(\mu_{strat})=\frac{1}{N}\sum_{i=1}^{I}\frac{p_i^2\sigma_i^2}{q_i}=\frac{1}{N}\sum_{i=1}^I(\frac{p_i\sigma_i}{q_i})^2q_i +\geq\frac{1}{N}(\sum_{i=1}^I\frac{p_i\sigma_i}{q_i}q_i)^2 +\end{equation*} +Si +\begin{equation} +\label{eqqi} +\forall 1\geq i \geq I, q_i=\frac{p_i\sigma_i}{\sum_{j=1}^Ip_j\sigma_j} +\end{equation} +${Var}(\mu_{strat})$ atteindra la borne inférieure trouvée précédemment. Maintenant qu'on a décrit le principe de la méthode de l'échantillonnage stratifié, +et qu'on a trouvé quelle est la proportion optimale de tirages à faire par strates, intéressons nous à l'algorithme pour implémenter ce modèle. + +\subsection{Description de l'algorithme} +On a vu dans la section précédente que les $q_i$ optimaux dépendent de la suite $(\sigma_i)_{1\geq i\geq I}$ qui sont les variances conditionnelles de $X$ +sachant $X\in A_{i}$. Mais si ces variances sont inconnues il nous faut les estimer. On ne peut trouver la répartition optimale de tirages à faire par strates +du premier coup. L'idée de l'algorithme consiste donc à faire plusieurs étapes. On commence par tirer un nombre $N_1$ assez restreint de variables $(X_{i})_{1\le i \le I}$ +en choisissant une répartition déterministe, par exemple la répartition uniforme $q_i=\frac{N_1}{I}$ ce qui nous donnera un premier estimateur de $\mu=\E(f(X))$ mais +surtout les premiers estimateurs de $\sigma_{i}$. Ensuite on pourra tirer un nombre $N_2 > N_1$ de $(X_{i})$ avec une de nouveaux $q_i$ donnés par \eqref{eqqi} +ce qui nous donnera un nouvel estimateur de $\mu$ (en utilisant les $N_1 + N_2$ premières valeurs) puis de nouveaux $q_i$ plus précis, et ainsi de suite. \printbibliography \end{document} -- cgit v1.2.3-70-g09d2