#LyX 2.2 created this file. For more info see http://www.lyx.org/
\lyxformat 508
\begin_document
\begin_header
\save_transient_properties true
\origin unavailable
\textclass amsart
\begin_preamble

\usepackage{a4wide}
\usepackage{bbm}
\newcommand{\1}{\mathbbm{1}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\var}{\mathbb{V}}
\newcommand{\p}{\mathbb{P}}
\newcommand{\N}{\mathbb{N}}

\newcommand{\convps}{\overset{\text{p.s.}}{\underset{n\rightarrow +\infty}{\longrightarrow}}}



    \newcommand\independent{\protect\mathpalette{\protect\independenT}{\perp}}
    \def\independenT#1#2{\mathrel{\rlap{$#1#2$}\mkern2mu{#1#2}}}
\end_preamble
\use_default_options false
\begin_removed_modules
eqs-within-sections
figs-within-sections
\end_removed_modules
\begin_modules
theorems-ams
\end_modules
\maintain_unincluded_children false
\language french
\language_package babel
\inputencoding auto
\fontencoding T1
\font_roman "default" "default"
\font_sans "default" "default"
\font_typewriter "default" "default"
\font_math "auto" "auto"
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_osf false
\font_sf_scale 100 100
\font_tt_scale 100 100
\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\paperfontsize 11
\spacing single
\use_hyperref false
\papersize default
\use_geometry false
\use_package amsmath 2
\use_package amssymb 2
\use_package cancel 1
\use_package esint 1
\use_package mathdots 0
\use_package mathtools 1
\use_package mhchem 0
\use_package stackrel 1
\use_package stmaryrd 1
\use_package undertilde 1
\cite_engine basic
\cite_engine_type default
\biblio_style plain
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\justification true
\use_refstyle 0
\index Index
\shortcut idx
\color #008000
\end_index
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\quotes_language french
\papercolumns 1
\papersides 2
\paperpagestyle default
\tracking_changes false
\output_changes false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\end_header

\begin_body

\begin_layout Standard
\align left
Université Nice Sophia Antipolis - M1 IM - Méthodes de simulation stochastique
 (Monte-Carlo)
\begin_inset Newline newline
\end_inset

 
\family typewriter

\begin_inset Flex URL
status open

\begin_layout Plain Layout

http://math.unice.fr/rubentha/cours.html
\end_layout

\end_inset


\family default

\begin_inset Newline newline
\end_inset


\begin_inset VSpace medskip
\end_inset


\end_layout

\begin_layout Title
Corrigés pour le chapitre 3
\end_layout

\begin_layout Standard
\begin_inset Note Comment
status open

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
setcounter{thm}{2}
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Exercise
\begin_inset space ~
\end_inset


\end_layout

\begin_layout Enumerate
On utilise l'estimateur de la variance introduit au chapitre 1.
 
\end_layout

\begin_layout Enumerate
Posons 
\begin_inset Formula $g(x)=\1_{x>0}e^{\beta x}$
\end_inset

, 
\begin_inset Formula $f(x)=e^{-x^{2}/2}/\sqrt{2\pi}$
\end_inset

.
 Nous remarquons que
\begin_inset Formula 
\begin{eqnarray*}
g(x)f(x) & = & \frac{\1_{x>0}}{\sqrt{2\pi}}\exp\left(-\frac{1}{2}(x-\beta)^{2}+\frac{\beta^{2}}{2}\right)\,.
\end{eqnarray*}

\end_inset

Nous utilisons les mêmes notations que dans le cours et prenons 
\begin_inset Formula 
\[
\widetilde{f}(x)=\frac{1}{\sqrt{2\pi}}\exp\left(-\frac{1}{2}(x-\beta)^{2}+\frac{\beta^{2}}{2}\right)\,.
\]

\end_inset

 Nous avons
