\documentclass{pbsheet}

\TITRE{Feuille de TP n°6 \\ Martingales en modélisation}
\FORMATION{Épreuve de modélisation - Agrégation Externe de Mathématiques}
\ETABLISSEMENT{Université Paul Sabatier Toulouse III}
\ANNEE{2005}
\MEL{chafai@math.ups-tlse.fr}
\AUTEUR{B. Bercu \& D. Chafaï}
\WEB{http://www.lsp.ups-tlse.fr/Chafai/agregation.html}
\DATE{Octobre-Novembre 2004}

\begin{document}

%%
\section{Martingales}
%%

%FIXME: ajouter de la biblio.

Soit $(\Om, \cA, \dP)$ un espace de probabilité muni d'une filtration
$\cF=(\cF_n)_n$ où $\cF_n$ représente la tribu des événements antérieurs à
l'instant $n$. Soit $(M_n)_n$ une suite des variables aléatoires adaptée à
$\cF$.

{\small

\noindent\textbf{Définition 1.} 
On dit que $(M_n)_n$ est une \emph{martingale} (resp.
\emph{sous-martingale}, resp. \emph{sur-martingale}), si
$(M_n)_n$ (resp. $(M^+_n)_n$, resp. $(M_n^-)_n$) est intégrable 
et pour tout $n\geq 0$, $\dE(M_{n+1}\,|\,\cF_n)=M_n$ (resp. 
$\dE(M_{n+1}\,|\,\cF_n)\geq M_n$, resp. $\dE(M_{n+1}\,|\,\cF_n)\leq M_n$).
On note alors respectivement (MG), (sMG), (SMG).

\noindent\textbf{Exemple.} 
Soit $(X_n)_n$ une suite de v.a. indépendantes et de même
loi, d'espérance $m$ et de variance $\si^2$. Soit $S_n=\sum_{k=1}^n X_k$,
$M_n=S_n-nm$ et $N_n=M_n^2-n\si^2$. Alors, $(M_n)_n$ et $(N_n)_n$ sont deux
martingales.

\noindent\textbf{Théorème de Doob.} 
Soit $(M_n)_n$ une MG, sMG, ou SMG, bornée dans
$\bL^1(\cA)$.  On a $M_n \rightarrow M_\infty$ p.s. avec $M_\infty \in
\bL^1(\cA)$. En particulier, toute sMG majorée ou SMG minorée converge
p.s.

\noindent\textbf{Définition 2.} Soit $(M_n)_n$ une MG de carré intégrable.
On appelle \emph{processus croissant} associé à $(M_n)_n$, la suite 
$(<\!M\!>_n)_n$ définie par $<\!M\!>_0=M_0^2$ et, pour tout $n\geq 0$,
$%
<\!M\!>_{n+1}-<\!M\!>_n=\dE((M_{n+1} -M_n)^2\,|\,\cF_n)%
=\dE(M_{n+1}^2 -M_n^2\,|\,\cF_n).%
$ La suite $(\!<\!M\!>_n)_n$ est prévisible, intégrable, positive et
croissante. Si $N_n=M_n^2 - <\!M\!>_n$, alors $(N_n)_n$ est une MG centrée
donc $\dE(M_n^2)=\dE(<\!M\!>_n)$.

\noindent\textbf{Inégalités de Kolmogorov.} 
Soit $(M_n)_n$ une MG de carré intégrable
et $M_n^*=\sup_{k\leq n}|M_k|$. Alors, pour tout $a>0$, $a\dP(M_n^* \geq
a)\leq \bE(|M_n|)$ et $a^2\dP(M_n^* \geq a)\leq \dE(<\!M_n\!>)$. En 
particulier, on obtient que $\dE((M_n^*)^2)\leq 4\dE(<\!M_n\!>)$.

} % \small

\noindent\textbf{Loi des Grands Nombres.} 
Soit $(M_n)_n$ une MG de carré intégrable.
\begin{enumerate}
\item Sur $\{<\!M\!>_\infty <+ \infty \}$, $M_n \rightarrow M_\infty$
p.s. avec $M_\infty$ finie. 
\item Sur $\{<\!M\!>_\infty = + \infty \}$,
$M_n=o(<\!M\!>_n)$ p.s. Plus précisement, pour tout $\ga>0$, on a
$$
\Bigl(\frac{M_n}{<\!M_n\!>}\Bigr)^2%
=o\Bigl(\frac{(\log<\!M_n\!>)^{1+\gamma}}{<\!M_n\!>}\Bigr)
\text{\quad p.s.}
$$
\end{enumerate}

\noindent\textbf{Théorème Limite Centrale.}
Soit $(M_n)_n$ une MG de carré intégrable
et soit $(a_n)_n$ une suite réelle, positive, déterministe croissante vers
l'infini. On pose $\De M_n := M_n -M_{n-1}$ et on suppose que 
\begin{enumerate}
\item Il existe $\la\geq 0$ déterministe tel que $a_n^{-1}<\!M\!>_n
  \limP{n}\la$.
\item Pour tout $\veps >0$,
  \ds{
  \frac{1}{a_n}\,\sum_{k=1}^n %
  \dE(\De M_k^2\,\rI_\BRA{|\De M_k|\geq \veps\sqrt{a_n}}\,|\,%
  \cF_{k-1})\limP{n} 0
  }
  (condition de Lindeberg).
\end{enumerate}
Alors, on a 
$$
\frac{1}{\sqrt{n}}\,M_n\limL{n} \cN(0,\la) 
\text{\quad et si }\la>0\quad
\sqrt{a_n}\,\frac{M_n}{<\!M\!>_n}\limL{n} \cN(0,\la^{-1}).
$$
On pourra consulter par exemple 
\cite{duflo}, \cite{cottrell-duhamel}, \cite{revuz-probas}, 
\cite{dacunha-castelle-duflo-2}.


\section{Utilisation en modélisation.}

\begin{exo}[Bandit à deux bras] 
  Le \emph{bandit à deux bras} est une machine à sous
  à deux leviers $A$ et $B$. Pour le levier $A$, le gain est $1$ avec
  probabilité $\te^A$ et $0$ avec probabilité $1-\te^A$. De même pour le
  levier $B$. On suppose que $0<\te^A,\te^B<1$ avec $\te^A\neq \te^B$. \`A
  l'instant $n$, le joueur choisit le levier $U_n\in\{A,B\}$ au
  vu des observations antérieures. Soit $(X_n)_n$ la suite des gains du
  joueur. Pour tout $n\geq 0$, on a $\dP(X_{n+1}=1\,|\,U_n)=\te^{U_n}$ et
  $\dP(X_{n+1}=0\,|\,U_n)=1-\te^{U_n}$.  Soit $(G_n)_n$ la suite des gains
  moyens du joueur, $G_n=\sum_{k=1}^n X_k/n$. Le joueur va chercher à
  optimiser son gain moyen. S'il connaissait $\te^A$ et $\te^B$, la stratégie
  optimale serait de jouer toujours avec le levier $A$ si $\te^A>\te^B$ et
  avec le levier $B$ sinon.  On aurait donc $G_n\rightarrow \sup(\te^A,\te^B)$
  p.s.  Pour $n \geq 0$, soit $N_n^A$ le nombre de fois où le joueur choisi le
  levier $A$ avant l'instant $n$ et $N_n^B=n-N_n^A$.  Soit
  $M_n=nG_n-\te^AN_n^A -\te^BN_n^B$. Montrer que $(M_n)_n$ 
  est une martingale de
  processus croissant 
  $<\!M\!>_n=\te^A(1-\te^A)N_n^A+\te^B(1-\te^B)N_n^B$.  En déduire que
  $M_n=o(n)$ p.s. et $ \inf(\te^A,\te^B)\leq\liminf G_n\leq \limsup G_n \leq
  \sup(\te^A,\te^B)$ p.s. On estime $\te^A$ et $\te^B$ par
  $$
  \WH{\te}_n^A=\frac{1}{N_n^A}\sum_{k=0}^{n-1}\rI_{\{U_k=A, \ X_{k+1}=1\}}%
  \text{\quad et\quad}%
  \WH{\te}_n^B=\frac{1}{N_n^B}\sum_{k=0}^{n-1}\rI_{\{U_k=B, \ X_{k+1}=1\}}.
  $$
  Vérifier que si l'on joue une infinité de fois avec le levier $A$ et le
  levier $B$, alors $\WH{\te}_n^A \rightarrow \te^A$ et $\WH{\te}_n^B
  \rightarrow \te^B$. Soit $(c_n)_n$ une suite de $\dN$, croissante, et telle
  que $n=o(c_n)$. Soit $I_c=\{c_n, \ n\geq 1\}$. À l'instant $n \geq 1$, on
  choisit $U_n=A$ si $\WH{\te}_n^A \geq \WH{\te}_n^B$ et $n \notin I_c$,
  $U_n=B$ si $\WH{\te}_n^A < \WH{\te}_n^B$ et $n \notin I_c$, $U_n=A$ si
  $n=c_{2k}$ avec $k \geq 1$ et $U_n=B$ si $n=c_{2k+1}$ avec $k \geq 0$.
  Montrer que cette stratégie est optimale i.e. $G_n\rightarrow
  \sup(\te^A,\te^B)$ p.s. \'Ecrire un programme illustrant le bandit à deux
  bras où les paramètres $\te^A$ et $\te^B$ sont affectés par l'utilisateur.
\end{exo}

\begin{exo}[Processus auto-régressif] On considère le processus autorégressif 
  $X_{n+1}=\te X_n + \veps_{n+1}$ avec $X_0=0$, où la suite $(\veps_n)_n$
  est i.i.d. centrée, de variance $\si^2$. On estime les paramètres inconnus
  $\te$ et $\si^2$ par
  $$
  \WH{\te}_n=\frac{\sum_{k=1}^n X_kX_{k-1}}{\sum_{k=0}^{n-1}X_k^2}%
  \text{\quad et \quad} %
  \WH{\si}_n^2=\frac{1}{n}\sum_{k=1}^n (X_k - \WH{\te}_{k-1}X_{k-1})^2.
  $$
  \begin{enumerate}
  \item\textbf{Cas stable.} $|\te|<1$. Montrer que $(\WH{\te}_n)_n$ CV
    p.s. vers $\te$ et que $(\sqrt{n}\,(\WH{\te}_n-\te))_n$ CV en loi
    vers $\cN(0,1-\te^2)$.  De plus, $(\WH{\si}_n^2)_n$ CV p.s. vers
    $\si^2$ et si les $\veps_n$ admettent un moment d'ordre 
    $4$ fini $\tau^4$, alors $(\sqrt{n}\,(\WH{\si}_n^2-\si^2))_n$ CV
    en loi vers $\cN(0,\tau^4)$.
  \item\textbf{Cas instable.} $|\te|=1$. Montrer que $(\WH{\te}_n)_n$
    CV p.s. vers $\te$ et que $(n\,(\WH{\te}_n-\te))_n$ CV en loi
    vers $\cL(\te L)$ où la v.a. $L$ est donnée par 
    $L:=\int_0^1B_t\,dB_t/\int_0^1B_t^2dt$ où $(B_t)_{t\geq0}$ est
    un mouvement brownien standard issu de $0$. D'autre part, vérifier que
    $(\WH{\si}_n^2)_n$ CV p.s. vers $\si^2$ et que si les $\veps_n$ 
    admettent un moment d'ordre scritement supérieur à $4$ fini,
    $(\sqrt{n}(\WH{\si}_n^2-\si^2))_n$ CV en loi vers $\cN(0,\tau^4)$.
  \item\textbf{Cas explosif.} $|\te|>1$. Montrer que $(\WH{\te}_n)_n$
    CV p.s. vers $\te$ et que dans le cadre gaussien,
    $((\te^2-1)^{-1}|\te|^n(\WH{\te}_n-\te))_n$ CV en loi vers une
    loi de Cauchy. D'autre part, vérifier que 
    $(\WH{\si}_n^2)_n$ CV p.s. vers $\si^2$ et que si les $\veps_n$ 
    admettent un moment d'ordre strictement supérieur à $4$ fini, 
    $(\sqrt{n}\,(\WH{\si}_n^2-\si^2))_n$ CV en loi vers 
    $\cN(0,\tau^4)$.
  \end{enumerate} 
  \'Ecrire un programme illustrant ces résultats de convergence lorsque
  $(\veps_n)_n$ est associée à $\cN(0,\si^2)$. 
\end{exo}

\begin{exo}[Nombre de records] 
  Soit $(X_{n})_{n\geq 1}$ une suite de v.a.r. i.i.d. de loi de densité $f$.
  Pour tout $n\geq 1$, on note
  $R_n$ le rang relatif de $X_{n}$, défini par
  $R_{n}=1+\sum_{k=1}^{n}\rI_{\{X_{k}> X_{n}\}}$.  Montrer que les variables
  aléatoires $R_1, \ldots, R_n$ sont indépendantes avec, pour tout
  $n\geq 1$, $ \dP(R_{n}=r_{n})=1/n$ où $r_{n}\in\{1,2,\ldots,n\}$.  Pour
  $n\geq 1$, si $R_{n}=1$, on dit qu'il se produit un record à l'instant $n$.
  On s'intéresse à la variable aléatoire $Z_{n}$ comptant le nombre de records
  jusqu'à l'instant $n$, $Z_{n}=\sum_{k=1}^{n}\rI_{\{R_{k}=1\}}$.  Montrer que
  $Z_{n}/\log n \rightarrow 1$ p.s. et
  $$
  \frac{Z_n -\log(n)}{\sqrt{\log n}}\limL{n}\cN(0,1).
  $$
  \'Ecrire un programme illustrant ces résultats de convergence
\end{exo}

{\tiny
\bibliographystyle{smfplain}
\bibliography{biblio}
}

\end{document}