
\section{Estimates of the binomial tail}
The Helmholtz principle leads  us to  evaluate as precisely as
possible a number of false alarms $\NFA(l,k,p)=N_{test}\cdot \prob
{S_l\geq k}$, where $S_l=\sum_{i=1}^l X_i$ and  $X_i$ are independent
Bernoulli random variables with parameter $p$, namely $\Prob{X_i=1}=p$ and
$\Prob{X_i=0}=1-p$. The number of tests $N_{test}$  being easily
calculated and generally just a simple function of the image size,
the estimation of the NFA boils down to an estimate of the tail of
the binomial law,
$$\Blkp(l, k, p)=\sum_{i=k}^l\binom{l}{i} p^i(1-p)^{l-i}.$$ In
this estimation problem,   $p$ is fixed,   $l$ is rather large and
$k$ in excess with respect to its expected value $pl$, since we
look for meaningful events.  The number of tests will be usually
very large and the NFA is interesting mainly when it is smaller
than 1; so we are primarily interested in good estimates of
$\Blkp(l, k, p)$ when this quantity is very small. There are
several tools available to do so.

\begin{itemize} \item The first one is
of course the {\bf law of large numbers}, which tells us that
$\Blkp(l, k, p)=\Prob{S_l\geq k}\to 0$ whenever $\frac kl \geq
r>p$ and $l\to \infty$. Now, this result yields no order of
magnitude for $\Blkp(l, k,  p)$.

\item {\bf Large deviations techniques} give  asymptotic estimates
of $\Blkp(l,k,p)$ when $k$ is roughly proportional to $l$, namely
$k\simeq rl$ with $r>p$.

\item The {\bf central limit theorem} also gives estimates for
smaller deviations from the mean, namely when $k\simeq pl +
C\sqrt{l}$.

\end{itemize}

We shall state these estimates along with some more precise
variants. Now, it is to be noticed that our estimation problem is
 not an asymptotic problem. We need a non
asymptotic precise evaluation of $\Blkp(l, k, p)$, valid if
possible for all values of $l, k, p$ and accurate whenever
$\Blkp(l, k, p)$ happens to be small.


 It can be objected that we could give up any estimate
of the binomial tail, as we can simply compute exact numerical
values of $\Blkp(l, k, p)$. These values can even be tabulated
once for all. This objection would be admissible if we were only
interested in the practical gestalt detection problem  in digital
images.

 Now, in practice as well as in theory, we will
   be interested in   explicit formulae
for the order of magnitude of the minimal value $k(l)$ for which a
gestalt with parameters $(l, k(l), p)$ becomes detectable. In the
next chapter (Chapter \ref{align.chap}) on the detection of alignments in a
digital image, we shall indeed be able to give estimates of the
minimal number $k(l)$ of aligned points in a segment of length $l$
to yield an alignment perception, this estimate being a simple
explicit function of $l$ and $p$. In Chapter \ref{modes.chap}, we
shall also be led to situations where $l$ is so large that the
actual computation of $\Blkp$ with computers  becomes cumbersome
and the large deviation estimate useful. Finally, in
Chapters \ref{max.chap} and \ref{modes.chap}, we shall deal with
{\it structural} properties of meaningful gestalts which can only
be proved thanks to the close formula estimates and formal
properties of $\Blkp (l,k,p)$.

As we mentioned before, there are several theories giving
asymptotic estimates of $\Blkp(l, k, p)$ and, luckily enough,
there also are inequalities which give good lower and upper
estimates of $\Blkp(l, k, p)$,  namely the Hoeffding and Slud
inequalities. We shall mainly use the asymptotic estimates to
evaluate how good these non asymptotic inequalities are.

A unified format is requested to compare these inequalities and,
in what follows, we shall compare the estimated values of $$-\frac
1 l \log \Blkp(l, k, p).$$

%$$thebinomiallaw_exo hoeffdinginequalities_exo,
%largedeviations_exo, centrallimitheorem_exo,$$


\subsection{Inequalities for $\Blkp(l, k, p)$}
\begin{pro}  \label{Hoeffdinginequalities} (Hoeffding
inequalities \cite{hoeffding}).
Let  $X_1,\dots, X_l$ be independent random variables such that
$0\leq X_i\leq 1$.  We set $S_l=\sum_{i=1}^lX_i$ and $p =\Expect{\frac
{S_l}l}$. Then for $pl< k< l$,
$$\Prob{S_l\geq k}\leq \left (\frac{p}{k/l}\right)^{l(\frac kl)} \left(\frac{1-p}{1-\frac kl}\right)^{l(1-k/l)}.
$$
In other terms, setting $r=k/l$,
 $$\Prob{S_l\geq  k}\leq   e^{-l(r\log\frac rp + (1-r)\log\frac
{1-r}{1-p})}.$$ In addition, the right-hand term of this
inequality can be bound in the following way:

$$e^{-l[r\log\frac rp + (1-r)\log\frac
{1-r}{1-p}]}\leq e^{-l(r-p)^2h(p)}\leq e^{-2l(r-p)^2},$$ where
$$h(p)=\frac 1{1-2p}\log \frac{1-p}{p} \hspace{0.3cm} {if} \hspace{0.3cm}  0<p<\frac 12 , $$
$${and} \hspace{0.3cm} h(p)=\frac 1{2p(1-p)} \hspace{0.3cm} {if} \hspace{0.3cm} \frac 12\leq p<1.$$
\end{pro}
See Figure \ref{hfunction.fig} for the graph of the function $p\mapsto h(p)$.\\
A more general version of this inequality is proved in  Exercise
\ref{hoeffdinginequalities_exo} at the end of this chapter. In the particular case where the
$X_i$ are Bernoulli variables, this inequality is also known as
Chernoff inequality \cite{chernoff}.



