Exemples d'utilisation
de l'algorithme de Robbins et Monro

LAPEYRE Bernard

28 mars 2018

Version pdf de ce document

La loi forte comme un algorithme stochastique

On considère $(G_n,n\geq 0)$ une suite de gaussiennes centrées réduites indépendantes. On pose $M_n=(G_1+\cdots+G_n)/n$

• Vérifier que
  
  $$M_{n+1} = M_n -\gamma_n \left(M_n - G_{n+1}\right),$$
  
  
  où $\gamma_n=1/(n+1)$. Interpréter cette équation comme un algorithme stochastique. Vérifier que l'on peut aussi prendre $\gamma_n=\alpha /(n+1)$. Etudier informatiquement la convergence pour $\alpha=1/10$, $\alpha=1$, $\alpha=2$. Que se passe t'il lorsque $\alpha$ est (trop) petit ?
  Correction

Calcul de fractile

Pour $\alpha$ un nombre compris entre $0$ et $1$, on cherche à calculer la valeur d'un fractile $x_p$ d'ordre $p$ d'une gaussienne centrée réduite $G$. On cherche ainsi à calculer la solution de l'équation :

$$f(x_p) = \P\left(\vert G\vert\leq x_p\right) = p.$$

Pour cela on pose $F(x,g)=\inde{\vert g\vert\leq x}-p$ et l'on remarque que $\P\left(\vert G\vert\leq x_p\right) - p = \E\left(F(x_p,G)\right)=0$.

1. Ceci suggère d'utiliser l'algorithme de Robbins et Monro suivant :
   
   $$X_{n+1}=X_n - \gamma_n F(X_n,G_{n+1}),$$
   
   
   où $(G_n,n\geq 1)$ est une suite de variables aléatoires gaussiennes centrées réduites et $\gamma_n=C/n^\beta$, où $0<\beta\leq 1$.

   On prendra pour $p=0.95$ (on cherche donc à approximer $x_p \approx 1.96$).

   Implémenter cet algorithme et étudier la convergence pour $C=1$, $\beta=0.6$ et $C=1$, $\beta=0.8$.

   Dans le cas $\beta=1.0$, tester les valeurs $C=0.5$, $C=1.0$, $C=2.0$, $C=4.0$.

   Commenter les difficultés que l'on peut rencontrer.

   Correction

2. La pente de la fonction $f$ en $x_p$ est donné par $c^*= {2e^{-\frac{x_p^2}{2}}}/{\sqrt{2\pi}}.$ Pour quelle valeur de $C$ peut on s'attendre à obtenir un TCL ?

   Verifier le théorème de la limite centrale pour cet algorithme sous cette condition.

   Correction

Optimisation du paramètre de la fonction d'importance importance

On veut calculer $\E(f(G))$. Comme

$$\E\left(e^{-\lambda G - \frac{\lambda^2}{2}} f(G+\lambda)\right) = \E(f(G)),$$

On cherche a minimiser en $\lambda$ la variance de $X_\lambda = e^{-\lambda G - \frac{\lambda^2}{2}} f(G+\lambda),$ mais

$$\Var\left(X_\lambda\right) = \E\left(e^{-\lambda G + \frac{\lambda^2}{2}} f^2(G)\right) - \E(f(G))^2.$$

On traitera le cas du call dans le modèle de Black et Scholes avec $K=100$ ou $K=200$ et les paramètres suivants $r=2\%$, $\sigma=30\%/\mbox{an}$, $S_0=x=100$, $T=1$.

1. Tracer (une approximation Monte-Carlo de) la courbe $\Var(X_\lambda)$.
   Correction
2. Montrer que la dérivée s'écrit sous les deux formes
   
   $$\frac{\partial}{\partial \lambda}\Var\left(X_\lambda\right)... ... \E\left( G e^{-2\lambda G - \lambda^2} f^2(G+\lambda)\right),$$
   
   
   et vérifier ce fait par simulation en tracant les deux approximations Monte-Carlo de la dérivées. Laquelle de ces deux représentations vous parait elle préférable du point de vue de la simulation ?
   Correction
3. On chercher à résoudre $\frac{\partial}{\partial \lambda}\Var\left(X_\lambda\right)=0$ en utilisant un algorithme de type Robbins et Monro utilisant la première représentation de la dérivée.

   On prendra $K=200$.

   Pour cela, on pose $X_0=0$, puis
   

   $$X_{n+1}=X_n -\gamma_n (\lambda - G_{n+1})e^{-\lambda G_{n+1} + \frac{\lambda^2}{2}} f^2(G_{n+1}).$$
   
   
   Implémenter cet algorithme de façon directe (sans borner l'algorithme). Constater l'instabilité de cet algorithme. Quelle hypothèse permettant de prouver la convergence n'est pas vérifiée ? (On essaye quand même!).

   Implémenter cet algorithme en ramenant $X_n$ à $0$ si $X_n$ dépasse la valeur de $5$ (procédure dite de ``projection de Chen''). Vérifier que l'algorithme converge (mieux!).

   Correction
4. Proposer un algorithme basée sur la deuxième représentation de la dérivée. Lequel de ces deux algorithmes vous parait le plus pertinent.