path: root/rapport.tex

\documentclass[titlepage,11pt]{article}
\usepackage[french]{babel}
\usepackage[utf8x]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{calc,amsmath,amssymb,amsthm}
\usepackage[hmargin=3.5cm]{geometry}
\usepackage{}
\newcommand{\trib}[1]{\mathcal{#1}}
\newcommand{\set}[1]{\mathbf{#1}}
\newcommand{\esp}[1]{\mathbb{E}\left[#1\right]}
\newcommand{\espc}[2]{\mathbb{E}\left[#1|#2\right]}
\newcommand{\prob}[1]{\mathbb{P}\left[#1\right]}
\renewcommand{\geq}{\geqslant}
\renewcommand{\leq}{\leqslant}
\newsavebox{\fmbox}
\newenvironment{encadre}[1]{\begin{lrbox}{\fmbox}%
\begin{minipage}{\textwidth-3em}\vspace{\baselineskip}}{\vspace{0.5\baselineskip
} \end{minipage} \end{lrbox} \begin{center}
\fbox{\hspace{1em}\usebox{\fmbox}\hspace{1em}}\end{center}}

\author{Thibaut Horel}
\title{Prédiction de suites individuelles}
\date{sujet encadré par Gilles Stoltz}

\newtheoremstyle{remark}
  {}%      Space above, empty = `usual value'
  {}%      Space below
  {}% Body font
  {}%         Indent amount (empty = no indent, \parindent = para indent)
  {\scshape}% Thm head font
  {.}%        Punctuation after thm head
  { }%     Space after thm head: " " = normal interword space;
  {}% Thm head spec

\theoremstyle{definition}
\newtheorem{prop}{Proposition}[section]
\newtheorem{thm}[prop]{Théorème}
\newtheorem{cor}[prop]{Corollaire}
\newtheorem{lem}[prop]{Lemme}
\newtheorem*{defi}{Définition}

\theoremstyle{remark}
\newtheorem*{rem}{Remarque}

\begin{document}

\maketitle

\section{Prédiction randomisée dans un univers fini}

\subsection{Introduction (A DETAILLER)}
$N$ le nombre d'actions.

Une stratégie est une suite de lois de probabilités
$(\mathbf{p_t})_{t\in\set{N}^*}$ avec $\mathbf{p_t}\in\set{R}^N$.

La stratégie de l'adversaire est une suite de vecteur de pertes
$(\mathbf{l_t})_{t\in\set{N}^*}$ avec $\mathbf{l_t}\in\set{R}^N$.

À chaque tour, on tire $I_t$ suivant la loi $\mathbf{p_t}$.

On définit le regret pour la stratégie $\mathbf{p}$ contre la stratégie
$\mathbf{l}$ :
\[
R_T(\mathbf{p},\mathbf{l})=\sum_{t=1}^T l_{I_t,t}-\min_{1\leq i\leq N}L_{i,T}
\]
et le regret espéré :
\[
R_T^*(\mathbf{p},\mathbf{l}) =
\sum_{t=1}^T\sum_{i=1}^N p_{i,t}l_{i,t}
-\min_{1\leq i\leq N}L_{i,T}
\]

Si l'on souhaite raisonner avec les gains, en posant $g_{i,t}=1-l_{i,t}$, on
définit le regret en terme de gains :
\[
R_T(\mathbf{p},\mathbf{g})=
\max_{1\leq i\leq N}G_{i,T}
-\sum_{t=1}^T g_{I_t,t}
\]
et le regret espéré en termes de gains :
\[
R_T^*(\mathbf{p},\mathbf{g}) =
\max_{1\leq i\leq N}G_{i,T}
-\sum_{t=1}^T\sum_{i=1}^N p_{i,t}g_{i,t}
\]

\begin{rem}
Les symboles $R_T$ et $R_T^*$ n'ont pas la même définition suivant que l'on
parle de gains et de pertes. Si $\mathbf{g}$ est la suite de gains associée à
la suite de pertes $\mathbf{l}$, on a les égalités :
\[
R_T(\mathbf{p},\mathbf{l})=R_T(\mathbf{p},\mathbf{g})
\quad\mathrm{et}\quad
R_T^*(\mathbf{p},\mathbf{l})=R_T^*(\mathbf{p},\mathbf{g})
\]
\end{rem}

\subsection{Stratégie exponentielle et information totale}

\begin{encadre}{\textwidth}
\begin{center}
\textbf{Stratégie par poids exponentiels}
\end{center}

\textbf{Initialisation :} On pose $w_{i,0}=1$ et $p_{i,1}=1/N$ pour
$i\in\{1,\ldots,N\}$.

À chaque tour $t\geq 1$ :

\begin{enumerate}
\item On tire $I_t\in\{1,\ldots,N\}$ suivant la loi
$\mathbf{p_t}=(p_{1,t},\ldots,p_{N,t})$.
\item On observe les gains $\mathbf{g_t}=(g_{1,t},\ldots,g_{N,t})$.
\item On met à jour les poids exponentiels :
$w_{i,t}=w_{i,t-1}\exp(\eta g_{i,t})$.
\item On calcule la distribution pour le tour suivant :
\[
p_{i,t+1}=w_{i,t}/W_t
\quad\bigg(\mathrm{avec}\ W_t=\sum_{i=1}^{N}w_{i,t}\bigg)
.\]
\end{enumerate}
\end{encadre}

\begin{thm}\label{infototale}
On suppose que les gains sont bornés par $K\geq 0$, alors, pour tout $\eta$ tel
que $\eta K\leq 1$ :
\[
R_n^* \leq\frac{\ln N}{\eta}
+\eta\sum_{t=1}^T\sum_{i=1}^N p_{i,t}g_{i,t}^2
\]
\end{thm}

\begin{proof}
On minore puis on majore le log-rapport :
\[
\ln\left(\frac{W_T}{W_{0}}\right)
=\ln\left(\sum_{i=1}^N\exp(\eta G_{i,T})\right)-\ln N \\
\geq \eta \max_{1\leq i\leq N}G_{i,T}-\ln N
\]

Pour la majoration, on remarque que :
\[
\ln\left(\frac{W_t}{W_{t-1}}\right)
=\ln\left(\sum_{i=1}^N
\frac{w_{i,t-1}}{W_{t-1}}\exp(g_{i,t})\right)
=\ln\esp{\exp(\eta X)}
\]
où $X$ est une variable aléatoire qui vaut $g_{i,t}$ avec
probabilité $p_{i,t}$. On peut donc appliquer le lemme
\ref{espexp}, on obtient :
\[
\ln\left(\frac{W_t}{W_{t-1}}\right)
\leq\eta\sum_{i=1}^N p_{i,t}g_{i,t}
+\eta^2\sum_{i=1}^N p_{i,t}g_{i,t}^2
\]

On somme pour $t\in\{1,\ldots,N\}$ et on combine avec la minoration :
\[
\eta \max_{1\leq i\leq N}G_{i,T}-\ln N 
\leq \eta\sum_{t=1}^T\sum_{i=1}^N p_{i,t}g_{i,t}
+\eta^2 \sum_{t=1}^T\sum_{i=1}^N p_{i,t}g_{i,t}^2
.\]

Enfin on réordonne et on divise par $\eta$.
\end{proof}

\subsection{Bandits à $N$ bras}
On utilise la stratégie de prédiction suivante :

\begin{encadre}{\textwidth}
\begin{center}
\textbf{Algorithme Exp3.P}
\end{center}

\textbf{Initialisation :} On pose $w_{i,0}=1$ et $p_{i,1}=1/N$ pour
$i\in\{1,\ldots,N\}$.

À chaque tour $t\geq 1$ :

\begin{enumerate}
\item On tire $I_t\in\{1,\ldots,N\}$ suivant la loi
$\mathbf{p_t}=(p_{1,t},\ldots,p_{N,t})$.
\item On estime les gains
$\mathbf{\widetilde{g}}=(\widetilde{g}_{1,t},\ldots,\widetilde{g}_{N,t})$ à
partir du gain observé $g_{I_t,t}$
\[
\widetilde{g}_{i,t}=\frac{1}{p_{i,t}}\left(g_{I_t,t}\mathbf{1}_{\{I_t=i\}}
+\beta\right)
\]

\item On met à jour les poids exponentiels :
$w_{i,t}=w_{i,t-1}\exp(\eta\widetilde{g}_{i,t})$.
\item On calcule la distribution pour le tour suivant :
\[p_{i,t+1}=(1-\gamma)\frac{w_{i,t}}{W_t}+\frac{\gamma}{N}
\quad\bigg(\mathrm{avec}\ W_t=\sum_{i=1}^{N}w_{i,t}\bigg)\]
\end{enumerate}
\end{encadre}

\begin{thm}
Avec  :
\[\beta\leq 1,\quad
\gamma\leq \frac{1}{2},\quad
\eta\leq \frac{\gamma}{2N}
\]
\end{thm}

\newpage

\subsection{Preuve}
On a une information totale sur les gains estimés, donc en notant
$q_{i,t}=w_{i,t}/W_t$ et en appliquant le résultat du théorème \ref{infototale}
: 
\begin{equation}\label{fullinfo}
R_T^*(\mathbf{q},\mathbf{\widetilde{g}})\leq\frac{\ln N}{\eta}
+\eta\sum_{t=1}^T\sum_{i=1}^N q_{i,t}\widetilde{g}_{i,t}^2
\end{equation}

puis en utilisant que $p_{i,t}\geq q_{i,t}(1-\gamma)$
\[
\begin{split}
R_T^*(\mathbf{p},\mathbf{\widetilde{g}})
&\leq\max_{1\leq i\leq N}\widetilde{G}_{i,T}
-(1-\gamma)\sum_{t=1}^T\sum_{i=1}^N q_{i,t}\widetilde{g}_{i,t}\\
&=(1-\gamma)R_n^*(\mathbf{q},\mathbf{\widetilde{g}})
+\gamma\max_{1\leq i\leq N}\widetilde{G}_{i,T}
\end{split}
\]
et en utilisant \eqref{fullinfo} :
\begin{equation}\label{base}
R_T^*(\mathbf{p},\mathbf{\widetilde{g}})
\leq \frac{\ln N}{\eta}
+\eta\sum_{t=1}^T\sum_{i=1}^N p_{i,t}\widetilde{g}_{i,t}^2
+\gamma\max_{1\leq i\leq N}\widetilde{G}_{i,T}
\end{equation}

Vu le choix de l'estimateur de gain, on a :
\[
\sum_{t=1}^T\sum_{i=1}^N p_{i,t}\widetilde{g}_{i,t}
=\sum_{t=1}^T\sum_{i=1}^N
\left(g_{I_t,t}\mathbf{1}_{\{I_t=i\}}+\beta\right)=\sum_{t=1}^T g_{I_t,t}
+TN\beta
\]
et :
\[
\sum_{t=1}^T\sum_{i=1}^N p_{i,t}\widetilde{g}_{i,t}^2
\leq(1+\beta)\sum_{i=1}^N\widetilde{G}_{i,t}
\leq(1+\beta)N\max_{1\leq i\leq N}\widetilde{G}_{i,t}
\]

D'où on déduit de \eqref{base}, en posant $C=\gamma+\eta(1+\beta)N$:
\[
R_T(\mathbf{p},\mathbf{g})
+\max_{1\leq i\leq N}\widetilde{G}_{i,T}
-\max_{1\leq i\leq N}G_{i,T}
\leq \frac{\ln N}{\eta}
+TN\beta
+C\max_{1\leq i\leq N}\widetilde{G}_{i,t}
\]
\begin{equation}\label{etape2}
R_T(\mathbf{p},\mathbf{g})
\leq \frac{\ln N}{\eta}
+TN\beta
+\max_{1\leq i\leq N}G_{i,T}
+(C-1)\max_{1\leq i\leq N}\widetilde{G}_{i,t}
\end{equation}

% On souhaite maintenant relier les gains estimés aux gains
% réels. On remarque que :
% \[
% \espc{g_{i,t}-\widetilde{g}_{i,t}}{\trib{F}_{t-1}}=-\frac{\beta}{p_{i,t}}
% .\]
% Donc le processus $(X_t)$ défini par
% \[
% X_t=g_{i,t}-\widetilde{g}_{i,t}+\frac{\beta}{p_{i,t}}
% ,\]
% est une suite d'accroissements de martingale.

On souhaite maintenant relier les gains estimés aux gains
réels. On choisit $\beta=\sqrt{\ln(N/\delta)/TN}$, alors avec probabilité
supérieure à $1-\delta$ :
\[
\max_{1\leq i\leq N} G_{i,T}-\max_{1\leq i\leq N}\widetilde{G}_{i,T}
\leq TN\beta = \sqrt{TN\ln\left(\frac{N}{\delta}\right)}
\]
d'où en remarquant que $0\leq 1-C\leq 1$ :
\[
(1-C)\max_{1\leq i\leq N} G_{i,T}
+(C-1)\max_{1\leq i\leq N}\widetilde{G}_{i,T}
\leq TN\beta
\]
puis, vu que $\max_{1\leq i\leq N} G_{i,T}\leq T$ :
\[
\max_{1\leq i\leq N} G_{i,T}
+(C-1)\max_{1\leq i\leq N}\widetilde{G}_{i,T}
\leq TN\beta+CT
\]
en injectant cette dernière majoration dans \eqref{etape2}, on obtient
finalement :
\[
R_T(\mathbf{p},\mathbf{g})
\leq \frac{\ln N}{\eta}
+2TN\beta+\big(\gamma+\eta(1+\beta)\big)T
\]

\section{Prédiction dans un univers convexe}
Soit $F$ un convexe compact de $\set{R}^n$. À chaque tour on choisit un
élément $x_t$ dans $F$ tandis que l'adversaire choisit une fonction de perte
convexe $l_t : F\longrightarrow \set{R}^+$.

On définit le regret par rapport à une stratégie fixe :
\[
R_T(\mathbf{x},\mathbf{l})=\sum_{t=1}^T l_t(x_t) - \min_{x\in F}\sum_{t=1}^T
l_t(x)
\]

On veut obtenir des bornes sur le regret valables pour toute stratégie de
l'adversaire.

\subsection{Réduction au cas des pertes linéaires}

\begin{prop}
Pour toute stratégie convexe $\mathbf{l}$ de l'adversaire, il existe une
stratégie linéaire $\mathbf{l'}$ de l'adversaire telle que :
\[
R_T(\mathbf{x},\mathbf{l})\leq R_T(\mathbf{x},\mathbf{l'})
\]
\end{prop}

\begin{proof} (A PRECISER)
Il suffit de considérer une suite de sous-gradients des fonctions $l_t$.
\end{proof}

On peut donc se restreindre à l'étude du regret pour des fonctions de perte
linéaire. Dans ce cas on identifie la fonction de perte est représentée par un
vecteur que l'on nomme également $l_t$. On a donc $l_t(x_t)=l_t\cdot x_t$.

\subsection{Cas de l'information totale}

On considère ici qu'à chaque tour on observe le vecteur $l_t$ (et pas seulement
$l_t\cdot x_t$).
On fixe une suite $(\eta_t)_{t\in\set{N}^*}$. On utilise alors la stratégie
suivante :
\[
x_{t+1}=p_F(x_t-\eta_t l_t)
\]
où $p_F$ est la projection sur le convexe fermé $F$ comme rappelée en
appendice.

Dans le cas d'une fonction de perte linéaire, le vecteur $l_t$ s'identifie au
gradient de la fonction de perte. La stratégie ci-dessus s'apparente donc à une
descente de gradient gloutonne.

\begin{thm}
Si toutes les fonctions de pertes sont bornées par la même constante $K$ et que
l'on note $D$ le diamètre du compact $F$, alors on a :
\[
R_T(\mathbf{x},\mathbf{l})
\leq\frac{D^2}{2\eta_T}
+\frac{K^2}{2}\sum_{t=1}^T \eta_t
\]

En particulier, en prenant $\eta_t=\frac{1}{\sqrt{t}}$, on obtient :
\[
R_T(\mathbf{x},\mathbf{l})
\leq\frac{D^2}{2}\sqrt{T}
+K^2\left(\sqrt{T}-\frac{1}{2}\right)
\]
\end{thm}

\begin{proof} (A PRECISER) majoration du corollaire \ref{projection} +
transformation d'Abel.
\end{proof}

 
\section{Appendice}

\subsection{Quelques résultats d'analyse réelle}

\begin{lem}\label{inegexp}
La fonction $x\longmapsto (e^x-x-1)/x^2$ est croissante sur $\set{R}$. 
\end{lem}

\begin{proof}
Évident.
\end{proof}

\begin{lem}\label{majorationh}
Pour tout $x\in\set{R}^+$ :
\[
(1+x)\ln(1+x)-x\geq \frac{x^2}{2+\frac{2}{3}x}
\]
\end{lem}

\begin{proof}
Les deux fonctions apparaissant de part et d'autre de l'inégalité s'éga\-lent en
0, de même que leurs dérivées premières. Par développement de Taylor avec
reste intégrale, il suffit donc de montrer l'inégalité pour les dérivées
secondes, ce qui s'écrit : 
\[
\frac{1}{1+x}\geq \left(\frac{1}{1+\frac{x}{3}}\right)^3
\]
que l'on sait vraie car $(1+x)^3\geq 1+3x$ si $x>0$.  
\end{proof}

\subsection{Inégalités de variables aléatoires}

On commence avec un lemme de « type Hoeffding » où on remplace un majorant de
la variance par la variance elle-même.

\begin{lem}\label{espexp}
Soient $X$ une variable aléatoire et $\eta\in\set{R}^+$ tels que $\eta X\leq 1$
alors :
\[
\ln\esp{\exp(\eta X)}\leq \eta \esp{X} +\eta^2(e-2)\esp{X^2}
.\]
\end{lem}

\begin{proof}
On a $\eta X\leq 1$, donc en appliquant le lemme \ref{inegexp}, on a :
\[
\exp(\eta X) \leq 1 +\eta X + \eta^2(e-2)X^2
\]

On conclut alors en prenant l'espérance puis en majorant $\ln(1+x)$ par $x$.
\end{proof}


\subsection{Inégalités de martingale}

Dans cette partie on s'intéressera toujours à un processus aléatoire
$(X_t)_{t\in\set{N}^*}$ adapté à la filtration
$(\trib{F}_t)_{t\in\set{N}}$. $\trib{F}_0$ est la tribu triviale.

\begin{defi}
On dit que $(X_t)$ est une suite d'accroissements de martingale si et seulement
si :
\[
\forall t \in \set{N}^*,\quad \espc{X_t}{\trib{F}_{t-1}}=0,
\]
ce qui signifie également que le processus $(Y_T)$ défini par :
\[
\forall T \in \set{N}^*,\quad Y_T=\sum_{t=1}^{T}X_t
\]
est une martingale par rapport à la filtration $(\trib{F}_T)$.
\end{defi}

\begin{lem}\label{lembernstein}
Soient $X$ une variable aléatoire avec $X\leq 1$ et $\trib{F}$ une tribu telle
que $\espc{X}{\trib{F}}=0$, alors :
\[
\forall\eta\in\set{R}^+,\quad \espc{\exp(\eta X)}{\trib{F}}
\leq \exp\left(\espc{X^2}{\trib{F}}(e^\eta-\eta-1)\right)
\]
\end{lem}

\begin{proof}
On a $\eta X\leq \eta$, donc grâce au lemme \ref{inegexp} :
\[
\exp(\eta X)-\eta X-1\leq X^2(e^\eta-\eta-1)
.\]

En prenant de part et d'autre l'espérance conditionelle :
\[
\espc{\exp(\eta X)}{\trib{F}}\leq 1 +(e^\eta-\eta-1)\espc{X^2}{\trib{F}}
.\]

On conclut alors en utilisant $1+u\leq\exp(u)$ si $u\in\set{R}$.
\end{proof}

\begin{lem}
Soit $(X_t)$ une suite d'accroissements de martingale majorée par 1. Notons :
\[
\forall T \in \set{N}^*, \quad S_T=\sum_{t=1}^T X_t, \quad V_T=\sum_{t=1}^T
\espc{X_t^2}{\trib{F}_{t-1}},
,\]
et définissons, pour $\eta\in\set{R}^+$, le processus $(M_t)$ par :
\[
\forall t \in \set{N}^*,\quad
M_t=\exp\big(\eta S_t-V_t\left(e^{\eta}-\eta-1\right)\big)
,\]
alors $(M_t)$ est une surmartingale par rapport à la filtration $(\trib{F}_t)$
et $\esp{M_1}\leq 1$.
\end{lem}

\begin{proof}La majoration de $\esp{M_1}$ est une application directe du
lemme \ref{lembernstein}. Pour le caractère surmartingale, soit $t\geq 2$, on
a :
\[\begin{split}
\espc{M_t}{\trib{F}_{t-1}}
&=\espc{\exp\big(\eta S_t-V_t(e^{\eta}-\eta-1)\big)}{\trib{F}_{t-1}} \\ 
&=M_{t-1}\mathbb{E}\Big[\exp\big(\eta
X_t-\espc{X_t^2}{\trib{F}_{t-1}}(e^{\eta}-\eta-1)\big)\big|\trib{F}_{t-1
}\Big] \\
&=M_{t-1} \frac{\espc{\exp\left(\eta
X_t\right)}{\trib{F}_{t-1}}}{\exp\left(\espc
{X_t^2}{\trib{F}_{t-1}}(e^{\eta}-\eta-1)\right)}\\
&\leq M_{t-1}
\end{split}
\]
où la dernière inégalité provient du lemme \ref{lembernstein}.
\end{proof}

De même qu'on peut étendre l'inégalité de Hoeffding aux suites d'accroissements
de martingales pour obtenir l'inégalité de Hoeffding-Azuma, on peut étendre
ainsi l'inégalité de Bernstein :

\begin{prop}
Soit $(X_1,\ldots,X_T)$ une suite d'accroissements de
martingale par rapport à la filtration $(\trib{F}_t)$. Supposons
qu'ils existent $K>0$ tel que :
\[
\forall t \in \{1,\ldots,T\},\quad X_t\leq K,
\]
et $\sigma^2$ tel que $V_T\leq \sigma^2$, alors avec les mêmes notations que
précédemment, on a:
\[
\forall\varepsilon>0,\quad
\prob{\max_{1\leq t\leq T}S_t>\varepsilon}
\leq
\exp\left(-\frac{\varepsilon^2}{2\sigma^2+\frac{2}{3}K\varepsilon}\right)
\]
\end{prop}

\begin{proof} Par homogénéité, on se ramène aux cas où
$K=1$. Soit $\varepsilon$ fixé, on a, pour tout
$\eta\in\set{R}^+$ :
\[
\begin{split}
\prob{\max_{1\leq t\leq T}S_t>\varepsilon}
&=\prob{\eta\max_{1\leq t\leq T}S_t>\eta\varepsilon} \\
&\leq \prob{\max_{1\leq t\leq T}M_t
>\exp\left(\eta\varepsilon-\sigma^2(e^\eta-\eta-1)\right)}
\end{split}
\]

Puis en utilisant successivement l'inégalité de Doob et le
lemme \ref{lembernstein} :
\[
\begin{split}
\prob{\max_{1\leq t\leq T}S_t>\varepsilon}
&\leq \exp\big(\sigma^2(e^\eta-\eta-1)-\eta\varepsilon\big)\esp{M_1}\\
&\leq \exp\big(\sigma^2(e^\eta-\eta-1)-\eta\varepsilon\big)
\end{split}
\]

La borne de droite est minimale pour
$\eta=\ln\left(1+\frac{\varepsilon}{\sigma^2}\right)$ et donne la majoration : 
\[
\prob{\max_{1\leq t\leq T}S_t>\varepsilon} 
\leq \exp\left(-\sigma^2 h\left(\frac{\varepsilon}{\sigma^2}\right)\right)
\]
avec $h(x)=(1+x)\ln(1+x)-x$.

On conclut alors en utilisant le lemme \ref{majorationh}.
\end{proof}

\begin{cor}
Soit $\delta\in[0,1]$, alors avec les mêmes
hypothèses que précédemment et probabilité supérieure à $1-\delta$ :
\[
S_T\leq\frac{2K}{3}\ln\left(\frac{1}{\delta}\right)+
\sqrt{2\sigma^2\ln\left(\frac{1}{\delta}\right)}
.\]
\end{cor}

\begin{proof}
On pose $\delta$ égal au membre de droite de l'inégalité de
Bernstein, puis on exprime $\varepsilon$ en fonction de $\delta$. On obtient
avec probabilité $1-\delta$ :
\[
S_T\leq \frac{K}{3}\ln\left(\frac{1}{\delta}\right)+
\sqrt{\frac{K^2}{9}\ln\left(\frac{1}{\delta}\right)^2+
2\sigma^2\ln\left(\frac{1}{\delta}\right)}
.\]

Puis on conclut en utilisant $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ si $a>0$ et
$b>0$.
\end{proof}

On peut également appliquer l'inégalité de Bernstein d'une autre façon, quitte
à renforcer les hypothèses, pour obtenir une inégalité faisant apparaître
directement la variance conditionnelle du processus :

\begin{cor}
Soit $(X_1,\ldots,X_T)$ une suite d'accroissements de
martingale par rapport à la filtration $(\trib{F}_t)$. Supposons que $V_T\geq
1$ et qu'il existe $K>0$ tel que :
\[
\forall t \in \{1,\ldots,T\},\quad \left|X_t\right|\leq K,
\]
alors, avec probabilité supérieure à $1-\delta$ et pour $T\geq 3$ :
\[
\forall C\in\left]1 ;+\infty\right[,\quad
S_T\leq\frac{2K}{3}\ln\left(\frac{\ln T}{\delta}\frac{(1+\ln C)}{\ln C}\right)+
\sqrt{2CV_T\ln\left(\frac{\ln T}{\delta}\frac{(1+\ln C)}{\ln C}\right)}
.\]

En particulier, en choisissant $C=3/2$, on obtient :
\[
S_T\leq\frac{2K}{3}\ln\left(\frac{\ln T}{\delta/4}\right)+
\sqrt{3V_T\ln\left(\frac{\ln T}{\delta/4}\right)}
.\]
\end{cor}

\begin{proof}
Posons $N=\lceil\ln T/\ln C\rceil$
D'après le corollaire précédent, pour tout $r\in\{1,\ldots,N\}$ :
\[
\prob{S_T\geq \frac{2K}{3}\ln\left(\frac{N}{\delta}\right)+
\sqrt{2K^2C^r\ln\left(\frac{N}{\delta}\right)}
\ \mathrm{et}\ V_T\leq K^2C^r}\leq\frac{\delta}{N}
\]

D'où :
\[
\prob{S_T\geq \frac{2K}{3}\ln\left(\frac{N}{\delta}\right)+
\sqrt{2CV_T\ln\left(\frac{N}{\delta}\right)}
\ \mathrm{et}\ K^2C^{r-1}\leq V_T\leq K^2C^r}\leq\frac{\delta}{N}
\]

Or, vu que $1\leq V_T\leq K^2T\leq K^2C^N$, en sommant l'inégalité précédente
pour
$r\in\{1,\ldots,N\}$, on obtient :
\[
\prob{S_T\geq \frac{2K}{3}\ln\left(\frac{N}{\delta}\right)+
\sqrt{2CV_T\ln\left(\frac{N}{\delta}\right)}}\leq\delta
.
\]

On conclut en remarquant que, si $T\geq 3$ :
\[
N\leq\frac{\ln T}{\ln C}+1=\ln T\frac{(1+\ln C/\ln T)}{\ln C}
\leq \ln T\frac{(1+\ln C)}{\ln C}\qedhere
\]
\end{proof}

\subsection{Projection sur un convexe fermé}

On se place dans un espace euclidien $E$. Si $x$ et $y$ sont dans $E$, on note
$x\cdot y$ le produit scalaire entre $x$ et $y$ et $\|x\|$ la norme euclidienne
associée. 

\begin{prop}
Soient $F$ une partie convexe fermée non vide de $E$ et $y\in E$. Alors, il
existe un unique $x\in F$ tel que :
\[
\|y-x\|=d(y,F)=\inf_{z\in F}\|y-z\|
.\]

De plus $x$ vérifie la propriété de l'angle obtus :
\[
\forall z\in F,\quad
(y-x)\cdot(z-x)\leq 0
\]

On dit que $x$ est la projection de $y$ sur le convexe $F$, et on note
$x=p_F(y)$.
\end{prop}

On en déduit notamment que pour tout $z\in F$, $\|y-p_F(y)\|\leq\|y-z\|$.
L'inégalité de l'angle obtus permet d'obtenir une autre inégalité.

\begin{cor}\label{projection}
Soient $F$ une partie convexe fermée non vide de $E$ et $y\in E$. Alors :
\[
\forall z\in F,\quad
\|z-p_F(y)\|\leq\|z-y\|
\]
\end{cor}

\begin{proof}
Soit $z\in F$, on part de l'inégalité de l'angle obtus :
\[
(y-p_F(y))\cdot(z-p_F(y))\leq 0
\]
d'où :
\[
(y-z+z-p_F(y))\cdot(z-p_F(y))
=\|z-p_F(y)\|^2-(z-y)\cdot(z-p_F(y))\leq 0
\]
puis en appliquant l'inégalité de Cauchy-Schwarz :
\[
\|z-p_F(y)\|^2\leq\|z-y\|\|z-p_F(y)\|\qedhere
\]
\end{proof}
\end{document}