\begin_inset Formula 
\begin{eqnarray*}
\frac{\widetilde{f}(x)}{\int_{\R}\widetilde{f}(y)dy} & = & \frac{1}{\sqrt{2\pi}}\exp\left(-\frac{1}{2}(x-\beta)^{2}\right)
\end{eqnarray*}

\end_inset

(c'est la densité de 
\begin_inset Formula $\mathcal{N}(\beta,1)$
\end_inset

, suivant laquelle nous savons simuler).
\end_layout

\begin_layout Enumerate
Nous avons 
\begin_inset Formula 
\begin{eqnarray*}
I & = & \E(g(X))\\
 & = & \E(g(X)-h(X))+\E(h(X))
\end{eqnarray*}

\end_inset

avec 
\begin_inset Formula $h(x)=e^{\beta x}$
\end_inset

 et
\begin_inset Formula 
\begin{eqnarray*}
\E(h(X)) & = & \int_{\R}\frac{\exp\text{\left(-\frac{x^{2}}{2}+\beta x\right)}}{\sqrt{2\pi}}dx\\
 & = & \int_{\R}\frac{\exp\left(-\frac{1}{2}(x-\beta)^{2}+\frac{\beta^{2}}{2}\right)}{\sqrt{2\pi}}dx\\
 & = & \exp\left(\frac{\beta^{2}}{2}\right)\,.
\end{eqnarray*}

\end_inset


\end_layout

\begin_layout Enumerate
Si 
\begin_inset Formula $X\sim\mathcal{N}(0,1)$
\end_inset

, alors 
\begin_inset Formula $-X\sim\mathcal{N}(0,1)$
\end_inset

.
 Donc 
\begin_inset Formula 
\[
\E(g(X))=\E(g(-X))=\E\left(\frac{g(X)+g(-X)}{2}\right)\,.
\]

\end_inset

On en déduit une nouvelle méthode de Monte-Carlo pour approcher l'espérance
 (voir le programme).
\end_layout

\begin_layout Standard
\begin_inset Separator parbreak
\end_inset


\end_layout

\begin_layout Exercise
\begin_inset space ~
\end_inset


\end_layout

\begin_layout Enumerate
On approche
\begin_inset Formula 
\[
I=\int_{\R}\sqrt{|u|}\frac{e^{-u^{2}/2}}{\sqrt{2\pi}}du\,.
\]

\end_inset


\end_layout

\begin_layout Enumerate
Voir le programme.
\end_layout

\begin_layout Enumerate
On sait calculer 
\begin_inset Formula 
\begin{eqnarray*}
\E(|X|) & = & \int_{\R}|x|\frac{e^{-x^{2}/2}}{\sqrt{2\pi}}dx\\
 & = & 2\int_{0}^{+\infty}x\frac{e^{-x^{2}/2}}{\sqrt{2\pi}}dx\\
 & = & 2\left[-\frac{e^{-x^{2}/2}}{\sqrt{2\pi}}\right]_{0}^{+\infty}\\
 & = & \sqrt{\frac{2}{\pi}}\,.
\end{eqnarray*}

\end_inset

Nous proposons donc une méthode de variable de contrôle avec 
\begin_inset Formula $h(x)=|x|$
\end_inset

.
 
\end_layout

\begin_layout Enumerate
Voir le programme (la variance est bien réduite).
\end_layout

\begin_layout Standard
\begin_inset Separator parbreak
\end_inset


\end_layout

\begin_layout Exercise
\begin_inset ERT
status open

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Enumerate
\begin_inset space ~
\end_inset


\begin_inset Separator latexpar
\end_inset


\end_layout

\begin_deeper
\begin_layout Enumerate
\begin_inset Note Note
status collapsed

\begin_layout Plain Layout
On commence par faire des calculs pour pouvoir simuler suivant la densité
 
\begin_inset Formula $f$
\end_inset

.
 La fonction de répartition est 
\begin_inset Formula 
\[
F(x)=\begin{cases}
0 & \mbox{ si }x\leq0\,,\\
\sqrt{x} & \mbox{ si }x\in[0;1]\,,\\
1 & \mbox{ si }x\geq1\,.
\end{cases}
\]