\begin{figure}[h]
\epsfxsize=10cm \centerline{\epsfbox{fig/hfunction.eps}}
\caption{The graph of the function $p\mapsto h(p)$.}
\label{hfunction.fig}
\end{figure}


\begin{theorem}\label{sludtheorem}(Slud's Theorem \cite{slud}).
If $0<p\leq 1/4$ and $pl \leq k
\leq l$, then
$$ \Prob{S_{l} \geq k}  \geq  \frac{1}{\sqrt{2\pi}} \int_{\alpha
(l, k)}^{+\infty} e^{- x^2 /2}  dx  \hspace{1cm} \mathrm{where} \,
\, \,
 \alpha (l, k) = \frac{k - p l}{\sqrt{lp(1-p)}}   .$$
 \end{theorem}
The assumption  $0<p\leq 1/4$ is not a strong condition for us;
it will be true for roughly all applications  we consider.


\subsection{Asymptotic theorems for $\Blkp(l, k, p)=\Prob{S_l\geq k}$}

\begin{pro} (Law of large numbers).
Let $X_i$ be Bernoulli i.i.d. random variables
with parameter $p$ and $S_l=\sum_{i=1}^l X_i$. Then
$$\Prob{\frac {S_l}l\underset{l\to \infty}{\longrightarrow} p}=1.$$
As a consequence, for every $r>p$ and $l\to \infty$ :
$$\Prob{S_l\geq rl}\to 0,\quad\hbox{that is,}\quad
 \Blkp(l, [rl], p)\to 0.$$
 (where $[s]$ denotes the integer part of a real number $s$.)
\end{pro}

\begin{pro} \label{CramerTCL} (Central limit theorem: De Moivre-Laplace,
 Cram\'{e}r \cite{Cramer}  1938).  Let $X_i$ be
Bernoulli i.i.d. random variables with parameter $p$ and let $S_l=\sum_{i=1}^l
X_i$. If
$\alpha(l)^6 /l \rightarrow 0$ as $l\rightarrow +\infty$, then
\begin{equation}\label{feller.prop} \Prob{ S_{l}  \geq  p{l} + \alpha(l) \sqrt{l \cdot
  p(1-p)}  }   \sim   {\frac{1} {\sqrt {2\pi}}}
  \int_{\alpha(l)}^{+\infty} {e^{- {x^2 /2}}  dx}   .
  \end{equation}
  \end{pro}

The original De Moivre-Laplace formula corresponds to the case
where $\alpha$ is a constant, which is allowed by the preceding
proposition.  We prove it in a slightly more general setting in
Problem \ref{centrallimitheorem_exo}. For the general case, see
\cite{feller1}.

 \begin{pro} \label{largedeviationtheoremBernouilli}
  (Cramér  large deviations theorem).
Let $X_i$ be Bernoulli i.i.d.
with parameter $p$ and $S_l=\sum_{i=1}^l X_i$. Let $p<r<1$.
 $$-\frac 1 l \log \Prob{S_l \geq rl}\approx
 r\log\frac rp + (1-r)\log\frac{1-r}{1-p} .$$
\end{pro}

For a proof of this theorem, in a more general setting, see
Problem \ref{largedeviations_exo}.

\subsection{A brief comparison of estimates for $\Blkp(l, k, p)$}

As announced, we shall compare the asymptotic estimates of $-\frac
1 l \log \Blkp(l, k, p)$ given by all of the preceding
propositions, put in a uniform format.

\begin{pro}\label{comparaisondetouteslesestimeesdelaqueuedebinomiale}
Let $X_i$, $i=1,\dots, l$  be independent Bernoulli random variables with
parameter $0<p<\frac 14$ and let $S_l=\sum_{i=1}^l X_i$. Consider a
constant $p<r<1$ or a real function $p<r(l)<1$. Then
$\Prob{S_l\geq k}=\Blkp(l, k, p)$ satisfies
%\begin{align}
%& avant le égal et \tag{Slud}
%\end{align}

\begin{eqnarray}
 \hbox{(Slud)} &-\frac 1 l \log\Prob{S_l\geq rl} \leq  &
\frac{(r-p)^2}{p(1-p)} + O(\frac{\log l}l)\\
\hbox {(Hoeffding-bis)} &-\frac 1 l\log\Prob{S_l\geq rl} \geq  &
(r-p)^2\frac{\log\frac{1-p}p}{1-2p} + O(\frac 1l) \\
\hbox{(Central limit)} &-\frac 1 l\log\Prob{S_l\geq r(l)l} \sim &
\frac{(r(l)-p)^2}{p(1-p)}\;\; \hbox{ if } (r(l)-p)l^\frac 13\underset{l\to\infty}{\longrightarrow} 0 \\
\hbox{(Hoeffding)} &-\frac 1 l\log\Prob{S_l\geq rl} \geq &
r\log\frac rp +(1-p)\log\frac{1-r}{1-p} \\
\hbox{(Large deviation)} &-\frac 1 l\log\Prob{S_l\geq rl} \sim  &
r\log\frac rp+(1-p)\log\frac {1-r}{1-p}\;\; \hbox{ if } r \hbox{ fixed, }
l\to\infty
\end{eqnarray}

\end{pro}

\begin{demo}
The first announced inequality immediately follows from Slud's
Theorem \ref{sludtheorem} and the following inequality
  \begin{equation} \label{estimationdelaqueuedegaussienne}
\frac {x}{1+x^2}e^{-\frac{x^2}2}\leq
\int_x^{+\infty}e^{-\frac {y^2}2} \, dy \,  .
\end{equation}  This inequality is proven in the exercise
\ref{centrallimitheorem_exo} and we have set in Slud's theorem:

$$\alpha(k,l)=\frac{k-pl}{\sqrt{lp(1-p)}}=\frac{(r-p)\sqrt{l}}{\sqrt{p(1-p)}}.$$
The second and fourth inequalities
  immediately derive from the  first and second  forms of  Hoeffding's
inequality (Proposition \ref{Hoeffdinginequalities}) and the third
and last inequalities are an immediate rewriting of
Propositions \ref{CramerTCL} and
\ref{largedeviationtheoremBernouilli}. More precisely, we have set
in Camér's theorem $r(l)l=pl +\alpha(l)\sqrt{lp(1-p)}$.
\end{demo}

  We have put all asymptotic and nonasymptotic estimates in a homogeneous form
  which makes their comparison easier. The Slud and Hoeffding inequalities are
precise non asymptotic ones. In order to extract their main terms,
we had to introduce an asymptotic term $O(\frac 1l)$  or $O(\frac
{\log l}l)$. Now, both terms are easily estimated with sharp
constants which prove them to be negligible when, say, $l$ exceeds
100, independently of $r$ and $p$. So in these inequalities, $r$
and $l$ can vary in any way without any constraint provided $l$ is
realistically large. In the central limit theorem instead, $r(l)$
must be so that $r(l)-p$ tends to zero fast enough, but we can
anyway compare $(Slud)$ and {\it (Central limit)} under this
condition: then we see that the estimates obtained are exactly
the same up to some $O(\frac{\log l}l)$.  As a conclusion, Slud's
theorem cannot be improved.
 The three first estimates given in Proposition
\ref{comparaisondetouteslesestimeesdelaqueuedebinomiale} are of
the same form and  give as main term an $(r-p)^2$ term multiplied
by a $p$ dependent function. So, as we shall see in the next
chapter \ref{align.chap},  they will yield the same orders of
magnitude for the detection thresholds of alignments. Finally, the
most striking fact comes from the classical comparison of {\it
(Hoeffding)} and {\it (Large deviation)}.  Both give exactly the
same estimate of the binomial tail when $r$ is fixed and $l$ tends
to infinity. This yields a strong argument in favor of  the use of
the Hoeffding inequality as a general estimate for the binomial
tail. We shall see in Chapter \ref{modes.chap} that this estimate
has outstanding structure properties.

\section{Bibliographic notes}


Upper bounds for $\Prob{S_l \geq k}$ had been obtained by Bernstein in 1946 \cite{} and Bennett in 1962 \cite{bennett} before Hoeffding \cite{hoeffding} proved Proposition \ref{Hoeffdinginequalities} in 1963.
In the case of Bernouilli i.i.d. random variables (i.e. $S_l$ follows a binomial law), Hoeffding's inequality was implicitely contained in a paper published by Chernoff \cite{chernoff} in 1952. The second part of Hoeffding's inequality (obtained thanks to the fact that $h(p)\geq 2$ for all $p$) had been proven by Okamoto \cite{okamoto} in 1958 in the binomial  case when $p\geq 1/2$ (which is not really the case we are interested in).

In a sense, Hoeffding seemed to close the subject since its upper-bound was in a certain sense optimal. However, in 1995, Talagrand showed in \cite{talagrand} that the exponential term of Hoeffding inequality could be refined by means of a ``missing factor''.

The problem of asymptotic estimates of $\Prob{S_l \geq k}$ as $l$ tends to infinity was addressed by Laplace (for $p$ fixed and $k$ in a range of the form $[lp+\alpha\sqrt{lp(1-p)},lp+\beta\sqrt{lp(1-p)}]$). Prohorov (1961) investigates in \cite{prohorov} this problem for all values of $k$ and $p$, but in a way depending on the relative values of $p$ and $n$. In 1969, Littewood gives in \cite{littlewood} an asymptotic estimate valid for $p$ fixed and $k$ in the range $[p,\frac{3(1-p)}{4p}]$.
A review of these results and more recent and precise estimates, valid for a larger range of values for $k$, can be found in \cite{moisan}, where L. Moisan improves
the asymptotic results of Bahadur \cite{bahadur} for ``very large deviations'' ($k\simeq n$).
%, and where he also obtains a large deviation asymptotic estimate of $\Prob{S_l \geq k}$ (for more details, see \cite{moisan} and the references therein).


\section{Exercices}

\subsection{Hoeffding's inequality for a sum of random variables}
\label{hoeffdinginequalities_exo}

Let $(\Omega, {\cal
F}, \mathbb{P})$ be a probability space. It is recalled that if $X_1$
et $X_2$ are independent variable, and if $f$ and $g$  are two measurable functions from $\real$ to
$\real$  then $f(X_1)$ et $g(X_2)$ also
are independent.  It is also recalled that  if $X_1$, $\dots$,
$X_l$ are independent, then $\E (X_1\dots X_l)= (\E X_1)\dots(\E
X_l)$.
 Let  $X_1,\dots, X_l$ be independent random variables such that
$0\leq X_i\leq 1$. We set $S_l=\sum_{i=1}^l X_i$ and
 $p  =\Expect{\frac{S_l}{l}}$.
We  shall prove that for $0<t<1- p $,
\begin{equation}
\Prob{S_l\geq  (p +t)l}\leq \left (\frac{ p }{ p +t}\right)^{l( p +t)}
\left(\frac{1- p }{1- p -t}\right)^{l(1- p -t)}\leq e^{-lt^2 h( p
)}\leq e^{-2lt^2},
\label{3inequalities.eq}
\end{equation}
where
$$h( p )=\frac 1{1-2 p }\log \frac{1- p
}{ p } \hspace{0.3cm} \mathrm{if} \hspace{0.3cm} 0< p <\frac 12,$$
$$\mathrm{and} \hspace{0.3cm} h( p )=\frac 1{2 p (1- p )},  \hspace{0.3cm} \mathrm{if} \hspace{0.3cm} \frac 12\leq p <1.$$
This kind of  inequality is called a ``large deviation
inequality". In order to understand its meaning in a more
particular setting, let us assume that the $X_i$ are  i.i.d..
Then, when $l$ is large, we know by the law of large numbers that
 $\frac {S_l}l\to  p $ almost surely.  So the Hoeffding inequality
 gives an estimate of a less and less likely event when $l$ tends
 to infinity, namely the event that the mean $\frac {S_l}l$ exceeds
 $p$ by a positive value $t$.


 \quest 1) In order to understand the meaning of the inequality,
 draw the graph of the function
$h( p )$.

\quest 2) Let $X$ be a random variable such that
  $a\leq X\leq b$. Let $\lambda$ be a positive real number. By using the convexity of the exponential
  function   $x\mapsto e^{\lambda x}$, prove that
$$\Expect{e^{\lambda X}}\leq \frac {b-\Expect{X}}{b-a}e^{\lambda a}+\frac{\Expect{X}-a}{b-a}e^{\lambda b}.$$


 \quest 3)   The  main trick of large deviation estimates is to
 use the very simple inequality: $\indic_{x\geq 0}\leq e^{\lambda x}$, true for $\lambda>0$. Prove this inequality. Then apply
