\documentclass{article}
\usepackage{titling}
\author{Laura \textsc{Gay} et Florian \textsc{Lemonnier}}
\include{preambule}
\include{preambuleflo}


\newboxedtheorem{defi}{Définition}{compteur1}
\newboxedtheorem{prop}{Proposition}{}
\newboxedtheorem{lem}{Lemme}{}
\newboxedtheorem{coro}{Corollaire}{compteur3}
\newboxedtheorem{thm}{Théorème}{compteur4}
\newboxedtheorem{exe}{Exemple}{compteur5}


\renewenvironment{proof}[1][]{{\underline{\bfseries \proofname #1 :}\\ }}{\hfill $\blacksquare$\\}

\begin{document}
\renewcommand{\proofname}{Preuve}

\begin{spacing}{2}
\setlength {\shadowsize }{2pt}
\begin{center} \shadowbox{\begin{minipage}{15cm}
\centering     \begin{huge} 
\textsc{Inégalité de Hoeffding}\end{huge}
\end{minipage}} \end{center}\end{spacing}
~\\


\underline{Référence :} \textsc{Ouvrard 2} : p. 128 + \textsc{Cadre-Vial} p.36 pour l'application\\
\underline{Lecons:} : 229, 253, 260,261,262.\\
~\\
\textbf{Notation:} On note $L_X(t)=\mathbb{E}[\e^{tX}]$ la transformée de Laplace de la variable aléatoire $X$.\\

\begin{lem}
Soit $X$ une variable aléatoire réelle $\IP$-ps bornée par 1 ie $\abs{X} \leq 1$ $\IP$-ps. On suppose que $X$ est centrée. On a: 
$$ L_X(t) \leq \exp \left( \frac{t^2}{2}\right)$$
\end{lem}
~\\
\begin{proof}
\begin{description}
\item[Etape 1:] Mq pour $t\in \R$, $x \in [-1,1]$, $\exp(tx) \leq \frac12(1-x)\exp(-t)+\frac12(1+x)\exp(t)$\\
C'est juste de la convexité car:
$$0\leq \lambda_1=\frac12(1-x) \leq 1$$
$$0\leq \lambda_2=\frac12(1+x) \leq 1$$
$$\lambda_1+\lambda_2=1$$
Et enfin
$$tx=\lambda_1(-t)+\lambda_2t$$
Comme $x \mapsto \exp (tx)$ est convexe (avec sa dérivée seconde), on a l'inégalité souhaitée.\\
\item[Etape 2:] Mq $L_X(t) \leq \frac12 (\exp(-t)+\exp(t))$.\\
Déjà, comme $X$ est ps bornée par 1, $\exp (tx)$ est bornée ps et admet donc une moyenne. Ainsi $L_X(t)$ existe. \\
Avec l'étape 1 on a, pour $t\in \R$, et ps, 
$$\exp(tX) \leq \frac12(1-X)\exp(-t)+\frac12(1+X)\exp(t)$$
et donc
$$L_X(t) \leq \frac12\mathbb{E}[1-X]\exp(-t)+\frac12\mathbb{E}[1+X]\exp(t) $$
Comme $X$ est centrée:
$$L_X(t) \leq \frac12\left(\exp(-t)+\exp(t) \right) =\text{ch} (t)$$
Or ch$(t)=\sum_{n \in \N} \frac{t^{2n}}{(2n)!}$ et $\exp\left( \frac{t^2}{2} \right)=\sum_{n \in \N} \frac{t^{2n}}{n!2^n}$.\\
mais pour tout $n \in \N$, on a $n!2^n=2\cdot 4\cdots 2n \leq (2n)!$ donc ch$(t)\leq \exp\left( \frac{t^2}{2} \right)$.\\
Et finalement
$$L_X(t) \leq \exp \left( \frac{t^2}{2}\right)$$
\end{description} 
\end{proof}

\begin{prop}[Inégalité de Hoeffding - 1963]
Soit $\left(X_n\right)_{n \in \IN^*}$ une suite de variables aléatoires réelles, indépendantes, centrées.\\
De plus, on suppose que $\forall n \in \IN^*, X_n$ est ps bornée par $c_n$, où $c_n > 0$.\\
On note : $\dst \forall n \in \IN^*, S_n = \sum_{j=1}^n{X_j}$ et $\dst a_n = \sum_{j=1}^n{c_j^2}$.\\
Alors $\dst \forall \varepsilon > 0, \forall n \in \IN^*, \IP\left(\left|S_n\right| > \varepsilon\right) \leq 2 \exp\left(-\frac{\varepsilon^2}{2a_n}\right)$.
\end{prop}
~\\
\begin{proof}
\begin{description}
\item[Etape 1:] Mq pour tout $t$, $L_{S_n}(t) \leq \exp\left( \frac{t^2}{2} a_n\right)$\\
Fixons $n \in \N^*$.\\
      On applique le \textbf{Lemme} aux variables $\dst \frac{X_j}{c_j}$, où $j \in [\![1,n]\!]$ : 
			$\dst \forall t \in \IR, L_{X_j}(t) = L_{\frac{X_j}{c_j}}(t c_j) \leq \exp\left(\frac{t^2}{2} c_j^2\right)$.\\
			Mais par indépendance des $\exp\left(tX_j\right)$ pour $j \in [\![1,n]\!]$, il vient :
			\[ \forall t \in \IR, L_{S_n}(t) = \prod_{j=1}^n{L_{X_j}(t)} \leq \exp\left(\frac{t^2}{2}a_n\right).\]
\item[Etape 2:]  Mq pour tout $\epsilon>0$, $\IP(S_n>\epsilon) \leq \exp \left(-\frac{\epsilon^2}{2a_n} \right)$\\
Soient $t>0$ et $\varepsilon > 0$ ; on a : $S_n > \varepsilon \Leftrightarrow \erm^{tS_n} > \erm^{t\varepsilon}$.\\
      Ainsi, par l'inégalité de Markov\footnote{Soit $Z$ une variable aléatoire réelle positive ou nulle ps. Alors
$\forall a >0,\mathbb P(Z\geqslant a)\leqslant\frac{\mathbb{E}[Z]}{a}$}, on obtient :
			\[ \IP\left(S_n > \varepsilon\right) = \IP\left( \erm^{tS_n} > \erm^{t\varepsilon}\right)
			                                     \leq \frac{\IE\left[\erm^{tS_n}\right]}{\erm^{t\varepsilon}}
																					 = \erm^{-t\varepsilon} L_{S_n}(t)
																					 \leq \exp \left(-t\varepsilon + \frac{t^2}{2}a_n\right). \]
			Cette inégalité est vraie pour tout $t>0$. On va donc minimiser en $t$.\\
			$t \mapsto -t\varepsilon+ \frac{t^2}{2} a_n$ atteint son minimum en $t=\frac{\epsilon}{a_n}$ et ce minimum vaut $-\frac{\epsilon^2}{2a_n}$,  d'où :
			$$\dst \IP\left(S_n > \varepsilon\right) \leq \exp\left(\frac{\varepsilon^2}{a_n^2}\frac{a_n}{2} - \frac{\varepsilon}{a_n} \varepsilon\right)
			                                        = \exp\left(- \frac{\varepsilon^2}{2a_n}\right)$$
\item[Etape 3:] Conclusion\\
Si $\epsilon>0$. On a les égalités:
$$ \{\abs{S_n} > \epsilon \} = \{S_n>\epsilon\}\sqcup\{S_n < - \varepsilon\}$$
Comme ces ensembles sont disjoints:\\
      On a : $\IP \left(\left|S_n\right| > \varepsilon\right) = \IP \left(S_n > \varepsilon\right) + \IP \left(S_n < -\varepsilon\right)$.\\
			Mais on aurait pu appliquer tout ce qu'on vient de faire aux variables $-X_j$, où $j \in [\![1,n]\!]$, et donc :
			$\dst \IP \left( S_n < -\varepsilon \right) = \IP \left( -S_n > \varepsilon\right) \leq \exp \left( - \frac{\varepsilon^2}{2a_n}\right)$.\\
			Et finalement, $\dst \IP\left(\left|S_n\right| > \varepsilon \right) \leq 2 \exp\left(-\frac{\varepsilon^2}{2a_n}\right)$.
\end{description}
\end{proof}
\newpage
\section*{Application 1: un critère de convergence presque sûre}

\begin{prop}
Soit $\alpha > 0$ ; on ajoute l'hypothèse supplémentaire : $\exists \beta > 0, \forall n \in \IN^*, a_n \leq n^{2\alpha-\beta}$.\\
Alors : $\dst \frac{S_n}{n^\alpha} \underset{n \rightarrow \infty}{\overset{\text{ps}}{\longrightarrow}} 0$.\end{prop}
~\\
\begin{proof}
\begin{description}
\item[Etape 1:] Mq pour tout $\epsilon >0$, la série de terme général $\IP(\abs{S_n}>n^{\alpha} \epsilon)$ est convergente.\\
Soit $\varepsilon > 0$, on a\footnote{manque le $/2$ dans Ouvrard}, par Hoeffding :
$\dst \forall n \in \IN^*, \IP\left(\left|S_n\right| > n^\alpha \varepsilon\right) \leq 2 \exp\left(-\frac{n^{2\alpha} \varepsilon^2}{2a_n}\right) \leq 2 \exp\left(-\frac{n^\beta\varepsilon^2}{2}\right)$.\\
Mais la série $\dst \sum_{n \geq 1}{\exp\left(-\frac{n^\beta \varepsilon^2}{2}\right)}$ converge (par le critère de Riemann), car  à partir d'un certain rang, $\frac{\varepsilon^2}{2}n^\beta \geq 2 \ln n$ et donc
$0 \leq \exp\left(-\frac{n^\beta\varepsilon^2}{2}\right) \geq \frac{1}{n^2}$.\\
Ainsi, la série $\dst \sum_{n \geq 1}{\IP\left(\left|S_n\right| > n^\alpha \varepsilon\right)}$ converge

\item[Etape 2:] \footnote{On fait pas comme Ouvrard parce que c'est pas rigoureux.} Par Borel-Cantelli\footnote{Lemme de Borel-Cantelli: Soit $(A_n)_{n\geq 0}$ une suite dans $\mathcal{A}$. Si $\sum_{n\geq 0}\IP(A_n)<+\infty$, alors $\IP (\limsup_n A_n) = 0$} :
\[ \forall \varepsilon > 0, \IP\left(\limsup_{n \rightarrow \infty}{\left\{\left|S_n\right| > n^\alpha \varepsilon\right\}}\right) = 0 \text{, ie }
\IP\left(\liminf_{n \rightarrow \infty}{\left\{\left|S_n\right| \leq n^\alpha \varepsilon\right\}}\right) = 1.\]
En particulier, $\dst \forall p \in \IN^*, \IP\left(\bigcup_{n \in \IN^*}{\bigcap_{k \geq n}{\left\{\left|\frac{S_k}{k^\alpha}\right| \leq \frac{1}{p}\right\}}}\right) = 1$.\\
C'est-à-dire : $\dst \forall p \in \IN^*, \exists N_p \text{ négligeable}, \forall \omega \in N_p^{\text{c}}, \exists n \in \IN, \forall k \geq n, \left|\frac{S_k(\omega)}{k^\alpha}\right| \leq \frac{1}{p}$.\\
On pose alors $\dst N = \bigcup_{p \in \IN^*}{N_p}$, alors $N$ est négligeable et :
\[ \forall \omega \in N^{\text{c}}, \forall p \in \IN^*, \exists n \in \IN, \forall k \geq n, \left|\frac{S_k(\omega)}{k^\alpha}\right| \leq \frac{1}{p}.\]
Ou, en d'autres termes : $\dst \frac{S_n}{n^\alpha} \underset{n \rightarrow \infty}{\overset{\text{ps}}{\longrightarrow}} 0$.
\end{description}\end{proof}

\newpage
\section*{Application 2: calcul d'intervalles de confiance par excès}

Rappelons les conditions de l'inégalité:\\

\fbox{\begin{minipage}{17cm}
Soit $\left(X_n\right)_{n \in \IN^*}$ une suite de variables aléatoires réelles, indépendantes, centrées.\\
De plus, on suppose que $\forall n \in \IN^*, X_n$ est ps bornée par $c_n$, où $c_n > 0$.\\
On note : $\dst \forall n \in \IN^*, S_n = \sum_{j=1}^n{X_j}$ et $\dst a_n = \sum_{j=1}^n{c_j^2}$.\\
Alors $\dst \forall \varepsilon > 0, \forall n \in \IN^*, \IP\left(\left|S_n\right| > \varepsilon\right) \leq 2 \exp\left(-\frac{\varepsilon^2}{2a_n}\right)$.
\end{minipage}}
~\\
~\\
Plaçons-nous dans un modèle statistique $\left(\Hcal^n, \left\{P_\theta\right\}_{\theta \in \Theta}\right)$ avec $\Hcal \subset \IR$ et $\Theta \subset \IR^d$.
Le paramètre d'intérêt est $g(\theta)$ avec $g : \Theta \rightarrow \IR$ une fonction continue
On suppose que $X_1, \ldots, X_n$ sont indépendantes et identiquement distribuées, de loi $P_\theta$ \footnote{Par exemple, $\mathcal{B}(\theta)^{\otimes n}$}, bornées $P_\theta$-ps et avec $\IE_\theta\left[X_1\right] = g(\theta)$\footnote{Toujours dans notre exemple, $g(\theta)=\theta$.}.
Soit $c$ une borne $P_\theta$-presque sûre de $X_1-g(\theta)$\footnote{Ex: on va avoir $1 \leq -\theta \leq X_1-\theta \leq 1- \theta \leq 1$ donc bornées par $1$.}.
On veut un intervalle de confiance pour $g(\theta)$ donc on cherche par exemple $\IP\left(\abs{\overline{X_n}-g(\theta)}>\epsilon\right)$\\
Par Hoeffding, 
$$\dst P_\theta\left(\left|\overline{X_n}-g(\theta)\right| > \varepsilon\right)
                   = P_\theta\left(\left|\sum_{j=1}^n{\left(X_j-g(\theta)\right)}\right| > n\varepsilon\right)
								   \leq 2 \exp\left(-\frac{n^2 \varepsilon^2}{2nc^2}\right)
									 = 2 \exp\left(-\frac{n \varepsilon^2}{2c^2}\right)$$
Soit $\alpha \in ]0,1[$, on choisit $\varepsilon$ de sorte que $\dst \alpha = 2 \exp \left(-\frac{n\varepsilon^2}{2c^2}\right)$, ie :
$\dst \varepsilon = c \sqrt{\frac{2}{n} \ln \frac{2}{\alpha}}$.
Dès lors, on obtient l'intervalle de confiance par excès\footnote{Un intervalle de confiance par excès pour un paramètre $\theta$ de niveau de confiance $1-\alpha$ est une statistique $I$ telle que $\IP_{\theta}(\theta \in I) \geq \alpha$.} au niveau $1-\alpha$, pour $g(\theta)$ :
$$\dst I_\alpha = \left[ \overline{X_n} - c \sqrt{\frac{2}{n} \ln \frac{2}{\alpha}} , \overline{X_n} + c \sqrt{\frac{2}{n} \ln \frac{2}{\alpha}} \right]$$

\vspace{2cm}

\hrulefill \\
~\\
\underline{Notes:}\\
~\\
\checkmark ~\textbf{A l'oral}, selon la leçon, on fera l'une des deux applications (de préférence la deuxième). En allant un peu vite lemme 4'46, lemme + inega = 9', appli 1= 4'41, appli 2=3'37 ou 4'27 si on détaille pour des bernoulli. L'idée c'est si appli 1 aller vite sur Hoeffding quitte à prendre le temps pour l'appli qui manipule des choses délicates. Si appli 2, prendre plus de temps sur hoeffding et voir à la fin comment j'ai le temps de détailler. \\
$\clubsuit$ Wassily \textsc{Hoeffding} (1914 - 1991) est un statisticien et probabiliste finnois. Il est l'un des fondateurs des statistiques non-paramétriques. Il est surtout connu pour cette inégalité. 



\end{document}