From 85a3697125dce0f6478115a50b8309e38e97c709 Mon Sep 17 00:00:00 2001
From: Bertrand <bertrand.horel@gmail.com>
Date: Mon, 11 Apr 2016 14:19:30 +0000
Subject: légère suite
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 doc/rapport.tex | 65 ++++++++++++++++++++++++++++++---------------------------
 1 file changed, 34 insertions(+), 31 deletions(-)

(limited to 'doc/rapport.tex')

diff --git a/doc/rapport.tex b/doc/rapport.tex
index 4e77c3b..d6b0d8d 100644
--- a/doc/rapport.tex
+++ b/doc/rapport.tex
@@ -19,46 +19,47 @@ Références : \cite{etore:hal-00192540} \cite{tuffin2004randomization}
 \section{Quasi Monte Carlo randomisé}
 \subsection{Présentation mathématique}
 On suppose qu'on cherche à calculer  
-\begin{equation}
+\begin{equation*}
 I=\int_{[0,1]^s}f(x)dx
-\end{equation}
+\end{equation*}
 Soit $(\xi^{(n)})_{n\in\mathbb{N}}$ une suite à discrépance faible à valeurs dans $[0,1]^s$.
 Au bout de N tirages de cette suite, la méthode de quasi Monte Carlo  nous donnerait une approximation de la valeur de $I$
 par la formule :
-\begin{equation}
-I\approx\frac{1}{N}\sum_{n=1}^Nf(\xi^{(n)})
-\end{equation}
+\begin{equation*}
+\frac{1}{N}\sum_{n=1}^Nf(\xi^{(n)})\overset{p.s}{\to} I
+\end{equation*}
 Le souci de cette méthode est de ne pas pouvoir obtenir d'erreur de l'estimateur facilement. En effet l'inégalité de Koksma–Hlawka nous donne une borne de 
 cette erreur mais nécessite de pouvoir calculer la variation finie de la fonction $f$ ce qui n'est pas toujours possible en pratique. C'est pourquoi on introduit
 la méthode de quasi Monte Carlo randomisé. Elle consiste à rajouter un décalage aléatoire à la suite $(\xi^{(n)})$. Soit $X$ une variable aléatoire
 uniformément distribuée sur ${[0,1]^s}$. On s'intéresse dorénavant à la somme aléatoire :
-\begin{equation}
+\begin{equation*}
 Z=\frac{1}{N}\sum_{n=1}^Nf(\{\xi^{(n)}+X\})
-\end{equation} 
+\end{equation*} 
 où \{$X$\} désigne la partie fractionnaire de $X$.
-L'idée consiste à faire $K$ tirages de $Z$, ce qui consiste à faire K tirages de $X$ vu que la suite $(\xi^{(n)})$ est déterministe, puis de faire
+L'idée consiste à faire $K$ tirages de $Z$, ce qui revient à faire K tirages de $X$ vu que la suite $(\xi^{(n)})$ est déterministe, puis de faire
 une méthode de Monte Carlo classique sur ces $K$ tirages. On a donc :
 \begin{equation}
-\label{eqrqmc}I\approx\frac{1}{K}\sum_{k=1}^KZ_{k}=\frac{1}{K}\sum_{k=1}^K\frac{1}{N}\sum_{n=1}^Nf(\{\xi^{(n)}+X_{k}\})
+\label{eqrqmc}\frac{1}{K}\sum_{k=1}^KZ_{k}=\frac{1}{K}\sum_{k=1}^K\frac{1}{N}\sum_{n=1}^Nf(\{\xi^{(n)}+X_{k}\})\overset{p.s}{\to} I
 \end{equation} 
 Il convient maintenant d'estimer l'avantage de cette méthode par rapport à une technique de Monte-Carlo usuelle, en terme de réduction de variance. 
 On voit dans \eqref{eqrqmc} qu'il nous coûte $NK$ évaluations de la fonction $f$ pour calculer notre estimation de $I$.
 Donc la variance pour la méthode de Monte-Carlo de base serait :
-\begin{equation}
+\begin{equation*}
 \mathrm{Var}(\frac{1}{NK}\sum_{n=1}^{NK}f(X_n))=\frac{1}{NK}\mathrm{Var}(f(X))
-\end{equation}
+\end{equation*}
 Il nous faut la comparer avec :
-\begin{equation}
+\begin{equation*}
 \mathrm{Var}(\frac{1}{K}\sum_{k=1}^K\frac{1}{N}\sum_{n=1}^Nf(\{\xi^{(n)}+X_{k}\}))=\frac{1}{K}\mathrm{Var}(\frac{1}{N}\sum_{n=1}^Nf(\{\xi^{(n)}+X\}))
-\end{equation}
+\end{equation*}
 On a donc réduction de variance si et seulement si : 
-\begin{equation}
+\begin{equation*}
 \mathrm{Var}(\frac{1}{N}\sum_{n=1}^Nf(\{\xi^{(n)}+X\}))<\frac{1}{N}\mathrm{Var}(f(X))
-\end{equation}
+\end{equation*}
 Or dans \cite{Tuffin:1997:VRA:268403.268419} il est montré que pour $f$ une fonction à variations bornées on a : 
 \begin{equation}