it to  $\indic_{\{S_l-\Expect{S_l} -lt\geq 0\}} $ and deduce that
$$\Prob{S_l\geq  (p +t)l} \leq e^{-\lambda(p+t)l}\prod_{i=1}^{l} \Expect{e^{\lambda X_i}}.$$

\quest 4) Set $p_i=\Expect{X_i}$. Applying question 2) with $a=0$ and
$b=1$, deduce that
$$\prod_{i=1}^l\Expect{e^{\lambda X_i}}\leq \prod_{i=1}^l (1-
p_i+ p_i e^\lambda).$$
Important remark: check that this inequality
becomes an identity when the $X_i$'s are Bernoulli random variables.


\quest 5)  Prove the geometric-arithmetic mean inequality: if $a_1$, \ldots, $a_l$ are positive real numbers then
$$\left( \prod_{i=1}^l a_i \right)^{1/l} \leq \frac 1l\sum_{i=1}^l a_i.$$


\quest 6) Deduce that $\prod_{i=1}^l \Expect{e^{ \lambda X_i}} \leq (1- p + p
e^\lambda)^l.$

\quest 7) Combine 3) et 6) and get an inequality. Prove that the
right-hand side of this inequality is minimal for $\lambda=\log
\frac{(1- p )( p +t)}{(1- p -t) p }.$  Check that this number is
positive when  $0<t<1- p  $ and obtain the first Hoeffding
inequality (left inequality in (\ref{3inequalities.eq})) by taking this value for $\lambda$ in the  inequality.

