From a06300b897b80c3979ee7b5a4ad35f3ce8e38027 Mon Sep 17 00:00:00 2001 From: Guillaume Horel Date: Fri, 22 Apr 2016 17:14:22 -0400 Subject: plus de changements --- doc/rapport.tex | 46 ++++++++++++++++++++++------------------------ 1 file changed, 22 insertions(+), 24 deletions(-) (limited to 'doc') diff --git a/doc/rapport.tex b/doc/rapport.tex index 41f1d84..aae5e00 100644 --- a/doc/rapport.tex +++ b/doc/rapport.tex @@ -64,7 +64,7 @@ Or dans \cite{Tuffin:1997:VRA:268403.268419} il est montré que pour $f$ une fon 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 à la convergence vers la loi normale de notre estimateur. On rappelle d'abord le cas d'une méthode de Monte-Carlo classique. +On s'intéresse maintenant à la convergence vers la loi normale de notre estimateur. On rappelle d'abord le cas d'une méthode de Monte-Carlo classique. Soit $X$ une variable aléatoire, on note $\mu = \E[f(X)]$ son espérance qu'on cherche à calculer et $\sigma$ son écart type. Alors si les $(X_n)_{1\leq n\leq N}$ sont $N$ tirages de la variable $X$, $\bar{X}_N=\frac{1}{N}\sum_{n=1}^Nf(X_n)$ sera notre estimateur de $\mu$ et on aura l'intervalle de confiance asymptotique usuel pour $\mu$ de la forme : $[\bar{X}_N-c_{\alpha}\frac{\sigma}{\sqrt{N}},\bar{X}_N+c_{\alpha}\frac{\alpha}{\sqrt{N}}]$ @@ -99,7 +99,7 @@ Alors que Tuffin trouve : \end{equation*} ce qui me semble être une erreur. Si on veut comparer les demi-tailles des intervalles de confiance, on voit que l'intervalle de Tuffin rajoute $\frac{C\beta}{\sigma^2N}$ à -l'intervalle habituel assymptotique tandis que je trouve un intervalle possiblement égal à $\mathbb{R}$ tout entier pour des petites valeurs de $N$. +l'intervalle habituel asymptotique tandis que je trouve un intervalle possiblement égal à $\mathbb{R}$ tout entier pour des petites valeurs de $N$. C'est pourquoi dans les applications ultérieures, j'utilise l'intervalle classique $[\bar{X}_N-c_{\alpha}\frac{\sigma}{\sqrt{N}}, \bar{X}_N+c_{\alpha}\frac{\alpha}{\sqrt{N}}]$. @@ -137,7 +137,7 @@ $\sum_{i=1}^{I}p_i = 1$) on a : \begin{equation*} \frac{1}{N}\sum_{i=1}^{I}p_i\,\E^{2}[f(X_{i})] \geq \frac{1}{N}(\sum_{i=1}^{I}p_i\,\E[f(X_{i})])^2 \end{equation*} -Si on pose $q_i = p_i$, $\mathrm{Var}(\mu_{strat})$ atteindra la borne inférieure trouvée pour $\mathrm{Var}(\mu_{mc})$. +Si on pose $q_i = p_i$, $\mathrm{Var}(\mu_{strat})=\frac{1}{N}\sum_{i=1}^{I}p_i\sigma_i^2$ qui est 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, toujours par l'inégalité de Jensen avec cette fois la suite des $q_i$ vue comme une probabilité discrète, on a : @@ -165,15 +165,15 @@ ce qui nous donnera un nouvel estimateur de $\mu$ (en utilisant les $N_1 + N_2$ Essayons maintenant de décrire plus précisément comment calculer la proportion de tirages à allouer par strates. En effet, en pratique il y a deux contraintes en plus de la formule qui nous donne la suite des $q_i$. Tout d'abord le nombre de tirages doit évidemment être entier, et de plus il doit y avoir au moins -un tirage par strate, sinon on ne peut garantir la convergence des variances conditionelles empiriques $\hat{\sigma}_i$ vers la vraie valeur. -Notons $I$ le nombre de strates, $\hat{\sigma}_i^k$ l'estimateur à l'étape $k$ de la variance de $X$ sachant que $X \in A_i$, $N_i^k$ le nombre total de tirages effectués de l'étape 0 à l'étape $k$ dans la $i^{\textrm{ème}}$ strate et $M_i^k$ le nombre de tirages à effectuer à +un tirage par strate, sinon on ne peut garantir la convergence des variances conditionnelles empiriques $\hat{\sigma}_i$ vers la vraie valeur. +Notons $I$ le nombre de strates, $\hat{\sigma}_i^k$ l'estimateur de la variance de $X$ sachant que $X \in A_i$ à l'étape $k$ , $N_i^k$ le nombre total de tirages effectués de l'étape 0 à l'étape $k$ dans la $i^{\textrm{ème}}$ strate et $M_i^k$ le nombre de tirages à effectuer à l'étape $k$ dans la strate $i$ qui est donc $M_i^k = N_i^k - N_i^{k-1}$. \paragraph{Étape 1 :} \begin{equation*} -\forall i \in I, \quad M_i^1 = 1+p_iN_1 +\forall i \in I, \quad M_i^1 = 1+p_i(N_1-I) \end{equation*} -C'est l'allocation proportionelle plus un, pour garantir au moins un tirage par strate. Si les $M_i^1$ ne sont pas entiers, voir la méthode ci-dessous pour les arrondir. +C'est l'allocation proportionelle modifié de 1, pour garantir au moins un tirage par strate. Si les $M_i^1$ ne sont pas entiers, voir la méthode ci-dessous pour les arrondir. \paragraph{Étape k :\\} On commence d'abord par calculer les $\hat{\sigma}_i^{k-1}$ avec les tirages de l'étape précédente. \begin{equation*} @@ -181,15 +181,15 @@ On commence d'abord par calculer les $\hat{\sigma}_i^{k-1}$ avec les tirages de \end{equation*} Ensuite on peut calculer les $M_i^k$. On sait qu'il nous faut au moins un tirage par strate on peut donc écrire $M_i^k$ de sous la forme $m_i^k + 1$ avec $m_i^k \in \mathbb{N}$ et comme on a $M_i^k = N_i^k - N_i^{k-1}$ il vient $\sum_{i=1}^Im_i^k=N^k-N^{k-1}-I$. Les auteurs de l'article proposent deux méthodes -pour calculer les $m_i^k$, je n'en ai utlisé qu'une seule que je vais présenter ici. +pour calculer les $m_i^k$, je n'en ai utilisé qu'une seule que je vais présenter ici. -D'après \eqref{eqqi}, on connait la proportion optimale à faire par strates en fonction des $\hat{\sigma}_i^{k-1}$. Sachant de plus que $\sum_{i=1}^Iq_i=1$, +D'après \eqref{eqqi}, on connaît la proportion optimale à faire par strates en fonction des $\hat{\sigma}_i^{k-1}$. Sachant de plus que $\sum_{i=1}^Iq_i=1$, on voit qu'un choix de $m_i^k$ idéal serait : \begin{equation*} \forall i \in I, \quad (m_i^k)^* = \frac{p_i\hat{\sigma}_i^{k-1}}{\sum_{j=1}^Ip_j\hat{\sigma}_j^{k-1}}(N^k-N^{k-1}-I) \end{equation*} Pour que les $m_i^k$ soient les entiers au plus près de leurs valeurs optimales, tout en assurant que leur somme ne dépasse pas le nombre total de tirages à faire -à l'étape $k$, Étoré et Jourdain proposent la méthode suivante. On pose d'abort $m_1^k =\floor{(m_1^k)^*}$. Puis pour chaque $i>1$ on pose : +à l'étape $k$, Étoré et Jourdain proposent la méthode suivante. On pose d'abord $m_1^k =\floor{(m_1^k)^*}$. Puis pour chaque $i>1$ on pose : \begin{equation*} m_i^k=\floor{(m_1^k)^*+\ldots+(m_i^k)^*}-\floor{(m_1^k)^*+\ldots+(m_{i-1}^k)^*} \end{equation*} @@ -203,16 +203,16 @@ Si $\E[f^2(X)]<\infty$ et si $k/N ^k\to0$ quand $k\to \infty$ alors : avec $\sigma_*=\sum_i^Ip_i\sigma_i$, ce qui atteint la borne inférieure de $\textrm{Var}(\mu_{strat})$ trouvée en \eqref{eq:borninf}. \section{Exemples} -Nous allons maintenant implémenter et comparer les deux techniques d'estimateur d'espérance sur deux exemples décrit dans \cite{etore:hal-00192540} +Nous allons maintenant implémenter et comparer les deux techniques d'estimateur d'espérance sur deux exemples décrit dans \cite{etore:hal-00192540}. \subsection{Calcul de l'espérance d'une loi normale} -Dans ce premier exemple assez simple, on va chercher à calculer $ \mu = \E[X]$ où $X$ suit une loi normale centrée réduite +Dans ce premier exemple assez simple, on va chercher à calculer $ \mu = \E[X]$ où $X$ suit une loi normale centrée réduite. \subsubsection{Échantillonnage stratifié} Pour cet exemple, les strates $A_i$ seront au nombre de $10$ et \[\forall i \in{\{1,\ldots,10\}}\quad A_i =]y_{i-1}, y_i] \] où $y_i$ désigne le quantile en $i/10$ d'une loi normale, en prenant pour convention $y_0 = - \infty $ et $y_{10} = + \infty $. Ainsi la suite des probabilités $(p_i)_{1\leq i\leq 10}$ -est constante à $1/10$. Pour cet exemple, Étoré et Jourdain ont effectué quatre étapes de leur algorithme avec $N_1 = 300, N_2 = 1300, N_3 = 11300$ +est constante à $1/10$. Dans l'article, Étoré et Jourdain ont effectué quatre étapes de leur algorithme avec $N_1 = 300, N_2 = 1300, N_3 = 11300$ et $N_4 = 31300$, j'ai donc pris les mêmes nombres pour ma propre implémentation. \subsubsection{Quasi Monte Carlo randomisé} On cherche toujours à calculer $\mu$ mais cette fois avec la méthode de quasi Monte Carlo randomisé dont je rappelle l'estimateur : @@ -268,8 +268,8 @@ On peut ensuite utiliser une méthode d'échantillonage stratifié pour calculer \[ A_i=\{X\in\mathbb{R}^d\textrm{ tels que }u'X\in [y_{i-1},y_i]\} \] -avec $u$ un vecteur de norme 1 dans $\mathbb{R}^d$ et les $y_i$ seront les quantiles en $i/I$ d'une normale centrée réduite. Il nous faut donc pouvoir tirer la loi conditionelle de $X$ sachant $u'X\in [a, b]$. Les auteurs de l'article -donnent d'ailleurs la méthode pour simuler ces lois conditionnelle : +avec $u$ un vecteur de norme 1 dans $\mathbb{R}^d$ et les $y_i$ seront les quantiles en $i/I$ d'une normale centrée réduite. Il nous faut donc pouvoir tirer la loi conditionnelle de $X$ sachant $u'X\in [a, b]$. Les auteurs de l'article +donnent d'ailleurs une méthode pour simuler ces lois conditionnelle : Soient $(a, b)$ les bornes de notre intervalle et $u$ un vecteur de $\mathbb{R}^d$ de norme 1. Notons $F$ la fonction de répartition d'une normale centrée réduite. On simule d'abord $V = F(a) +U(F(b)-F(a))$ avec $U$ une uniforme sur $[0,1]$. @@ -282,29 +282,27 @@ de tirages par strates (la répartition $q_i = p_i$ donné plus haut lors de la $\mathbb{R}$ en $I=100$ strates suivant les quantiles au $1/100^{\textrm{ème}}$ de $\mathcal{N}(0,1)$ notés $y_i$ et ont alloué $N_i = N/I$ tirages par intervalles. Étoré et Jourdain ont donc refait le même travail avec leur algorithme adaptatif qui converge vers la répartition optimale $q_i=N_i/N$ posés dans \eqref{eqqi}, -technique utile dans ce cas car on ne connait pas la suite des $\sigma_i = \mathrm{Var}(f_{\mu}(X)|u'X\in [y_{i-1},y_i])$. +technique utile dans ce cas car on ne connait pas la suite des $\sigma_i = \mathrm{Var}(f_{\mu}(X)|u'X\in [y_{i-1},y_i])$. \subsection{Résultats} -Maintenant qu'on a décrit ce qu'est une option asiatique et comment utiliser l'importance sampling pour diminuer au mieux +Maintenant qu'on a décrit ce qu'est une option asiatique et comment utiliser l'importance sampling pour diminuer au mieux la variance, on peut comparer les méthodes d'échantillonage stratifié et de quasi Monte-Carlo randomisé. \begin{center} \input{table2.tex} \end{center} -Cette première table représente les différentes valeurs des estimateurs $\mu_{strat}$ et $\mu_{rqmc}$ ainsi que les demi-tailles des intervalles de confiance. -$d$ représente la dimension, c'est à dire le nombre d'instants ${t_m}$ entre $0$ et $T$ où le prix du sous-jacent est connu. d sera aussi la dimension +Cette première table représente les différentes valeurs des estimateurs $\mu_{strat}$ et $\mu_{rqmc}$ pour la valeur d'une option d'achat (call) ainsi que les demi-tailles des intervalles de confiance. +$d$ représente la dimension, c'est à dire le nombre d'instants ${t_m}$ entre $0$ et $T$ où le prix du sous-jacent est connu. $d$ sera aussi la dimension de notre suite à discrépance faible dans le cas du quasi Monte-Carlo randomisé. $K$ est le prix d'exercice de l'option. -On peut constater que l'avantage d'une méthode par rapport à l'autre est assez dépendante du prix d'exercice. +On peut constater que l'avantage d'une méthode par rapport à l'autre est assez dépendant du prix d'exercice. L'algorithme de stratified sampling étant supérieur quand le prix de l'option est plux faible. -Regardons maintenant la table équivalente dans le cas de l'option de vente. J'obtiens : +Regardons maintenant la table équivalente dans le cas de l'option de vente (put). J'obtiens : \begin{center} \input{table3.tex} \end{center} -Pour conculure on peut constater que quasi Monte-Carlo randomisé semble être tout de même plus efficace que la méthode d'échantillonage stratifié, en tout -cas sur les deux exemples étudiés ici. Sachant de plus que quasi Monte-Carlo randomisé est bien plus simple à implémenter, l'intérêt pratique de l'échantillonage -stratifié pour étudier des cas simples ne semble pas démontré. +Pour conclure, on peut constater que la méthode de quasi Monte-Carlo randomisé est — suivant les valeurs des paramètres — entre trois fois plus lente et plus rapide que la méthode d'échantillonnage par strates. En tout cas sur les deux exemples étudiés ici, les deux méthodes sont du même ordre de grandeur. Sachant que quasi Monte-Carlo randomisé est bien plus simple à implémenter, nous recommendons son usage en pratique comme méthode générale pour accélérer les algorithmes de Monte-Carlo. \newpage \printbibliography -- cgit v1.2.3-70-g09d2