\end_inset

Le pseudo-inverse de 
\begin_inset Formula $F$
\end_inset

 est 
\begin_inset Formula 
\[
u\in[0;1]\mapsto u^{2}\,.
\]

\end_inset

Voir le programme pour le calcul de l'espérance.
\end_layout

\end_inset

Nous avons 
\begin_inset Formula $p_{l}=\E(Y)$
\end_inset

 avec 
\begin_inset Formula $Y=\1_{[l;l+1]}(X).$
\end_inset

 Si nous tirons 
\begin_inset Formula $Y_{1}$
\end_inset

, 
\begin_inset Formula $Y_{2}$
\end_inset

, … i.i.d.
 de même loi que 
\begin_inset Formula $Y$
\end_inset

, alors
\begin_inset Formula 
\[
\frac{Y_{1}+\dots+Y_{n}}{n}\convps p_{l}\,.
\]

\end_inset

Voir le programme pour la mise en œuvre.
\end_layout

\begin_layout Enumerate
Voir le programme pour une approximation de la variance par Monte-Carlo.
 On demande ici un calcul explicite.
 Puisque 
\begin_inset Formula $Y$
\end_inset

 est de loi 
\begin_inset Formula $\mathcal{B}(p)$
\end_inset

, on calcule facilement : 
\begin_inset Formula $\var(Y)=p_{l}(1-p_{l})$
\end_inset

 (voir cours de licence).
\end_layout

\end_deeper
\begin_layout Enumerate
\begin_inset space ~
\end_inset


\begin_inset Separator latexpar
\end_inset


\end_layout

\begin_deeper
\begin_layout Enumerate
Prenons 
\begin_inset Formula 
\[
\widetilde{f}_{1}(x)=e^{-l}\1_{[l;l+1]}(x)\,.
\]

\end_inset

Cette fonction est proche de 
\begin_inset Formula $x\mapsto e^{-x}\1_{[l;l+1]}(x)$
\end_inset

.
 Nous avons
\begin_inset Formula 
\[
\widetilde{f}(x)=\frac{\widetilde{f}_{1}(x)}{\int_{u}\widetilde{f}_{1}(u)du}=\1_{[l;l+1]}(x)\,,
\]

\end_inset

qui est la densité de la loi uniforme sur 
\begin_inset Formula $[l;l+1]$
\end_inset

.
 Si nous tirons 
\begin_inset Formula $Z_{1}$
\end_inset

, 
\begin_inset Formula $Z_{2}$
\end_inset

, … i.i.d.
 de loi uniforme sur 
\begin_inset Formula $[l;l+1]$
\end_inset

, nous avons
\begin_inset Formula 
\[
\frac{1}{n}\sum_{i=1}^{n}\frac{e^{-Z_{i}}\1_{[l;l+1]}(Z_{i})}{\widetilde{f}(Z_{i})}\convps p_{l}\,.
\]

\end_inset

Voir le programme pour la mise en œuvre.
\end_layout

\begin_layout Enumerate
Voir le programme pour un calcul approché.
 Et voir ci-dessous pour le calcul exact (vu l'énoncé, on veut un calcul
 exact).
\end_layout

\begin_layout Enumerate
On peut calculer les espérances
\begin_inset space ~
\end_inset

:
\begin_inset Formula 
\begin{eqnarray*}
\E(\1_{[l;l+1]}(X)^{2}) & = & \E(\1_{[l;l+1]}(X))\\
 & = & p_{l}\,,
\end{eqnarray*}

\end_inset


\begin_inset Formula 
\begin{eqnarray*}
\E((e^{-Z_{1}})^{2}) & = & \E(e^{-2Z_{1}})\\
 & = & \int_{l}^{l+1}e^{-2x}dx\\
 & = & \frac{e^{-2l}-e^{-2(l+1)}}{2}\,.
\end{eqnarray*}

\end_inset