\quest 8) In order to prove  the second inequality of (\ref{3inequalities.eq}), one can remark
that the first proved upper bound has a form
  $e^{-lt^2G(t, p )}$ where $G(t,p)$ is defined by
$$G(t,  p )= \frac{ p  +t}{t^2}\log \frac{ p  +t} p
+\frac{1- p -t}{t^2}\log\frac{1- p -t}{1- p } .$$
Thus, it is
enough to show that $h( p )\leq \inf_{0<t<1- p } G(t,  p ).$  First
check that
$$t^2\frac{\partial }{\partial t}G(t, p )=(1-2\frac{1- p }t)\log (1-\frac{t}{1- p })
-(1-2\frac{ p +t}t)\log(1-\frac t{t+ p })$$
$$=H(\frac t{1- p })-H(\frac t{t+ p }),$$
where $H(x)= (1-\frac 2x)\log (1-x).$ In continuation, show that
$$H(x)=2+(\frac 23-\frac 12)x^2+(\frac 24-\frac 13)x^3+ (\frac 25-\frac 14)x^4+...$$
Deduce that  $H(x)$ is increasing  for $0<x<1$ and that
$\frac{\partial}{\partial t} G(t,  p )>0$ if and only if $\frac
t{1- p }>\frac t{ p +t},$ which means $t> 1-2 p $. Deduce that,
when $1-2 p
>0$, the function $G(t,  p )$ attains its minimum for $t=1-2 p $
and the corresponding minimal value is $h( p )=\frac{1}{1-2 p }\log \frac{1-
p } p .$

\quest 9) Prove that if  $1-2 p \leq 0,$ then $G(t,  p )$ attains
its minimum when $t\to 0$ and that in that case,
$$\lim_{t\to 0} G(t,  p )=\frac 1{2 p (1- p )}=h( p ).$$
 Check that  $h(p )\geq h(\frac 12)=2$ and the proof of the announced Hoeffding
inequalities is complete.

%\quest 10) Deduce the proposition \ref{suffi.prop} from Hoeffding's inequality.

\subsection{A second Hoeffding's inequality}
\label{secondhoeffding_exo}

We now
consider  independent bounded random variables with different
bounds, namely $a_i\leq X_i\leq b_i$. We set $S_l=\sum_{i=1}^l X_i$ and $p=\Expect{\frac{S_l}{l}}$. Then we shall prove that for every $t>0$,
$$\Prob{S_l\geq  (p +t)l} \leq e^{-\frac{2l^2t^2}{\sum_{i=1}^l(b_i-a_i)^2}} .$$


\quest 1) Set $ p _i=\Expect{X_i}$. Prove that for all $\lambda>0$,
$$\Prob{S_l\geq  (p +t)l} \leq e^{-\lambda lt}\prod_{i=1}^l\Expect{e^{\lambda (X_i- p _i)}}.$$

\quest 2) Using question 2) of the  preceding exercise, show  that
$$\Expect{e^{\lambda(X_i- p _i)}} \leq
e^{-\lambda ( p _i-a_i)} \left(\frac{b_i- p _i}{b_i-a_i}+\frac{ p
_i-a_i}{b_i-a_i} e^{\lambda (b_i-a_i)} \right).$$

