#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{\convloi}{\overset{\text{loi }}{\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
\master poly-cours-monte-carlo-m1-im.lyx
\begin_removed_modules
eqs-within-sections
figs-within-sections
\end_removed_modules
\begin_modules
theorems-ams
\end_modules
\maintain_unincluded_children false
\language english
\language_package none
\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 english
\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 4
\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
Soient 
\begin_inset Formula $(x,u)$
\end_inset

 et 
\begin_inset Formula $(y,v)$
\end_inset

 dans 
\begin_inset Formula $E\times F$
\end_inset

.
 Le noyau 
\begin_inset Formula $Q$
\end_inset

 est irréductible donc il existe 
\begin_inset Formula $n$
\end_inset

 dans 
\begin_inset Formula $\N$
\end_inset

, 
\begin_inset Formula $x_{1},\dots,x_{n}$
\end_inset

, tels que
\begin_inset Formula 
\[
Q(x,x_{1})Q(x_{1},x_{2})\dots Q(x_{n-1},x_{n})Q(x_{n},y)>0\,.
\]

\end_inset

Nous avons, par hypothèse,
\begin_inset Formula 
\[
K(x_{1},v)K(x_{2},v)\dots K(x_{n},v)K(y,v)>0\,.
\]

\end_inset

Donc
\begin_inset Formula 
\begin{multline*}
\overline{Q}((x,u),(x_{1},v))\overline{Q}((x_{1},v),(x_{2},v))\dots\overline{Q}((x_{n},v),(y,v))\\
=Q(x,x_{1})K(x_{1},v)Q(x_{1},x_{2})K(x_{2},v)\dots Q(x_{n},y)K(y,v)>0\,.
\end{multline*}

\end_inset

Donc le noyau 
\begin_inset Formula $\overline{Q}$
\end_inset

 est irréductible et, de plus, pour tout 
\begin_inset Formula $n\in N^{*}$
\end_inset

, 
\begin_inset Formula $x,y\in E$
\end_inset

, 
\begin_inset Formula $u,v\in F$
\end_inset


\begin_inset Formula 
\begin{equation}
Q^{n}(x,y)>0\Rightarrow\overline{Q}^{n}((x,u),(y,v))>0\,.\label{eq:inclusion-ensemble}
\end{equation}

\end_inset


\end_layout

\begin_layout Enumerate
On remarque que pour tous 
\begin_inset Formula $x_{n},x_{n+1}^{*}\in E$
\end_inset

, 
\begin_inset Formula $u_{n},u_{n+1}^{*}\in F$
\end_inset

, 
\begin_inset Formula 
\begin{eqnarray*}
\frac{Z(x_{n+1}^{*},u_{n+1}^{*})Q(x_{n+1}^{*},x_{n})}{Z(x_{n},u_{n})Q(x_{n},x_{n+1}^{*})} & = & \frac{Z(x_{n+1}^{*},u_{n+1}^{*})K(x_{n+1}^{*},u_{n+1}^{*})Q(x_{n+1}^{*},x_{n})K(x_{n},u_{n})}{Z(x_{n},u_{n})K(x_{n},u_{n})Q(x_{n},x_{n+1}^{*})K(x_{n+1}^{*},u_{n+1}^{*})}\\
 & = & \frac{Z(x_{n+1}^{*},u_{n+1}^{*})K(x_{n+1}^{*},u_{n+1}^{*})\overline{Q}((x_{n+1}^{*},u_{n+1}^{*}),(x_{n},u_{n}))}{Z(x_{n},u_{n})K(x_{n},u_{n})\overline{Q}((x_{n},u_{n}),(x_{n+1}^{*},u_{n+1}^{*}))}\,.
\end{eqnarray*}

\end_inset

Donc la chaîne 
\begin_inset Formula $((X_{n},U_{n}))_{n\geq0}$
\end_inset

 est une chaîne de Metropolis de noyau de proposition 
\begin_inset Formula $\overline{Q}$
\end_inset

 et de loi cible 
\begin_inset Formula $C\times Z(.,.)K(.,.)$
\end_inset

 (avec 
\begin_inset Formula $C$
\end_inset

 constante telle que 
\begin_inset Formula $\sum_{(x,u)\in E\times F}Z(x,u)K(x,u)=1/C$
\end_inset

).
\end_layout

\begin_layout Enumerate
Si 
\begin_inset Formula $\overline{Q}((x,u),(y,v))>0$
\end_inset

 alors
\begin_inset Formula 
\[
\overline{Q}((y,v),(x,u))=Q(y,x)K(x,u)>0
\]

\end_inset

d'après nos hypothèse.
 D'après le lemme 4.13 du cours, le noyau 
\begin_inset Formula $\overline{P}$
\end_inset

 est donc irréductible.
\end_layout

\begin_layout Enumerate
Soit 
\begin_inset Formula $(x,u)\in E\times F$
\end_inset

, d'après l'équation (
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:inclusion-ensemble"

\end_inset

), nous avons
\begin_inset Formula 
\[
\{n\,:\,\overline{Q}^{n}((x,u),(x,u))>0\}\subset\{n\,:\,Q^{n}(x,x)>0\}\,.
\]

\end_inset

Donc, puisque 
\begin_inset Formula $d(x)=1$
\end_inset

 (car 
\begin_inset Formula $Q$
\end_inset

 est apériodique), 
\begin_inset Formula $d((x,u))=1$
\end_inset

.
 D'après le lemme 4.7 du cours, 
\begin_inset Formula $\overline{Q}$
\end_inset

 est apériodique.
 Puisque 