-\mathrm{Var}(\frac{1}{N}\sum_{n=1}^Nf(\{\xi^{(n)}+X\}))=O(N^{-2}(log N)^{2s})
+\mathrm{Var}(\frac{1}{N}\sum_{n=1}^Nf(\{\xi^{(n)}+X\}))=O(N^{-2}(\log N)^{2s})
 \end{equation}
+Pour cette classe de fonctions on a une réduction de variance par un facteur de $N / (\log N)^{2s}$.
 
 \subsection{Calcul de vitesse et d'intervalle de confiance}
 On s'interesse maintenant 
@@ -66,32 +67,34 @@ On s'interesse maintenant
 \section{Échantillonnage stratifié}
 \subsection{Présentation mathématique}
 Soit $f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ et $X$ un vecteur aléatoire à $d$ dimensions.
-Comme pour la méthode de quasi Monte Carlo randomisé on suppose qu'on cherche à calculer $\mu=\E(f(X))$.
-On suppose maintenant qu'on divise $\mathbb{R}^{d}$ en $I$ strates appelées $(A_{i})_{1\le i \le n}$ et de telle sorte que 
-$\forall i \in {1,...,i}$ on ait $\mathbb{P}(X\in A_{i})$ qui soit positive. On notera ces probabilités $p_{i}$.
-Si on note maintenant $(X_{i})_{1\le i \le n}$ la suite de variables aléatoires suivant pour chaque $i$ la loi de $X$ sachant $X\in A_{i}$,
+On cherche à calculer $\mu=\E(f(X))$.
+On suppose maintenant qu'on divise $\mathbb{R}^{d}$ en $I$ strates appelées $(A_{i})_{1\le i \le I}$ et de telle sorte que 
+$\forall i \in {1,...,i}$ on ait $\mathbb{P}(X\in A_{i}) > 0$ . On notera ces probabilités $p_{i}$.
+Si on note maintenant $(X_{i})_{1\le i \le I}$ l'ensemble de variables aléatoires suivant la loi conditionnelle de $X$ sachant $X\in A_{i}$,
 on a clairement $\E(f(X)) = \sum_{i=1}^{I}p_{i}\E(f(X_{i}))$.
 Or si on sait simuler chacune des variables $(X_{i})$, on peut estimer chacune des espérances $\E(f(X_{i}))$ par un estimateur de Monte-Carlo usuel
 $\frac{1}{N_{i}}\sum_{j=1}^{N_{i}}f(X_{i}^{j})$ où $N_{i}$ est le nombre de tirages de la variable $X_{i}$. Et donc il vient naturellement :
-\begin{equation}
-\mu\approx\mu_{strat}=\sum_{i=1}^{I}p_{i}\sum_{j=1}^{N_{i}}f(X_{i}^{j})=
-\frac{1}{N}\sum_{i=1}^{I}\frac{p_{i}}{q_{i}}\sum_{j=1}^{q_{i}N}f(X_{i}^{j})
-\end{equation}
-où $N$ désigne le nombre total de tirages, c'est à dire $N=\sum_{i=1}^{I}N_{i}$, et $q_{i}=\frac{{N_{i}}}{N}$ la proportion de tirages dans chacune 
+\begin{equation*}
+\mu_{strat}=\sum_{i=1}^{I}p_{i}\sum_{j=1}^{N_{i}}f(X_{i}^{j})=
+\frac{1}{N}\sum_{i=1}^{I}\frac{p_{i}}{q_{i}}\sum_{j=1}^{q_{i}N}f(X_{i}^{j}) \overset{p.s}{\to} \mu
+\end{equation*}
+où $N$ désigne le nombre total de tirages, c'est à dire $N=\sum_{i=1}^{I}N_{i}$, et $q_{i}=N_i / N$ la proportion de tirages dans chacune 
 des strates. 
 
 On veut maintenant regarder dans quels cas cette méthode peut être utile pour réduire la variance. 
 Si on note $\sigma_{i} = \mathrm{Var}(f(X_{i})) = \mathrm{Var}(f(X)|X\in A_{i})$, la variance de notre estimateur est :
-\begin{equation}
+\begin{equation*}
 \mathrm{Var}(\mu_{strat})=\sum_{i=1}^{I}\frac{p_{i}^{2}\sigma_{i}^2}{N_{i}}=
 \frac{1}{N}\sum_{i=1}^{I}\frac{p_{i}^{2}\sigma_{i}^2}{q_{i}}
-\end{equation}
+\end{equation*}
 Tandis qu'avec un estimateur usuel de Monte-Carlo $\frac{1}{N}\sum_{j=1}^{N}f(X^{j})$, noté $\mu_{mc}$, pour le même nombre $N$ total de tirages, on aurait :
-\begin{equation}
+\begin{equation*}
 \mathrm{Var}(\mu_{mc}) = 
-\frac{1}{N}(\sum_{i=1}^{I}p_{i}(\sigma_{i}^2 + \E^{2}(f(X_{i})))-(\sum_{i=1}^{I}p_{i}\E(f(X_{i})))^{2})
-\end{equation}
-
+\frac{1}{N}\left(\sum_{i=1}^{I}p_{i}(\sigma_{i}^2 + \E^{2}[f(X_{i})])-(\sum_{i=1}^{I}p_{i}\E[f(X_{i})])^{2}\right)
+ \geq \frac{1}{N}\sum_{i=1}^{I}p_i\sigma_i^2
+\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.
 
 \printbibliography
 \end{document}
-- 
cgit v1.2.3-70-g09d2