\quest 3) Set $\lambda_i= \lambda (b_i-a_i)$ and $q_i=\frac{ p
_i-a_i}{b_i-a_i}$. We denote by $L(\lambda_i)$ the  logarithm of the
right-hand side of the preceding inequality. Then
$$L(\lambda_i)=-\lambda_i q_i +\log (1-q_i + q_ie^{\lambda_i}).$$
Prove that   $L''(\lambda_i)\leq \frac 1 4$. Using a Taylor-Mac-Laurin
expansion, deduce that
$$L(\lambda_i)\leq L(0) + \lambda_i L'(0) +\frac 18 \lambda_i^2=\frac 18 \lambda^2(b_i-a_i)^2.$$

\quest 4) Finally prove that $\Prob{S_l\geq  (p +t)l} \leq
e^{-\lambda lt +\frac 18 \lambda ^2\sum_{i=1}^l (b_i-a_i)^2}$. Choose the best
value for $\lambda >0$ so as to deduce the announced inequality.


\subsection{Generating function}

We call generating function of a
random variable $X$ with mean $\mu$ the function   $M : \;
\real\to \real^+$ defined  by  $M(t)=\Expect{e^{tX}}.$ In all that
follows, we assume for all considered random variables that $M(t)$
is bounded on an open interval $I\subset \real$, containing $0$.


\quest 1)  Prove that for all $x$ real, $|x|^k\leq \eps^{-k}k!\, (e^{\eps  x}+ e^{-\eps
x}).$  Deduce that $X$ has moments $\Expect{X^k}$ of any order.

 \quest 2) Use the asymptotic expansion of the
exponential function to prove that $$M(t)=\sum_{k=0}^\infty
\frac{\Expect{X^k}}{k!}t^k$$ on $I$ and that
$$\Expect{X}=M'(0), \; \;\Expect{X^k}=M^{(k)}(0), \;\; M'(t)=\Expect{Xe^{tX}},\; M''(t)=\Expect{X^2e^{tX}}.$$


Hint : Let $\mu_X$ be the law of  $X$.  We can write
$$\E(e^{tX})=\int_{\real} \sum_k \frac{t^kx^k}{k!}d\mu_X(x) =
\int_{\real^+} \sum_k \frac{t^kx^k}{k!}d\mu_X(x) +\int_{\real^-}
\sum_k\frac{t^kx^k}{k!}d\mu_X(x).$$ For the first integral, one
can apply the monotone convergence  theorem since all terms are
nonnegative. For the second integral, just split again the
integral in two terms, one where $x<-C$ and one for which $-C\leq
x\leq 0$. The first term can be made arbitrarily small for $C$
large. In the second terms, sum and integral can be exchanged by
bounded convergence theorem (Lebesgue theorem).



\quest 3) We set $\Lambda(t)=\log M(t).$ Prove  that
$$\Lambda(0)=\log M(0)=0,\quad \Lambda'(0)=\frac{M'(0)}{M(0)}=\mu.$$


\quest 4) Show that  $\Lambda(t)$ is convex on $I$. More
precisely, prove by Cauchy-Schwartz inequality that
$$\Lambda''(t)=\frac{M(t)M''(t)-M'(t)^2}{M(t)^2}\geq 0.$$

\quest 5)  Cauchy-Schwartz' inequality $(\Expect{XY}^2\leq
\Expect{X^2} \Expect{Y^2})$ is an equality if and only if there is $\lambda\in\R$
such that $X=\lambda Y$. Deduce from this  fact that  if $X$ has
non zero variance, then $\Lambda(t)$ is strictly convex on $I$.

\quest 6) The Fenchel-Legendre transform of
$\Lambda$ is defined by
$$\Lambda^*(a)=\sup_{t\in\real} (at -\Lambda(t)),\quad a\in\real.$$
Prove that $\Lambda^*$ is convex.

\subsection{Large deviations estimate}
\label{largedeviations_exo}

We shall now prove the following large deviation estimate.

\begin{theorem} Let $X_1$, $X_2$,... be  i.i.d. random variables
with mean  $\mu$ and such that  $M(t)=\Expect{e^{tX}}$ is finite on an
open interval containing   $0$. We set
 $S_n= X_1+\dots +X_n .$
Let $a>\mu$ be such that $\Prob{X>a}>0$. Then $\Lambda^*(a)>0$ and
$$-\frac 1n \log \Prob{S_n>an}\to \Lambda^*(a)\quad \hbox{ when } n\to \infty.$$
\end{theorem}

Comments : the large number law tells us that $\frac 1nS_n\to \mu$
almost  surely. The central limit theorem asserts that typical
deviations of   $S_n-n\mu$ must  be of order  $c\sqrt n$. Thus,
the probabilities  $\Prob{S_n-n\mu}\geq n^{\alpha})$ with
$\alpha>\frac 12$ must  be  small and the preceding theorem yields
a precise asymptotic estimate of  this smallness when $\alpha=1$.


\quest As a preliminary question,  let us examine the meaning of
this theorem when  $X_i$ are Bernoulli with parameter $p=\mu$. In
that case,  $\Prob{S_n>an}=\Blkp(n, an, p)$  and
$M(t)=\Expect{e^{tX}}=pe^t+(1-p)$. Thus, $\Lambda(t)=\log(pe^t+(1-p))$.
Now,
$$\underset{t>0}{\arg\min} (at-\Lambda(t))=\log\frac qp+\log\frac a{1-a}$$
and finally
$$\Lambda^*(a)=a\log\frac ap + (1-a)\log\frac{1-a}q$$
So the large deviation theorem yields
$$-\frac 1 n \log \Pro(S_n> an) \to a\log\frac ap + (1-a)\log\frac{1-a}{1-p} \quad \mathrm{when} n\to \infty .$$
Thus, for the binomial law, Hoeffding's inequality and the large
deviation behavior yield exactly the same estimate.
 In that particular framework, Hoeffding's inequality is also known as