Donc 
\begin_inset Formula 
\[
\var(\1_{[l;l+1]}(X))=p_{l}-p_{l}^{2}=p_{l}(1-p_{l})\,,
\]

\end_inset


\begin_inset Formula 
\[
\var(e^{-Z_{1}})=\frac{e^{-2l}-e^{-2(l+1)}}{2}-p_{l}^{2}\,.
\]

\end_inset

De plus
\begin_inset space ~
\end_inset

: 
\begin_inset Formula 
\[
p_{l}=\int_{l}^{l+1}e^{-x}dx=e^{-l}-e^{-(l+1)}\,.
\]

\end_inset

On regarde le rapport des deux variances (et on multiplie par 
\begin_inset Formula $e^{-l}$
\end_inset

 en haut et en bas)
\begin_inset Formula 
\begin{eqnarray*}
\frac{\left(\frac{e^{-2l}-e^{-2l-2}}{2}\right)-\left(e^{-l}-e^{-l-1}\right)^{2}}{\left(e^{-l}-e^{-l-1}\right)-\left(e^{-l}-e^{-l-1}\right)^{2}} & = & \frac{\left(\frac{e^{-l}-e^{-l-2}}{2}\right)-(1-e^{-1})(e^{-l}-e^{-l-1})}{(1-e^{-1})-(1-e^{-1})(e^{-l}-e^{-l-1})}\\
 & \underset{l\rightarrow+\infty}{\longrightarrow} & 0\,.
\end{eqnarray*}

\end_inset


\end_layout

\end_deeper
\begin_layout Standard
On recommence ensuite avec 
\begin_inset Formula $X\sim\mathcal{N}(0;1)$
\end_inset

.
 On cherche une fonction d'importance 
\begin_inset Formula $\widetilde{f}$
\end_inset

 dont le profil ressemble à celui de 
\begin_inset Formula $x\mapsto\1_{[l;l+1]}(x)\exp(-x^{2}/2)/\sqrt{2\pi}$
\end_inset

.
 Dans le programme, on fait deux essais
\begin_inset space ~
\end_inset

:
\begin_inset Formula 
\[
\widetilde{f}_{1}(x)=\1_{[l;l+1]}(x)\,,
\]

\end_inset


\begin_inset Formula 
\[
\widetilde{f}_{2}(x)=\1_{[l;l+1]}(x)\times\frac{e^{-x}}{e^{-l}-e^{-l-1}}\,.
\]

\end_inset

La fonction 
\begin_inset Formula $\widetilde{f}_{2}$
\end_inset

 a l'air mieux adapté et en effet, on constate que la variance de la méthode
 d'échantillonage d'importance avec 
\begin_inset Formula $\widetilde{f}_{2}$
\end_inset

 est environ la moitié de celle avec 
\begin_inset Formula $\widetilde{f}_{1}$
\end_inset

.
 
\end_layout

\begin_layout Standard
\begin_inset Separator parbreak
\end_inset


\end_layout

\begin_layout Exercise
\begin_inset ERT
status open

\begin_layout Plain Layout

\end_layout

\end_inset


\begin_inset Separator latexpar
\end_inset


\end_layout

\begin_deeper
\begin_layout Enumerate
On sait que la probabilité d'accepter dans la méthode du rejet est 
\begin_inset Formula $1/M$
\end_inset

.
 Quelque soit 
\begin_inset Formula $i$
\end_inset

, pour parvenir à simuler 
\begin_inset Formula $X_{i}$
\end_inset

 de densité 
\begin_inset Formula $p$
\end_inset

 par la méthode du rejet, on fait 
\begin_inset Formula $N_{i}$
\end_inset

 boucles avec 
\begin_inset Formula $N_{i}$
\end_inset

 qui suit la loi 
\begin_inset Formula 
\[
\forall k\in\N^{*}\,,\,\p(N_{i}=k)=\left(1-\frac{1}{M}\right)^{k-1}\frac{1}{M}
\]

