1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
\documentclass[a4paper, 11pt, french]{article}
\usepackage{babel}
\usepackage{fontspec}
\usepackage{amssymb, amsmath}
\usepackage[pagebackref=true,breaklinks=true,colorlinks=true,backref=false]{hyperref}
\usepackage[capitalize,noabbrev]{cleveref}
\usepackage[backend=biber,style=trad-plain]{biblatex}
\addbibresource{rapport.bib}
\newcommand{\E}{\mathbb{E}}
\begin{document}
\section*{Introduction}
Sujet : Comparer les performances des méthodes de stratification exposées dans \cite{etore:hal-00192540}
et de QMC randomisées exposées dans \cite{tuffin2004randomization} sur les exemples présentés dans \cite{etore:hal-00192540}
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}
I=\int_{[0,1]^s}f(x)dx
\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}
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 consite à 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}
Z=\frac{1}{N}\sum_{n=1}^Nf(\{\xi^{(n)}+X\})
\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
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}\})
\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}
\mathrm{Var}(\frac{1}{NK}\sum_{n=1}^{NK}f(X_n))=\frac{1}{NK}\mathrm{Var}(f(X))
\end{equation}
Il nous faut la comparer avec :
\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}
On a donc réduction de variance si et seulement si :
\begin{equation}
\mathrm{Var}(\frac{1}{N}\sum_{n=1}^Nf(\{\xi^{(n)}+X\}))<\frac{1}{N}\mathrm{Var}(f(X))
\end{equation}
\subsection{Calcul de vitesse et d'intervalle de confiance}
On veut calculer l'espérance : $\E(f(X))=\sum_{i=1}^Ip_if(X_i)$
\begin{equation}
\label{eqesti}\hat{c}=\sum_{i=1}^I\frac{p_i}{N_i}\sum_{j=1}^{N_i}f(X_i^j)=
\frac{1}{N}\sum_{k=1}^I\frac{p_i}{q_i}\sum_{j=1}^{q_iN}f(X_i^j)
\end{equation}
\[a \leq b \]
\begin{center}
\input{table.tex}
\end{center}
\printbibliography
\end{document}
|