Bernstein's inequality.
\medskip

\quest{\bf FIRST PART}

\quest 1) Prove that we can take $\mu=0$ without loss  of
generality. \\
Hint: just   assume that the theorem is proved in
that particular case and replace $X$ by $X_i-\mu$.


\quest 2) By changing  $X_i$ into $-X_i$ and by applying the
theorem, give the limit of $\frac 1n \log \Prob{S_n<na}, $ for
$a<\mu$.



\quest 3) Let us prove that  $\Lambda^*(a)>0$. Let
$\sigma^2=\var(X).$ Prove that
$$at-\Lambda(t)=\log\left(\frac{e^{at}}{M(t)}\right)=\log\frac{1+at+o(t)}{1+\frac
12\sigma^2t^2+o(t^2)}$$ for  $t$ small and deduce that
$\Lambda^*(a)>0.$

\quest 4) Use $\Lambda'(0)=\Expect{X}=0$ and get
$$\Lambda^*(a)=\sup_{t>0} (at-\Lambda(t)),\quad a>0.$$

\quest 5) In this question and the following ones, one proceeds as
for Hoefdding's inequality. Remark that
$e^{tS_n}>e^{nat}\indic_{S_n>na}$ and derive
$$\Prob{S_n>na}\leq e^{-n(at-\Lambda(t))}.$$

\quest 6) Deduce that
$$\frac 1n \log \Prob{S_n>na}\leq -\sup_{t>0}(at-\Lambda(t))=-\Lambda^*(a).$$
This upper bound brings us half way in the proof.  Now we need  a
lower bound.

\medskip

\quest{\bf SECOND  PART}

In this part, we make an assumption on
  $\Lambda^*$ which is in practice always satisfied.

\begin{definition} We shall say that we stand in the ``regular case" at $a$
if the maximum value defining    $\Lambda^* (a)$ is attained at a point $t$ in the
interior of $I$, the  definition interval for the generating function $M$. We denote
by $\tau = \tau(a)$ this value of $t$.

\end{definition}
Let  us also define $T=\sup\{t,\; M(t)<\infty.\}.$

\quest 1) Check  that
$$\Lambda^*(a)=a\tau -\Lambda(\tau),\;\;\; \Lambda'(\tau)=a.$$

\quest 2) We set $F(u)=\Prob{X \leq u}$, the distribution function
of  $X$. We shall associate with this function an auxiliary
function defined as follows.  Set $d\tilde F(u)=\frac{e^{\tau
u}}{M(\tau)}dF(u)$, or, in other terms,
$$\tilde F(y)=\frac 1{M(\tau)}\int_{-\infty}^y e^{\tau u}dF(u).$$
 Consider  $\tilde X_1,\; \tilde X_2,\dots $ independent random variables having  all $\tilde F$
  as distribution function  and set $\tilde S_n=\tilde X_1+\dots +\tilde X_n$.

\quest 3)By using  the general formula
$M(t)=\Expect{e^{tX}}=\int_{\real} e^{tu}dF(u)$, prove that
$$\tilde M(t)=\frac{M(t+\tau)}{M(\tau)}.$$

\quest 4)  Deduce  that
$$\Expect{\tilde X_i}=\tilde M'(0)=a,$$
$$\var(\tilde X_i)=\Expect{\tilde X_i^2}-\Expect{\tilde X_i}^2=\tilde M''(0)-\tilde
M'(0)^2=\Lambda''(\tau).$$

\quest 5) Prove that the generating  function of  $\tilde S_n$ is
$$\left(\frac{M(t+\tau)}{M(\tau)}\right)^n=\frac
1{M(\tau)^n}\int_{\real}e^{(t+\tau)u}dF_n(u),$$ where $F_n$ is the
distribution function  of $S_n$. Deduce that  the distribution
function   $\tilde F_n$ of  $\tilde S_n$ satisfies
$$d\tilde F_n(u)=\frac{e^{\tau u}}{M(\tau)^n}dF_n(u).
$$

\quest 6) Let  $b>a$. Deduce from the preceding question that

$$\Prob{S_n>na}\geq e^{-n(\tau b-\Lambda(\tau))} \Prob{na<\tilde S_n<nb}.$$

\quest 7) By using the fact that the mean of  $\tilde X_i$ is $a$,
the law of  large numbers and  the central limit theorem, prove
that $\Prob{na<\tilde S_n<nb}\to \frac 12$. Deduce from this  fact
and from the preceding question that
$$\lim\inf_{n\to \infty}\frac 1n \log\Prob{S_n>na}\geq -(\tau b-\Lambda(\tau))\to
-\Lambda^*(a)  \;\; \hbox{ when } b\to a.$$

\medskip

\quest {\bf THIRD  PART}


\quest 1) We take the same assumptions as in the preceding part,
but we are now in the non regular case. In order to get back to
the regular case, we fix   $c>a$ and we set $X^c=\inf (X, c)$.
Denote by $M^c(t) $ the associated generating function and set
  $\Lambda^c(t)=\log
M^c(t)$.

\quest 2) Prove that    $M^c(t)<\infty$ for every $t>0$, and that
$\Expect{X^c}\to 0 $ when $c\to \infty$ and $\Expect{X^c}\leq 0$.


\quest 3) Show that there exists $b\in (a, c)$ such that
$\Prob{X>b}>0$ and deduce that
$$at-\Lambda^c(t)\leq at-\log(e^{tb}\Prob{X>b})\to -\infty\hbox{ when } t\to\infty.$$