\end_inset

(c'est un résultat du cours).
 Nous avons 
\begin_inset Formula 
\[
N=N_{1}+N_{2}+\dots+N_{n}
\]

\end_inset

et les 
\begin_inset Formula $N_{i}$
\end_inset

 sont indépendants.
 Si on note 
\begin_inset Formula $g$
\end_inset

 la loi des 
\begin_inset Formula $N_{i}$
\end_inset

, la loi de 
\begin_inset Formula $N$
\end_inset

 est 
\begin_inset Formula $g*g*\dots*g$
\end_inset

 (convolée 
\begin_inset Formula $n$
\end_inset

 fois).
 C'est à dire 
\begin_inset Formula 
\begin{multline*}
\forall m\geq n\,,\,\p(N=m)=\sum_{(k_{1},\dots,k_{n})\in(\N^{*})^{n}}\1_{k_{1}+\dots+k_{n}=m}\prod_{i=1}^{n}\left(1-\frac{1}{M}\right)^{k_{i}-1}\frac{1}{M}\\
=\sum_{(k_{1},\dots,k_{n})\in(\N^{*})^{n}}\1_{k_{1}+\dots+k_{n}=m}\left(1-\frac{1}{M}\right)^{m-n}\left(\frac{1}{M}\right)^{n}\\
=\#\{(k_{1},\dots,k_{n})\in(\N^{*})^{n}\,:\,k_{1}+\dots+k_{n}=m\}\times\left(1-\frac{1}{M}\right)^{m-n}\left(\frac{1}{M}\right)^{n}\\
=C_{m-1}^{n-1}\left(1-\frac{1}{M}\right)^{m-n}\left(\frac{1}{M}\right)^{n}\,.
\end{multline*}

\end_inset

La dernière égalité vient d'un résultat classique de dénombrement.
\end_layout

\begin_layout Enumerate
On calcule, pour une fonction 
\begin_inset Formula $\varphi\in C_{b}^{+}(\R)$
\end_inset

, avec 
\begin_inset Formula $Y$
\end_inset

 et 
\begin_inset Formula $U$
\end_inset

 indépendantes, 
\begin_inset Formula $Y\sim q$
\end_inset

, 
\begin_inset Formula $U\sim\mathcal{U}([0;1])$
\end_inset

 
\begin_inset Formula 
\begin{eqnarray*}
\E(\varphi(Y)\1_{U\times Cq(Y)>p(Y)}) & = & \int_{\R}\varphi(y)\left(1-\frac{p(y)}{Cq(y)}\right)q(y)dy\\
 & = & \E(\varphi(Y))-\frac{1}{C}\E(\varphi(X))\,,
\end{eqnarray*}

\end_inset

avec 
\begin_inset Formula $X\sim p$
\end_inset

.
 Donc
\begin_inset Formula 
\begin{eqnarray*}
\E(\varphi(Y)|U\times Cq(Y)>p(Y)) & = & \frac{\E(\varphi(Y))-\frac{1}{C}\E(\varphi(X))}{1-\frac{1}{C}}\,.
\end{eqnarray*}

\end_inset

Donc la loi de 
\begin_inset Formula $Y$
\end_inset

 conditionnellement à 
\begin_inset Quotes fld
\end_inset


\begin_inset Formula $Y$
\end_inset

 rejeté
\begin_inset Quotes frd
\end_inset

 est de densité
\begin_inset Formula 
\[
y\mapsto f(y)=\frac{q(y)-\frac{p(y)}{C}}{1-\frac{1}{C}}\,.
\]

\end_inset

Conditionnellement à 
\begin_inset Formula $N=n+p$
\end_inset

, 
\begin_inset Formula $Z_{1},\dots,Z_{N-n}$
\end_inset

 sont 
\begin_inset Formula $p$
\end_inset

 variables indépendantes de densité 
\begin_inset Formula $f$
\end_inset

.
 
\end_layout

\end_deeper
\end_body
\end_document