\begin_inset Formula $Z(.,.)$
\end_inset

 ne s'annule jamais, nous avons 
\begin_inset Formula $\overline{Q}((x,u),(y,v))>0\Rightarrow\overline{Q}((y,v),(x,u))>0$
\end_inset

 donc, pour 
\begin_inset Formula $(x,u)\in E\times F$
\end_inset

,
\begin_inset Formula 
\[
\{n\,:\,\overline{P}^{n}((x,u),(x,u))>0\}\subset\{n\,:\,\overline{Q}^{n}((x,u),(x,u))>0\}\,.
\]

\end_inset

Donc (en utilisant encore le lemme 4.7), 
\begin_inset Formula $\overline{P}$
\end_inset

 est apériodique.
\end_layout

\begin_layout Enumerate
Le noyau 
\begin_inset Formula $\overline{P}$
\end_inset

 est irréductible, apériodique et admet la probabilité invariante 
\begin_inset Formula $Z$
\end_inset

.
 D'après le théorème 4.8, 
\begin_inset Formula $((X_{n},U_{n}))_{n\geq0}$
\end_inset

 converge en loi vers 
\begin_inset Formula $CZ(.,.)K(.,.)$
\end_inset

.
 En particulier, si nous prenons une fonction 
\begin_inset Formula 
\[
\varphi\,:\,E\rightarrow\R^{+}\,,
\]

\end_inset


\begin_inset Formula 
\begin{eqnarray*}
\E(\varphi(X_{n})) & \underset{n\rightarrow+\infty}{\longrightarrow} & \sum_{(x,u)\in E\times F}\varphi(x)CZ(x,u)K(x,u)=\sum_{x\in E}\varphi(x)Cz(x)\,.
\end{eqnarray*}

\end_inset

Donc 
\begin_inset Formula $(X_{n})_{n\geq0}$
\end_inset

 converge en loi vers 
\begin_inset Formula $C\times z(.)$
\end_inset

.
\end_layout

\end_deeper
\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
Pour tout 
\begin_inset Formula $n$
\end_inset

, la loi de 
\begin_inset Formula $X_{n+1}$
\end_inset

 ne dépend que de 
\begin_inset Formula $X_{n}$
\end_inset

 donc nous avons bien une chaîne de Markov.
\end_layout

\begin_layout Enumerate
Pour tout 
\begin_inset Formula $x$
\end_inset

 et 
\begin_inset Formula $y$
\end_inset

 dans 
\begin_inset Formula $E$
\end_inset

 tels que 
\begin_inset Formula $y\neq x$
\end_inset

, 
\begin_inset Formula 
\begin{eqnarray*}
P(x,y) & = & q(y)\times\frac{p(y)}{cq(y)}\\
 & = & \frac{p(y)}{c}\,.
\end{eqnarray*}

\end_inset

D'où
\begin_inset Formula 
\[
P(x,x)=1-\sum_{y\neq x}P(x,y)=1-\sum_{y\neq x}\frac{p(y)}{c}\,.
\]

\end_inset


\end_layout

\begin_layout Enumerate
Pour tout 
\begin_inset Formula $n$
\end_inset

, on propose 
\begin_inset Formula $Y_{n+1}$
\end_inset

 de loi 
\begin_inset Formula $q$
\end_inset

, que l'on accepte avec probabilité 
\begin_inset Formula $p(Y_{n+1})/cq(Y_{n+1})$
\end_inset

.
 C'est ce qui se passerait dans une méthode de rejet basée sur l'inégalité
 
\begin_inset Formula $p\leq cq$
\end_inset

.
 Si on définit par récurrence les temps d'arrêt
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
begin{itemize}
\backslash
item 
\end_layout

\end_inset


\begin_inset Formula $T_{0}=0$
\end_inset

, 
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
item 
\end_layout

\end_inset


\begin_inset Formula $T_{k+1}=\inf\{n>T_{k}\,:\,U_{n-1}<p(Y_{n})/(cq(Y_{n}))\}$
\end_inset

,
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
end{itemize}
\end_layout

\end_inset

 alors 
\begin_inset Formula $X_{T_{1}}$
\end_inset

, 
\begin_inset Formula $X_{T_{2}}$
\end_inset

, 
\begin_inset Formula $X_{T_{3}}$
\end_inset

, \SpecialChar ldots
 sont i.i.d.
 de loi 
\begin_inset Formula $p$
\end_inset

.
\end_layout

\begin_layout Enumerate
Nous calculons pour tout 
\begin_inset Formula $x$
\end_inset


\begin_inset Formula 
\begin{eqnarray*}
\mu P(x) & = & \mu(x)P(x,x)+\sum_{y\neq x}\mu(y)P(y,x)\\
 & = & \mu(x)\left(1-\sum_{y\neq x}\frac{p(y)}{c}\right)+\sum_{y\neq x}\mu(y)\frac{p(x)}{c}\,.
\end{eqnarray*}

\end_inset

On voit donc que 
\begin_inset Formula $pP=p$
\end_inset

 (
\begin_inset Formula $p$
\end_inset

 est invariante pour 
\begin_inset Formula $P$
\end_inset

).
 La chaîne 
\begin_inset Formula $(X_{n})$
\end_inset

 est irréductible (pour tout 
\begin_inset Formula $x\neq y$
\end_inset

, on a toujours une probabilité non nulle d'aller de 
\begin_inset Formula $x$
\end_inset

 à 
\begin_inset Formula $y$
\end_inset

).
 Comme l'espace est fini, nous savons alors que 
\begin_inset Formula $(X_{n})\convloi p$
\end_inset

.
 
\end_layout

\end_deeper
\end_body
\end_document