\quest 4) Conclude that the sequence   $X_i^c$ stands in the
``regular case", in other terms that the  supremum of
 $(at-\Lambda^c(t))$ for  $t>0$ is  attained  at a value $\tau^c\in
(0, \infty)$, and finally that
$$\frac 1n \log\Prob{\sum_{i=1}^nX_i^c>na}\to -(\Lambda^{c})^*(a)  \hbox{ when } t\to
\infty.$$ (We set
$\Lambda^{c^*} =\sup_{t>0}(at-\Lambda^c(t))=a\tau^c-\Lambda^c(\tau^c)$).

\quest 5)  Prove  that   $\Lambda^{c*}(a)\downarrow
\Lambda^{\infty *} \hbox{ when } c\to + \infty.$ and $0\leq
\Lambda^{\infty*}<\infty.$

\quest 6) Prove that    $$\frac 1n\log \Prob{S_n>na}\geq \frac
1n\log \Prob{\sum_{i=1}^nX_i^c>a}.
$$

\quest 7) Explain  why it  is enough, in order to conclude the
proof of the theorem  in the irregular case, to prove that
$\Lambda^{\infty*}\leq \Lambda^*(a).$

\quest 8) In order to show this last relation, proceed as follows
: prove that the set
   $I_c=\{t\geq 0,\;\; at-\Lambda^c(t)\geq \Lambda^{\infty *}\}$ is not empty. Prove that
    $I_c$ is a compact interval. Prove that the intervals
$I_c$ decrease (by inclusion) as  $c$ grows and deduce that there
is  some $\zeta\in \cap_{c>a}I_c$. Finally show that
$\Lambda^c(\zeta)\to \Lambda(\zeta)$ when $c\to \infty$ and that
$a\zeta-\Lambda(\zeta)=\lim_{c\to
\infty}(a\zeta-\Lambda^c(\zeta))\geq \Lambda^{\infty * }$.
Conclude the  proof.

\subsection{Problem: the central limit Theorem}
\label{centrallimitheorem_exo}

\subsubsection{Some basics on the characteristic function of a random variable
  and on the Gauss function}

 Let $X$ be a random variable with values in    ${\R}^d$. Let, for $t\in \R^d$,
$$\phi_{X}(t)=\Expect{e^{it.X}}=
\int_{\real^d}e^{it.x}d\mu_X(dx)=\int_{\real^d}e^{it.x}f_X(x)dx$$
be its characteristic function where it is assumed that the random
variable $X$ has a density $f_X(t)$ with respect to the Lebesgue
measure, and   $t.x=<t,x> =\sum_{i=1}^d t_ix_i $ denotes the
scalar product of   $t$ and  $x$. \\
Briefly prove the following properties
  (we write $\varphi$ for  $\varphi_X$) :
  \begin{enumerate}
  \item $\varphi(0)=1$
  \item $\forall t, $ $|\varphi(t)|\leq 1$
  \item $t\to \varphi(t)$ is continuous  (use Lebesgue dominated convergence theorem)
  \item $\varphi_{(-X)}(t)=\overline{\varphi_X(t)}$
  \item $\varphi_{aX+b}(t)=e^{ib.t}\varphi_X(at),$ \hspace{0.4cm} ($a\in \real, \; b\in \real^d$)
  \item  If  $X$ and $Y$ are independent, $\varphi_{X+Y}=\varphi_X \varphi_Y$.
\end{enumerate}
Prove the following properties of gaussian distributions:
\begin{enumerate}
\item If $X$ is  gaussian and has density
  $\frac 1{\sigma\sqrt{2\pi}}e^{-\frac{(x-\mu)^2}{2\sigma^2}}$,
  then
  $\phi_X(t)=e^{i\mu t-\frac 12 \sigma^2t^2}$. \\
  Hint : prove this result first when $\mu=0$ and $\sigma=1$.  Set
  $\varphi(t)=\frac 1{\sqrt{2\pi}}\int e^{-itx}e^{-\frac{x^2}2}dx$
  and prove that
  $\varphi'(t)=t\varphi(t)$, $\varphi(0)=1$. It will follow that  $\varphi(t)=e^{-\frac
  {t^2}2}.$

  \item The variance de $X$
  is $\sigma^2$ and its mean is $\mu$.
  \item If $X_1$ and $X_2$ are gaussian independent, then  $X_1+X_2$
  also is
   gaussian : compute  the mean and variance of  $X_1+X_2$ as a function of those $(\mu_i,\;\sigma_i^2)$,
  $i=1,\; 2$  of $X_1$ and $X_2$.
  \end{enumerate}


\subsubsection{Asymptotic expansion  of the characteristic function}

Let  $X$ be a random variable with values in ${\mathbb R}^d$ and
admitting  an order $2$ moment (i.e.
$\Expect{X^2}=\int_{\real^d}x^2d\mu_X(x)<\infty$).

\quest 1)Prove that for every real number  $x$,
$$\exp(ix)=1+ix-x^{2}\int_{0}^{1}(1-u)\exp(iux)du$$

\quest 2)  Deduce that
$$\left|\exp(ix)-\left(1+ix-x^{2}/2\right)\right|\leq x^{2}$$

\quest 3) By applying the same method as in both preceding
questions, prove that
$$\left|\exp(ix)-\left(1+ix-x^{2}/2\right)\right|\leq |x|^{3}/6$$

\quest 4) Deduce that
$$\left|\exp(ix)-(1+ix-x^{2}/2)\right|\leq \inf(x^{2},|x|^{3}/6),$$
and
$$\left|\phi_{X}(t)-\left(1+it\Expect{X}-\cfrac{t^2}
{2} \Expect{X^{2}}\right)\right|\leq
t^{2}\Expect{\inf(X^{2},\;|t||X|^{3}/6)}.$$ By applying to
the right hand term the Lebesgue theorem, deduce an  asymptotic
expansion of order 2  of   $\varphi_X(t)$ at $t=0$.




\subsubsection{Central limit theorem}

We shall prove the following theorem (Central limit theorem in $\R^d$):

\begin{theorem}
Let $(X_{n})_{n\geq 1}$ be a sequence of random  variables defined
on the same probability space   $(\Omega, {\cal F},\Probf)$, with
values in   ${\mathbb R}^{d}$. We assume that they are independent, identically
distributed and having  an order two moment $\Expect{\parallel X_i \parallel^2}<+\infty$.
Then the sequence $Y_{n}$ defined by
$$Y_{n}=\cfrac{1}{\sqrt{n}}\sum_{j=1}^{n}(X_{j}-\Expect{X_{j}})$$
converges in law towards a $d$-dimensional gaussian distribution with zero mean and whose
covariance matrix is the same as the one of the $X_i$'s.
\end{theorem}

We recall that a
sequence of random variables is  said to converge in law towards a
random variable $X$ if for every continuous and bounded function
$g$ on $\real^d$ one has
$$\int_{\real^d} g(x)d\mu_{X_n}(x)\to \int_{\real^d}g(x)d\mu_X(x).$$
We shall, however, use a convergence in law criterion, Lévy's
theorem,  whose statement is given in question 5).


\quest 1) Prove that the characteristic function of $Y_n$ is given
by :

\begin{equation*}
\phi_{Y_n}(t)=\left[\phi_{<X_1-\Expect{X_1},t>}\left(\cfrac{1}{\sqrt{n}}\right)\right]^n
\end{equation*}

\quest 2) Deduce, by using the preceding exercise on the
asymptotic expansion of the characteristic  function, that
\begin{equation*}
\phi_{Y_n}(t)=\left[1-\cfrac{1}{2n}\Expect{<X_1-\Expect{X_1},t>^2}+o\left(\cfrac{1}{n}\right)\right]^n
\end{equation*}


\quest 3) Prove that for every $z \in \mathbb{C}$,
$$\lim_{n\rightarrow +\infty}\left(1+\cfrac{z}{n}\right)^n=\exp(z),$$
the  convergence being uniform on every bounded set. (Use  the
complex logarithm and  an asymptotic expansion of order 1).

\quest Hint, or rather solution of  3):  one can use the
principal determination of the  logarithm, denoted by  $log (z)$. It
satisfies $e^{log (z)}=z$ if $|z-1|<1$  and its asymptotic
expansion yields $log (1+z)= z-\frac 12 z^2+\frac 13 z^3+\dots$.
Thus, for  $|z|\leq A$ and for $n$ large enough ($n>A$),
$$|log(1+\frac zn)^n-z|=|-\frac{z^2}{2n}+\frac{z^3}{3n^2}-\frac {z^4}{4n^3}+\dots|\leq
\frac {A^2}n(\frac 12+\frac A{3n}+\frac{A^2}{4n^2}+\dots)\to 0$$
when $n\to\infty$. Thus $log(1+\frac zn)^n\to z$ uniformly for
 $|z|<A$ when $n\to\infty$. From this inequality also follows that
  $|log(1+\frac zn)^n|\leq A+1$ for $n$ large enough. The
  exponential function being uniformly continuous on the set $\{ |z|\leq A+1\}$, the result follows.

\quest 4) Deduce  that
$$\lim_{n \rightarrow  + \infty} \phi_{Y_n}(t)=\exp\left[-\cfrac{1}{2}<Ct,t>\right] ,$$
where $C$ is the covariance matrix of $X_1$.

\quest 5) Conclude by applying   Lévy's theorem: if  $X_n$ are
real random variables  such that $\phi_{X_n}\to\phi$ and if $\phi$
is a continuous function at 0, then there exists a random variable
$X$ such that   $\phi_X=\phi$ and the sequence  $X_n$ converges in
law  to $X$.



\subsection{The tail of the gaussian law}
\label{equivalentqueuedeloigaussienne}


In this exercice, we set  $\phi(y)=(2\pi)^{-1/2}\exp(-y^{2} /2)$ and $\Phi
(x)=\int_{-\infty}^{x}\phi(y)dy$. We consider a random variable
$X$ with density law $\varphi$.\\

\quest 1) Remark that $\phi^{'}(y)=-y\phi(y)$ and deduce that
for every  $x>0$,
$$ x^{-1}\phi(x)\geq(1-\Phi(x)) .$$

\quest 2) Remark that $(y^{-1}\phi (y))^{'}=-(1+y^{-2})\phi(y)$
and show that for every $x>0$,
$$\phi(x)\leq (x+x^{-1})(1-\Phi(x)) .$$

\quest 3) Deduce upper and lower bounds for $\Pro (X>x)$ for $x>0$.

%Solution :  En intégrant entre $x$ et $+\infty$ la relation
%différentielle, on obtient $-\phi(x)=\int_x^{+\infty}y\phi(y)\leq
%-x\int_x^{+\infty} \phi(y)=-x(1-\Phi).$ Donc
%$(1-\Phi)=\int_x^{+\infty}\phi(y)dy\leq \frac{\phi(x)}{x}.$
%\newline b) En intégrant la relation proposée, on a
%$-x^{-1}\phi(x)=\int_x^{+\infty}(1+y^{-2})\phi(y)\geq
%-(1+x^{-2})(1-\Phi).$  En combinant a) et b), on obtient
%$$\frac {x^{-1}}{1+x^{-2}}e^{-\frac{x^2}2}\leq
%\int_x^{+\infty}e^{-\frac {y^2}2}=\sqrt{2\pi}\Pro(X>x)\leq
%x^{-1}e^{-\frac{x^2}2}.$$
