---
abstract: 'We propose new concentration inequalities for self-normalized martingales. The main idea is to introduce a suitable weighted sum of the predictable quadratic variation and the total quadratic variation of the martingale. It offers much more flexibility and allows us to improve previous concentration inequalities. Statistical applications on autoregressive process, internal diffusion-limited aggregation process, and online statistical learning are also provided.'
address:
- ' Université de Bordeaux, Institut de Mathématiques de Bordeaux, UMR 5251, 351 cours de la libération, 33405 Talence cedex, France.'
- 'Sorbonne Université, Laboratoire de Probabilités Statistique et Modélisation, UMR 8001, Campus Pierre et Marie Curie, 4 Place Jussieu, 75005 Paris cedex, France'
author:
- Bernard Bercu
- Taieb Touati
title: 'New insights on concentration inequalities for self-normalized martingales'
---

Introduction
============

Let $(M_n)$ be a locally square integrable real martingale adapted to a filtration ${\mathbb{F}}=({\mathcal{F}}_n)$ with $M_0=0$. The predictable quadratic variation and the total quadratic variation of $(M_n)$ are respectively given by $${<\!\!M\!\!>}_n=\sum_{k=1}^n{\mathbb{E}}[\Delta M_k^{2}|\mathcal{F}_{k-1}]
\hspace{1cm}\mbox{and}\hspace{1cm}
[M]_n=\sum_{k=1}^n\Delta M_k^{2}$$ where $\Delta M_n=M_n -M_{n-1}$ with ${<\!\!M\!\!>}_0=0$ and $[M]_0=0$. Since the pionner work of Azuma and Hoeffding @Azuma1967, @Hoeffding1963, a wide literature is available on concentration inequalities for martingales. We refer the reader to the recent books @BDR2015, @BLM2013, @DLPKlassLai2007 where the celebrated Azuma-Hoeffding, Freedman, Bernstein, and De la Pe<span>ñ</span>a inequalities are provided. Over the last two decades, there has been a renewed interest in this area of probability. To be more precise, extensive studies have been made in order to establish concentration inequalities for $(M_n)$ without boundedness assumptions on its increments @BercuTouati2008, @Delyon2009, @DVZ2001, @FGL2015, @Pinelis2014, @Rio2013b. For example, it was established in @BercuTouati2008 that for any positive $x$ and $y$, $$\label{BT2008}
{\mathbb{P}}(|M_n | {\geqslant}x,[M]_n\,+{<\!\!M\!\!>}_n {\leqslant}y){\leqslant}2 \exp\Bigl(-\frac{x^2}{2y}\Bigr).$$ We shall improve inequality by showing that a special case of our inequalities leads, for any positive $x$ and $y$, to $$\label{NCIMART8}
{\mathbb{P}}(|M_n | {\geqslant}x,[M]_n\,+{<\!\!M\!\!>}_n {\leqslant}y){\leqslant}2 \exp\Bigl(-\frac{8x^2}{9y}\Bigr).$$ Moreover, it was proven by Delyon @Delyon2009 that for any positive $x$ and $y$, $$\label{D2009}
{\mathbb{P}}(|M_n | {\geqslant}x,[M]_n+ 2{<\!\!M\!\!>}_n {\leqslant}y){\leqslant}2 \exp\Bigl(-\frac{3x^2}{2y}\Bigr).$$ We will show that inequality is a special case of a more general result involving a suitable weighted sum of $[M]_n$ and ${<\!\!M\!\!>}_n$. Furthermore, it was shown by De la Pe<span>ñ</span>a and Pang @DLPPang2009 that for any positive $x$, $$\label{DLPP2009}
{\mathbb{P}}\Bigl(\frac{|M_n|}{\sqrt{[M]_n+ {<\!\!M\!\!>}_n+{\mathbb{E}}[M_n^2]}}{\geqslant}x\sqrt{\frac{3}{2}}\Bigr){\leqslant}\Bigl(\frac{2}{3} \Bigr)^{1/3} x^{-2/3} \exp\Bigl(-\frac{x^2}{2}\Bigr).$$ We shall improve inequality by using of the tailor-made normalization $$\label{DEFSNA}
S_n(a)= [M]_n+ c(a)\!{<\!\!M\!\!>}_n,$$ where for any $a > 1/8$, $$\label{DEFCA}
c(a) = \frac{2(1 - 2a +2\sqrt{a(a+1)})}{8a-1}.$$ The novelty of our approach is that $S_n(a)$ is a suitable weighted sum ${<\!\!M\!\!>}_n$ and $[M]_n$. In the special case where ${<\!\!M\!\!>}_n=[M]_n$, $S_n(a)$ reduces to $S_n(a)=(1+c(a)){<\!\!M\!\!>}_n$ and the best choice of $a$ is clearly the one that minimizes $aS_n(a)=a(1+c(a)){<\!\!M\!\!>}_n$, that is $a=1/3$. However, for small values of $n$, the behavior of ${<\!\!M\!\!>}_n$ may be totally different from that of $[M]_n$. Consequently, our approach provides interesting concentration inequalities in many situations where ${<\!\!M\!\!>}_n\neq [M]_n$. The paper is organised as follows. Section \[S-MR\] is devoted to our new concentration inequalities for self-normalized martingales which improve some previous results of Bercu and Touati @BercuTouati2008, Delyon @Delyon2009 and De la Pe<span>ñ</span>a and Pang @DLPPang2009. Section \[S-SA\] deals with statistical applications on autoregressive process, internal diffusion-limited aggregation process, and online statistical learning. All technical proofs are postponed to the Appendices.  

\

Main results {#S-MR}
============

Our first result holds without any additional assumption on $(M_n)$.

\[T-CIWA\] Let $(M_n)$ be a locally square integrable real martingale. Then, as soon as $a>1/8$, we have for any positive $x$ and $y$, $$\label{CIWA1}
{\mathbb{P}}(|M_n | {\geqslant}x,  S_n(a){\leqslant}y){\leqslant}2 \exp\Bigl(-\frac{x^2}{2ay}\Bigr),$$ where $S_n(a)= [M]_n+ c(a)\!{<\!\!M\!\!>}_n$ and $c(a)$ is given by .

The function $c$ is positive, strictly convex and $c(a)\sim 1/2a$ as $a$ tends to infinity. Special values are given in Table 1.

    a     $9/55$   $4/21$   $9/40$   $25/96$   $1/3$   $9/16$   $49/72$   $4/5$
  ------ -------- -------- -------- --------- ------- -------- --------- -------
   c(a)    $10$     $6$      $4$       $3$      $2$     $1$      $4/5$    $2/3$

\

Table 1. Special values of the function $c(a)$

On the one hand, $c(a)=1$ if and only if $a=9/16$. Replacing the value $a=9/16$ into immediately leads to as $S_n(a)= [M]_n+ \!{<\!\!M\!\!>}_n$. On the other hand, $c(a)=2$ if and only if $a=1/3$. Hence, in this special case, $S_n(a)= [M]_n+ 2{<\!\!M\!\!>}_n$ and we find again by taking the value $a=1/3$ into .

Some recent results of Johansen and Nielsen @Jo-Nielsen2016b, @Jo-Nielsen2016a on outlier detection algorithms and robust statistical methods for linear regressions are based on the tail probability for the maximum of a family of martingales. This tail probability follows from inequality . It should be interesting to improve the results in @Jo-Nielsen2016b, @Jo-Nielsen2016a by use of our new inequality , see also @BN2018.

Our second result for self-normalized martingales is as follows.

\[T-CISNWA\] Let $(M_n)$ be a locally square integrable real martingale. Then, as soon as $a>1/8$, we have for any positive $x$ and $y$, $$\label{CISNWA1}
{\mathbb{P}}\left(\frac{|M_n|}{S_n(a)}{\geqslant}x, S_n(a){\geqslant}y\right) {\leqslant}2\exp\Bigl(-\frac{x^2y}{2a}\Bigr)$$ where $S_n(a)= [M]_n+ c(a)\!{<\!\!M\!\!>}_n$ and $c(a)$ is given by . Moreover, we also have for any positive $x$, $$\label{CISNWA2}
{\mathbb{P}}\Bigl(\frac{|M_n|}{S_n(a)} {\geqslant}x \Bigr) {\leqslant}2 \inf_{p>1}\left({\mathbb{E}}\Bigl[\exp\Bigl(-\frac{(p-1)x^2S_n(a)}{2a}\Bigr)\Bigr]\right)^{1/p}\!\!\!\!\!.$$

In the special case $a=9/16$, we find from and that for any positive $x$ and $y$, $${\mathbb{P}}\left(\frac{|M_n|}{[M]_n+ {<\!\!M\!\!>}_n}{\geqslant}x, [M]_n+ {<\!\!M\!\!>}_n{\geqslant}y\right) {\leqslant}2\exp\Bigl(\!-\frac{8x^2y}{9}\Bigr),$$ $${\mathbb{P}}\Bigl(\frac{|M_n|}{[M]_n+ {<\!\!M\!\!>}_n}{\geqslant}x \Bigr)
{\leqslant}2 \inf_{p>1}\left({\mathbb{E}}\Bigl[\exp\Bigl(-\frac{8(p-1)x^2}{9}\Bigl( [M]_n+ {<\!\!M\!\!>}_n\Bigr) \Bigr)\Bigr]\right)^{1/p}\!\!\!\!.$$ Similar concentration inequalities for self-normalized martingales can be obtained for $a=1/3$ as well as for other values of $a>1/8$. In addition, via the same lines as in the proof of Theorem \[T-CISNWA\], it is easy to see that for any positive $x$ and $y$, $$\label{CISNWA3}
{\mathbb{P}}\left(\frac{|M_n|}{{<\!\!M\!\!>}_n}{\geqslant}x, c(a)\!{<\!\!M\!\!>}_n{\geqslant}[M]_n+y\right) {\leqslant}2\exp\Bigl(\!-\frac{x^2y}{2ac^2(a)}\Bigr),$$ $$\label{CISNWA4}
{\mathbb{P}}\Bigl(\frac{|M_n|}{{<\!\!M\!\!>}_n}{\geqslant}x, [M]_n {\leqslant}c(a) y\!{<\!\!M\!\!>}_n \Bigr)\!
\!{\leqslant}\! 2 \inf_{p>1}\!\left(\!{\mathbb{E}}\Bigl[\exp\Bigl(-\frac{(p-1)x^2\!{<\!\!M\!\!>}_n}{2ac(a)(1+y)}\Bigr)\Bigr]\!\right)^{1/p}\!\!\!\!\!\!\!.$$

Our third result deals with missing factors in exponential inequalities for self-normalized martingales with upper bounds independent of $[M]_n$ or ${<\!\!M\!\!>}_n$.

\[T-CISNMISS\] Let $(M_n)$ be a locally square integrable real martingale. Assume that ${\mathbb{E}}[|M_n|^p] \!<\! \infty$ for some $p {\geqslant}2$. Then, as soon as $a\!>\!1/8$, we have for any positive $x$, $$\label{CISNMISS1}
{\mathbb{P}}\Bigl(\frac{|M_n|}{\sqrt{aS_n(a)+({\mathbb{E}}[|M_n|^p])^{2/p}}}{\geqslant}\frac{x}{\sqrt{B_q}}\Bigr){\leqslant}C_q x^{-B_q} \exp\Bigl(-\frac{x^2}{2}\Bigr)$$ where $q=p/(p-1)$ is the Hölder conjugate exponent of $p$, $$B_q= \frac{q}{2q-1}
\hspace{1cm}\text{and}\hspace{1cm}
C_q=\Bigl(  \frac{q}{2q-1} \Bigr)^{B_q/2}.$$ In particular, for $p=2$, we have for any positive $x$, $$\label{CISNMISS2}
{\mathbb{P}}\Bigl(\frac{|M_n|}{\sqrt{aS_n(a)+{\mathbb{E}}[M_n^2]}}{\geqslant}x\sqrt{\frac{3}{2}}\Bigr){\leqslant}\Bigl(\frac{2}{3} \Bigr)^{1/3} x^{-2/3} \exp\Bigl(-\frac{x^2}{2}\Bigr).$$

In the special case $a=9/16$, we saw that $S_n(a)=[M]_n+ {<\!\!M\!\!>}_n$. Hence, we deduce from that for any positive $x$, $${\mathbb{P}}\Bigl(\frac{|M_n|}{\sqrt{a([M]_n+ {<\!\!M\!\!>}_n)+{\mathbb{E}}[M_n^2]}}{\geqslant}x\sqrt{\frac{3}{2}}\Bigr){\leqslant}\Bigl(\frac{2}{3} \Bigr)^{1/3} x^{-2/3} \exp\Bigl(-\frac{x^2}{2}\Bigr).$$ Since $a<1$, this inequality clearly leads to $${\mathbb{P}}\Bigl(\frac{|M_n|}{\sqrt{[M]_n+ {<\!\!M\!\!>}_n+{\mathbb{E}}[M_n^2]}}{\geqslant}x\sqrt{\frac{3}{2}}\Bigr){\leqslant}\Bigl(\frac{2}{3} \Bigr)^{1/3} x^{-2/3} \exp\Bigl(-\frac{x^2}{2}\Bigr).$$ Consequently, in the special case $a=9/16$, provides a tighter upper bound than inequality (3.2) in @DLPPang2009. Moreover, in the special case $a=1/3$, we also saw that $S_n(a)= [M]_n+ 2{<\!\!M\!\!>}_n$. Hence, we obtain from that for any positive $x$, $${\mathbb{P}}\Bigl(\frac{|M_n|}{\sqrt{[M]_n+2{<\!\!M\!\!>}_n+3{\mathbb{E}}[M_n^2]}}{\geqslant}\frac{x}{\sqrt{2}}\Bigr){\leqslant}\Bigl(\frac{2}{3} \Bigr)^{1/3} x^{-2/3} \exp\Bigl(-\frac{x^2}{2}\Bigr)$$ which is exactly inequality (3.64) in @BDR2015.

The proofs are given in Appendices A and B.

Statistical applications {#S-SA}
========================

Autoregressive process
----------------------

Consider the first-order autoregressive process given, for all $n{\geqslant}1$, by $$\label{AR}
X_{n}=\theta X_{n-1} + \varepsilon_{n}$$ where $X_n$ and $\varepsilon_n$ are the observation and the driven noise of the process, respectively. Assume that $(\varepsilon_n)$ is a sequence of independent and identically distributed random variables sharing the same ${\mathcal{N}}(0,\sigma^2)$ distribution where $\sigma^2>0$. The process is said to be stable if $| \theta|< 1$, unstable if $| \theta|= 1$, and explosive if $| \theta|> 1$. We estimate the unknown parameter $\theta$ by the standard least-squares estimator given, for all $n{\geqslant}1$, by $$\label{LSAR}
\widehat{\theta}_n=\frac{\sum_{k=1}^nX_{k-1}X_k}{\sum_{k=1}^nX_{k-1}^2}.$$ It is well-known that whatever the value of $\theta$ is, $\widehat{\theta}_n$ converges almost surely to $\theta$. Moreover, White @White1958 has shown that in the stable case $| \theta|< 1$, $$\sqrt{n} \bigl( \widehat{\theta}_n - \theta \bigr) \liml {\mathcal{N}}(0, 1-\theta^2),$$ while in the explosive case $| \theta|> 1$ with initial value $X_0=0$, $$|\theta|^n  \bigl( \widehat{\theta}_n - \theta \bigr) \liml (\theta^2 -1) {\mathcal{C}}$$ where ${\mathcal{C}}$ stands for the Cauchy distribution. Furthermore, in the stable case $| \theta|< 1$, it was proven in @BercuGamboaRouault1997 that the sequence $(\widehat{\theta}_n )$ satisfies a large deviation principle with a convex-concave rate function, see also @Bercu2001. A fairly simple concentration inequality for the estimator $\widehat{\theta}_n$ was established in @BercuTouati2008, whatever the value of $\theta$ is. More precisely, assume that $X_0$ is independent of $(\varepsilon_n)$ with ${\mathcal{N}}(0,\tau^2)$ distribution where $\tau^2 {\geqslant}\sigma^2$. Then, for all $n{\geqslant}1$ and for any positive $x$, we have $$\label{APPLARLS}
{\mathbb{P}}(|\widehat{\theta}_n-\theta| {\geqslant}x)
{\leqslant}2\exp\Bigl(-\frac{nx^2}{2(1+y_x)}\Bigr)$$ where $y_x$ is the unique positive solution of the equation $h(y_x)=x^2$ and $h$ is the function given, for any positive $x$, by $h(x)=(1+x)\log(1+x) -x$. It follows from that, as soon as $0<x<1/2$, $${\mathbb{P}}\bigl(|\widehat{\theta}_n-\theta| {\geqslant}x\bigr)
{\leqslant}2\exp\Bigl(-\frac{nx^2}{2(1+2x)}\Bigr).$$ The situation in which $(\varepsilon_n)$ is not normally distributed, is much more difficult to handle. If $(\varepsilon_n)$ is a sequence of independent and identically distributed random variables, uniformly bounded with symmetric distribution, we can use De la Pe$\tilde{\mbox{n}}$a's inequality @DLP1999 for self-normalized conditionally symmetric martingales, to prove concentration inequalities for the least-squares estimator, see @BDR2015. Our motivation is to establish concentration inequalities for $\widehat{\theta}_n$ in the situation where the distribution of $(\varepsilon_n)$ is non-symmetric.

\[C-AR\] Assume that $(\varepsilon_n)$ is a sequence of independent and identically distributed random variables such that, for all $n {\geqslant}1$, $$\varepsilon_n= 
 \left \{ \begin{array}{ccc}
   \,\, 2q & \text{with probability} & p,  \vspace{1ex} \\
   \!\! -2p & \text{with probability} & q,
   \end{array} \nonumber \right.$$ where $p\in ]0,1/2]$ and $q=1-p$. Moreover, assume that $X_0$ is independent of $(\varepsilon_n)$ with $|X_0| {\geqslant}2p$. Then, for any $a>1/8$ and for any $x$ in the interval $[0, \sqrt{ad(a)}]$, we have $$\label{INEGLS}
{\mathbb{P}}\bigl(|\widehat{\theta}_n-\theta| {\geqslant}x\bigr)
{\leqslant}2\exp\Bigl(-\frac{np^2x^2}{a d(a)}\Bigr),$$ where $$\label{DEFDA}
d(a)=\frac{4\bigl(q^2+pq c(a)\bigr)^2}{\bigl(p^2+pq c(a)\bigr)}.$$

In the symmetric case $p=1/2$, ${<\!\!M\!\!>}_n=[M]_n$, $S_n(a)=(1+c(a)){<\!\!M\!\!>}_n$ and $d(a)$ reduces to $d(a)=1+c(a)$. Hence, if $a=1/3$, $c(a)=2$ and $d(a)=3$. Consequently, we deduce from that for any $x$ in $[0, 1]$, $${\mathbb{P}}\bigl(|\widehat{\theta}_n-\theta| {\geqslant}x\bigr)
{\leqslant}2\exp\Bigl(-\frac{nx^2}{4}\Bigr).$$ Moreover, in the nonsymmetric case $p\neq 1/2$, we have almost surely $$\frac{p}{q}{<\!\!M\!\!>}_n \leqslant [M]_n \leqslant \frac{q}{p} {<\!\!M\!\!>}_n.$$ For example, if $p=1/3$ and $a=9/16$, $c(a)=1$ and $d(a)=16/3$ which implies that $ad(a)=3$ Therefore, we obtain from that for any $x$ in $[0,\sqrt{3}]$, $${\mathbb{P}}\bigl(|\widehat{\theta}_n-\theta| {\geqslant}x\bigr)
{\leqslant}2\exp\Bigl(-\frac{nx^2}{27}\Bigr).$$

It immediately follows from together with that for all $n {\geqslant}1$, $$\label{LSMART}
\widehat{\theta}_n-\theta=\sigma^2\frac{M_n}{{<\!\!M\!\!>}_n}$$ where $\sigma^2=4pq$ and $(M_n)$ is the locally square integrable real martingale given by $$M_n=\sum_{k=1}^nX_{k-1}\varepsilon_k,
\hspace{1cm}
{<\!\!M\!\!>}_n=\sigma^2\sum_{k=1}^nX_{k-1}^2,
\hspace{1cm}
[M]_n= \sum_{k=1}^nX_{k-1}^2\varepsilon_k^2.$$ We clearly have $d_{min}(a){<\!\!M\!\!>}_n {\leqslant}S_n(a) {\leqslant}d_{max}(a) {<\!\!M\!\!>}_n$ where $$d_{min}(a)= \frac{p}{q} +c(a)
\hspace{1cm}
\mbox{and}
\hspace{1cm}
d_{max}(a)= \frac{q}{p} +c(a).$$ Hereafter, we obtain from that for any $a>1/8$ and for any $x>0$, $$\label{CIAR1}
{\mathbb{P}}\bigl( |M_n|  {\geqslant}x S_n(a) \bigr) {\leqslant}2 \left({\mathbb{E}}\Bigl[\exp\Bigl(-\frac{x^2S_n(a)}{2a}\Bigr)\Bigr]\right)^{1/2}$$ which implies via that for any $x>0$, $$\label{CIAR2}
{\mathbb{P}}\bigl( |\widehat{\theta}_n-\theta | {\geqslant}x  \bigr) {\leqslant}2 \left({\mathbb{E}}\Bigl[\exp\Bigl(-\frac{x^2  {<\!\!M\!\!>}_n}{2a  \sigma^2 d(a)}\Bigr)\Bigr]\right)^{1/2}$$ where $d(a)$ is given by . It only remains to find a suitable upper-bound for the Laplace transform of ${<\!\!M\!\!>}_n$. We have from that $X_n^2=\theta^2 X_{n-1}^2 + 2 \theta X_{n-1} \varepsilon_n + \varepsilon_n^2$. Hence, if ${\mathcal{F}}_n=\sigma(X_0, \ldots, X_n)$, we obtain that for any real $t$ and for all $n {\geqslant}1$, $$\label{CIAR3}
{\mathbb{E}}[\exp(tX_n^2)|{\mathcal{F}}_{n-1}]
=\exp(t \theta^2 X_{n-1}^2)\Lambda_{n-1}(t)$$ where $$\label{CIAR4}
\Lambda_{n-1}(t)= p \exp\bigl(4tq^2+4\theta t q X_{n-1}\bigr)+q \exp\bigl(4tp^2-4\theta t p X_{n-1}\bigr).$$ It follows from Kearns-Saul's inequality @BDR2015, @KS1998 that for any real $s$, $$\label{CIAR5}
p\exp(qs)+ q\exp(-ps) {\leqslant}\exp\Bigl(\frac{\varphi(p)s^2}{4}\Bigr),$$ where the function $\varphi$ is defined by $\varphi (p) = (q-p)/ \log(q/p)$. One can observe that $\varphi (p) \in [0, 1/2]$. Then, we deduce from and with $s=4 \theta t X_{n-1}$ that for any $t{\leqslant}0$, $
\Lambda_{n-1}(t) {\leqslant}\exp\bigl(4tp^2 + 4\varphi(p)t^2\theta^2 X_{n-1}^2 \bigr)
$ leading to $$\label{CIAR6}
{\mathbb{E}}[\exp(tX_n^2)|{\mathcal{F}}_{n-1}] {\leqslant}\exp\bigl(4tp^2 +  t \theta^2 X_{n-1}^2(1+4\varphi(p)t) \bigr).$$ As soon as $t \in[-1/2,0]$, we get from that ${\mathbb{E}}[\exp(tX_n^2)|{\mathcal{F}}_{n-1}] {\leqslant}\exp(4tp^2)$. Consequently, for any $t\in [-1/2\sigma^2,0]$ and for all $n {\geqslant}1$, $${\mathbb{E}}[\exp(t{<\!\!M\!\!>}_n)] {\leqslant}{\mathbb{E}}[\exp(t{<\!\!M\!\!>}_{n-1})] \exp(4tp^2 \sigma^2)$$ which ensures that $$\label{CIAR8}
{\mathbb{E}}[\exp(t{<\!\!M\!\!>}_n)] {\leqslant}\exp(4n tp^2\sigma^2)$$ as $|X_0| {\geqslant}2p$. Therefore, it follows from and that for any $x \in [0, \sqrt{ad(a)}]$, $${\mathbb{P}}\bigl(|\widehat{\theta}_n-\theta| {\geqslant}x\bigr)
{\leqslant}2\exp\Bigl(-\frac{np^2x^2}{a d(a)}\Bigr)$$ which achieves the proof of Corollary \[C-AR\].

Internal diffusion-limited aggregation process
----------------------------------------------

Our second application deals with the internal diffusion-limited aggregation process. This aggregation process, first introduced in Mathematics by Diaconis and Fulton @DiaconisFulton1991, is a cluster growth model in ${\mathbb{Z}}^d$ where explorers, starting from the origin at time $0$, are travelling as a simple random walk on ${\mathbb{Z}}^d$ until they reach an uninhabited site that is added to the cluster. In the special case $d=1$, the cluster is an interval $A(n)=[L_n,R_n]$ which, properly normalized, converges almost surely to $[-1,1]$. In dimension $d {\geqslant}2$, Lawler, Bramson and Griffeath @LBG1992 have shown that the limit shape of the cluster is a sphere, see some refinements in @Lawler1995. We shall restrict our attention on the one-dimensional internal diffusion-limited aggregation process. Consider the simple random walk on the integer number line ${\mathbb{Z}}$ starting from the origin at time $0$. At each step, the explorer moves to the right $+1$ or to the left $-1$ with equal probability $1/2$. Let $(A(n))$ be the sequence of random subsets of ${\mathbb{Z}}$, recursively defined as follows: $A(0)=\{0\}$ and, for all $n{\geqslant}0$, $$A(n+1) = \left \{ \begin{array}{l}
    A(n)\cup \{L_{n}-1\} \vspace{0.5ex} \\
    A(n)\cup \{R_{n}+1\}
   \end{array} \nonumber \right.$$ if the explorer leaves $A(n)$ by the left side or by the right side, respectively, where $L_n$ and $R_n$ stand for be the minimum and the maximum of $A(n)$. To be more precise, $$A(n)=\{L_n,L_n + 1,\ldots,R_n-1, R_n\}.$$ The random set $A(n)$ is characterized by $X_n=L_n+R_n$ as $R_n-L_n=n$, $$L_n=\frac{X_n-n}{2} \hspace{1cm}\text{and}\hspace{1cm} R_n=\frac{X_n+n}{2}.$$ One can observe that $L_n$ and $R_n$ correspond to the number of negative and positive sites of $A(n)$, respectively. It was proven in @DiaconisFulton1991 that $$\lim_{n\rightarrow \infty} \frac{X_n}{n}=0 \hspace{1cm}\text{a.s.}$$ and $$\frac{X_n}{\sqrt{n}} \liml {\mathcal{N}}\Bigl(0,\frac{1}{3} \Bigr),$$ which are respectively equivalent to the almost sure convergences $$\lim_{n\rightarrow \infty} \frac{L_n}{n}=-\frac{1}{2} \hspace{1cm}\text{and} \hspace{1cm}
\lim_{n\rightarrow \infty} \frac{R_n}{n}=\frac{1}{2}$$ and the asymptotic normalities $$\frac{1}{\sqrt{n}}\Bigl(L_n + \frac{n}{2} \Bigr) \liml {\mathcal{N}}\Bigl(0,\frac{1}{12} \Bigr)
\hspace{1cm}\text{and} \hspace{1cm}
\frac{1}{\sqrt{n}}\Bigl(R_n - \frac{n}{2} \Bigr) \liml {\mathcal{N}}\Bigl(0,\frac{1}{12} \Bigr).$$ It is possible to prove from Azuma-Hoeffding's inequality @BDR2015 that for any positive $x$, $$\label{IDLAAH}
{\mathbb{P}}\Bigl( \frac{|X_n|}{n} {\geqslant}x \Bigr) {\leqslant}2 \exp\Bigl(-\frac{3}{8} n x^2\Bigr).$$ Our goal is to improve this inequality with a suitable use of Theorems \[T-CIWA\] and \[T-CISNMISS\].

\[C-IDLA\] For any $a$ in the interval $]1/8,9/16]$ and for any positive $x$, we have $$\label{INEGIDLA1}
{\mathbb{P}}\Bigl( \frac{|X_n|}{n} {\geqslant}x \Bigr) {\leqslant}2 \exp\Bigl(-\frac{nx^2}{2ac_n(a)} \Bigr)$$ and $$\label{INEGIDLA2}
{\mathbb{P}}\Bigl(\frac{|X_n|}{\sqrt{n}}{\geqslant}x\Bigr){\leqslant}(d_n(a))^{1/3} x^{-2/3} \exp\Bigl(-\frac{x^2}{3d_n(a)}\Bigr)$$ where $$\label{DEFCNA}
c_n(a)=\Bigl(\frac{2n+1}{n+1}\Bigr)\Bigl(\frac{3+c(a)}{6}\Bigr)+\Bigl(\frac{n(1+c(a)) + 2c(a)}{(n+1)^2}\Bigr)$$ and $$\label{DEFDNA}
d_n(a)=c_n(a)+\Bigl(\frac{n+2}{3n}\Bigr).$$

The calculation of $c_n(a)$ and $d_n(a)$ looks rather complicated. However, it is absolutely not the case. As a matter of fact, if $a=1/3$, $c(a)=2$ and it immediately follows from that $$c_n(a)= \frac{10n^2+33n+29}{6(n+1)^2}.$$ It is not hard to see that for all $n {\geqslant}1$, $c_n(a) {\leqslant}3$ and $d_n(a) {\leqslant}4$. Consequently, we can deduce from that for any positive $x$, $${\mathbb{P}}\Bigl( \frac{|X_n|}{n} {\geqslant}x \Bigr) {\leqslant}2 \exp\Bigl(-\frac{nx^2}{2} \Bigr)$$ which clearly outperforms inequality . In addition, implies that for any positive $x$, $${\mathbb{P}}\Bigl(\frac{|X_n|}{\sqrt{n}}{\geqslant}x\Bigr){\leqslant}\Bigl(\frac{2}{x} \Bigr)^{2/3} \exp\Bigl(-\frac{x^2}{12}\Bigr).$$ Moreover, if $a=25/96$, $c(a)=3$ and we obtain from that $$c_n(a)= \frac{2n^2+5n+7}{(n+1)^2}.$$ Hence, for all $n {\geqslant}1$, $c_n(a) {\leqslant}7/2$ and $d_n(a) {\leqslant}9/2$. Therefore, we find from that for any positive $x$, $${\mathbb{P}}\Bigl( \frac{|X_n|}{n} {\geqslant}x \Bigr) {\leqslant}2 \exp\Bigl(-\frac{96 nx^2}{175} \Bigr)$$ which improves the above inequality for $a=1/3$. Finally, we also deduce from that for any positive $x$, $${\mathbb{P}}\Bigl(\frac{|X_n|}{\sqrt{n}}{\geqslant}x\Bigr){\leqslant}\Bigl(\frac{3}{\sqrt{2}x} \Bigr)^{2/3} \exp\Bigl(-\frac{2x^2}{27}\Bigr).$$

It follows from a stopping time argument for gambler's ruin @DiaconisFulton1991, @Freedman1965 that for all $n {\geqslant}1$, $$\begin{aligned}
\label{GR}
{\mathbb{P}}(X_{n}=X_{n-1}-1|X_{n-1}) &=& \frac{(n+1+X_{n-1})}{2(n+1)},  \notag \\
{\mathbb{P}}(X_{n}=X_{n-1}+1|X_{n-1}) &=&\frac{(n+1-X_{n-1})}{2(n+1)}.\end{aligned}$$ We obtain from that for all $n {\geqslant}1$, $X_n=X_{n-1} + \xi_n$ where the distribution of the increment $\xi_n$ given ${\mathcal{F}}_{n-1}$ is a Rademacher ${\mathcal{R}}(p_n)$ distribution with $$p_n=\frac{(n+1-X_{n-1})}{2(n+1)}.$$ Hence, we clearly have $$\label{CMEAN1X}
{\mathbb{E}}[X_n | {\mathcal{F}}_{n-1} ]= X_{n-1} + {\mathbb{E}}[\xi_n | {\mathcal{F}}_{n-1} ] = \Bigl(\frac{n}{n+1}\Bigr) X_{n-1}$$ and $$\label{CMEAN2X}
{\mathbb{E}}[X_n^2 | {\mathcal{F}}_{n-1} ]= X_{n-1}^2 + 2 X_{n-1}{\mathbb{E}}[\xi_n | {\mathcal{F}}_{n-1} ] +1= 1+\Bigl(\frac{n-1}{n+1}\Bigr) X_{n-1}^2.$$ Let $(M_n)$ be the sequence defined by $M_n=(n+1)X_n$. We immediately deduce from and that $(M_n)$ is a locally square integrable real martingale such that $${<\!\!M\!\!>}_n=\sum_{k=1}^n (k+1)^2- \sum_{k=1}^n X_{k-1}^2.$$ Moreover, for all $n {\geqslant}1$, $|X_n| {\leqslant}n$. Hence, $$[M]_n = \sum_{k=1}^n((k+1)X_k -kX_{k-1})^2= \sum_{k=1}^n( k\xi_k +X_{k})^2 {\leqslant}3 \sum_{k=1}^n k^2 + \sum_{k=1}^n X_{k}^2.$$ One can observe that we always have ${<\!\!M\!\!>}_n\neq [M]_n$. In addition, $$\label{INEGSNA1}
S_n(a)  {\leqslant}(3+c(a)) \sum_{k=1}^n k^2 +(1-c(a)) \sum_{k=1}^{n-1} X_{k}^2 +X_n^2 +c(a)n(n+2).$$ We already saw that for any $a \in ]1/8,9/16]$, $c(a) {\geqslant}1$. Therefore, we obtain from that for any $a \in ]1/8,9/16]$, $$\label{MAJSNA}
S_n(a)  {\leqslant}(3+c(a)) \sum_{k=1}^n k^2 + n(n+c(a)(n+2)) {\leqslant}n(n+1)^2 c_n(a)$$ where $c_n(a)$ is given by . Hence, it follows from with $y\!=\! n(n+1)^2 c_n(a)$ that for any $a \!\in ]1/8,9/16]$ and for any positive $x$, $$\begin{aligned}
{\mathbb{P}}\Bigl( \frac{|X_n|}{n} {\geqslant}x \Bigr) &=& {\mathbb{P}}\bigl( |M_n|{\geqslant}x n(n+1)\bigr), \\
&=& {\mathbb{P}}\bigl( |M_n|{\geqslant}x n(n+1), S_n(a) {\leqslant}y \bigr), \\
& {\leqslant}& 2 \exp\Bigl(-\frac{nx^2}{2ac_n(a)} \Bigr),\end{aligned}$$ which is exactly what we wanted to prove. Furthermore, we can deduce from identity that for all $n {\geqslant}1$, $${\mathbb{E}}[X_n^2]= 1+\Bigl(\frac{n-1}{n+1}\Bigr) {\mathbb{E}}[X_{n-1}^2]$$ where the initial value ${\mathbb{E}}[X_1^2]=1$. It implies that for all $n {\geqslant}1$, $$\label{MEANX}
{\mathbb{E}}[X_n^2]= \frac{(n+2)}{3}.$$ Consequently, we immediately obtain from that for all $n {\geqslant}1$, $$\label{MEANM}
{\mathbb{E}}[M_n^2] =\frac{(n+1)^2(n+2)}{3}.$$ Finally, we find from together with , and that for any $a \in ]1/8,9/16]$ and for any positive $x$, $${\mathbb{P}}\Bigl(\frac{|X_n|}{\sqrt{n d_n(a)}}{\geqslant}x\sqrt{\frac{3}{2}}\Bigr){\leqslant}\Bigl(\frac{2}{3} \Bigr)^{1/3} x^{-2/3} \exp\Bigl(-\frac{x^2}{2}\Bigr)$$ which clearly leads to , completing the proof of Corollary \[C-IDLA\].

Online statistical learning
---------------------------

Our third application is devoted to the study of the statistical risk of hypothesis during an online learning process using concentration inequalities for martingales. We refer the reader to the survey of Cesa-Bianchi and Lugosi @CBLugosi2006 for a rather exhaustive description of the the underlying theory concerning online learning, as well as to the recent book of Hazan @Hazan2016 for online convex optimization. Our approach is based on the contributions of Cesa-Bianchi <span>*et al.*</span> @CBCG2004, @CBG2008 dealing with the statistical risk of hypothesis in the situation where the ensemble of hypothesis is produced by training a learning algorithm incrementally on a data set of independent and identically distributed random variables. Their bounds rely on Freedman concentration inequality for martingales @Freedman1975. Consider the task of predicting a sequence in an online manner with inputs and outputs taking values in some abstract measurable spaces ${\mathcal{X}}$ and ${\mathcal{Y}}$, respectively. We call hypothesis $H$, the classifier or regressor generated by a learning algorithm after training. The predictive performance of hypothesis $H$ is evaluated by the theoritical risk denoted $R(H)$, which is the expected loss on a realisation $(X,Y) \in {\mathcal{X}}\times {\mathcal{Y}}$ drawn from the underlying distribution $$\label{TRisk}
R(H)={\mathbb{E}}[\ell(H(X),Y)]$$ where $\ell$ is a nonnegative and bounded loss function. For the sake of simplicity, we assume that $\ell$ is bounded by $1$. Denote by ${\mathcal{S}}_n=\{(X_1,Y_1),\ldots,(X_n,Y_n)\}$ a training data set of independent random variables sharing the same unknown distribution as $(X,Y)$. Our goal is to predict $Y_{n+1} \in {\mathcal{Y}}$ given $X_{n+1} \in {\mathcal{X}}$, on the basis of ${\mathcal{S}}_n$. Let ${\mathcal{H}}_n=\{H_0,H_1,\ldots,H_{n-1} \}$ be a finite ensemble of hypothesis generated by an online learning algorithm where the initial hypothesis $H_0$ is arbitrarily chosen.The empirical risk associated with the ensemble of hypothesis ${\mathcal{H}}_n$ and the training data set ${\mathcal{S}}_n$ is given by $$\label{ERisk}
\widehat{R}_n=\frac{1}{n}\sum_{k=1}^{n}\ell(H_{k-1}(X_k),Y_k).$$ Denote by $R_n$ the average risk associated with the ensemble of hypothesis ${\mathcal{H}}_n$, $$\label{AriskH}
R_n=\frac{1}{n}\sum_{k=1}^{n} R(H_{k-1}).$$ Our bound on the average risk $R_n$ is as follows.

\[C-OSL\] Let ${\mathcal{H}}_{n}=\{H_0,H_1,...,H_{n-1}\}$ be a finite ensemble of hypothesis generated by a learning algorithm. Then, for any $a$ in the interval $]1/8,9/16]$ and for any positive $x$, we have $$\label{OSLR1}
{\mathbb{P}}( R_n {\geqslant}\widehat{R}_n +x ) {\leqslant}\exp\Bigl(-\frac{nx^2}{2a(1+c(a)V_n)}\Bigr),$$ where $$\label{VER}
V_n=\frac{1}{n}\sum_{k=1}^{n}{\mathbb{E}}[\ell^2(H_{k-1}(X),Y)].$$ In other words, for any $0< \delta \leqslant 1$, $$\label{OSLR2}
{\mathbb{P}}\Bigl( R_n {\geqslant}\widehat{R}_n + \sqrt{\frac{d_n(a)}{n}}\Bigr) {\leqslant}\delta,$$ where $
d_n(a)=-2a(1+c(a)V_n)\log (\delta).
$ Moreover, denote $m(a)=\max(4(1+c(a)),c^2(a))/2$. Then, for any $0< \delta \leqslant 1$ and for all $n {\geqslant}-am(a) \log (\delta)$, we also have $$\label{OSLR3}
{\mathbb{P}}\Bigl( R_n {\geqslant}\widehat{R}_n -ac(a) \frac{\log(\delta)}{n}+ \frac{1}{2} \sqrt{\Delta_n(a)} \Bigr)
{\leqslant}\delta$$ where $\Delta_n(a)=B_n(a)\bigl(4+4c(a)\widehat{R}_n +c^2(a)B_n(a)\bigr)$ with $B_n(a)= -2a\log (\delta)/n$.

On the one hand, improves the deviation inequality given in Proposition 1 of Cesa-Bianchi, Conconi and Gentile @CBCG2004, $${\mathbb{P}}\Bigl( R_n {\geqslant}\widehat{R}_n + \sqrt{\frac{-2\log(\delta)}{n}}\Bigr) {\leqslant}\delta,$$ as $V_n$ is always smaller than $1$. On the other hand, is drastically more accurate than the deviation inequality given in Proposition 2 of Cesa-Bianchi and Gentile @CBG2008, $$\label{CBG}
{\mathbb{P}}\Bigl( R_n {\geqslant}\widehat{R}_n + \frac{36}{n}\log\Bigl( \frac{n  \widehat{R}_n +3}{\delta}\Bigr)
+ 2\sqrt{\frac{\widehat{R}_n}{n}\log\Bigl( \frac{n  \widehat{R}_n +3}{\delta}\Bigr)}\Bigr) {\leqslant}\delta.$$ Indeed, one can observe that the right-hand sides of and are increasing functions of $\widehat{R}_n$. The smallest value in for $\widehat{R}_n=0$ is given by $36\log(3/\delta)/n$. Consequently, inequality is only effective for $n {\geqslant}36\log(3/\delta)$, which implies that $n$ must always be greater than $40$. For example, if $\delta=1/5$, it is necessary to assume that $n {\geqslant}36\log(15)$, that is $n{\geqslant}98$. If $a=1/3$, then $c(a)=2$ and $m(a)=6$. Consequently, inequality is interesting as soon as $n {\geqslant}-2 \log(\delta)$. For example, if $\delta=1/5$, it is necessary to assume that $n{\geqslant}4$. For instance, if $\delta=1/5$, $n=100$ and $a=1/3$, the smallest values in and are respectively given by $0.220$ and $0.975$. Finally, for all values of $\delta$, $n$ and $a$, one can easily check that is always sharper than .

Let $(M_n)$ be the locally square integrable real martingale given by $$\label{MartRisk}
M_n=\sum_{k=1}^{n}\bigl(R(H_{k-1})-\ell(H_{k-1}(X_{k}),Y_{k})\bigr),$$ where we recall that $R(H)={\mathbb{E}}[\ell(H(X),Y)]$. We clearly have $${<\!\!M\!\!>}_n = \sum_{k=1}^{n}\bigl({\mathbb{E}}[\ell^2(H_{k-1}(X),Y))]-R^2(H_{k-1})\bigr),$$ $$[M]_{n} = \sum_{k=1}^{n}\bigl( R(H_{k-1})-\ell(H_{k-1}(X_{k}),Y_{k})\bigr)^2.$$ Consequently, for any $a \in ]1/8,9/16]$, $$S_n(a) {\leqslant}(1-c(a)) \sum_{k=1}^{n}R^2(H_{k-1}) 
+ \sum_{k=1}^n  \ell^2(H_{k-1}(X_{k}),Y_{k}) + c(a)  \sum_{k=1}^n {\mathbb{E}}[\ell^2(H_{k-1}(X),Y)]$$ Hence, as $c(a) {\geqslant}1$ and the loss function $\ell$ is bounded by $1$, we obtain from that $S_n(a) {\leqslant}n(1+c(a)V_n)$. Therefore, it follows from with $y\!=\! n(1+c(a)V_n)$ that for any $a \in ]1/8,9/16]$ and for any positive $x$, $$\label{CRisk1}
{\mathbb{P}}(M_n {\geqslant}x) {\leqslant}\exp\Bigl(-\frac{x^2}{2na(1+c(a)V_n)}\Bigr)$$ which immediately leads to $$\label{CRisk2}
{\mathbb{P}}\Bigl(\frac{M_n}{n} {\geqslant}x\Bigr) {\leqslant}\exp\Bigl(-\frac{n x^2}{2a(1+c(a)V_n)}\Bigr).$$ However, we clearly have from that $$\frac{1}{n}M_n = R_n - \widehat{R}_n.$$ Hence, immediately implies and . It only remains to prove . Since the loss function $\ell$ is bounded by $1$, we obtain from that $V_n {\leqslant}R_n$. Consequently, if $B_n(a)= -2a\log (\delta)/n$, ensures that for any $0< \delta \leqslant 1$, $$\label{CRisk3}
{\mathbb{P}}\Bigl( R_n {\geqslant}\widehat{R}_n + \sqrt{B_n(a)(1+c(a)R_n)}\Bigr) {\leqslant}\delta.$$ Therefore, we deduce from that for any $0< \delta \leqslant 1$, $$\label{CRisk4}
{\mathbb{P}}\bigl( \Phi_a(R_n)  {\geqslant}\widehat{R}_n  \bigr) {\leqslant}\delta$$ where the function $\Phi_a$ is defined, for all $x$ in $[0,1]$, by $\Phi_a(x)=x-\sqrt{B_n(a)(1+c(a)x)}$. It is not hard to see that, as soon as $n {\geqslant}-am(a) \log (\delta)$ with $m(a)=\max(4(1+c(a)),c^2(a))/2$, $\Phi_a$ is a strictly convex and increasing function on $[0,1]$. Then, $\Phi_a$ is invertible and it follows from straightforward calculations that $$\Phi_a^{-1}(x)=x  + \frac{1}{2} c(a) B_n(a)+ \frac{1}{2} \sqrt{B_n(a)\bigl(4+4c(a)x +c^2(a)B_n(a)\bigr)}.$$ Finally, we immediately obtain from that $$\label{CRisk5}
{\mathbb{P}}\bigl( \Phi_a(R_n)  {\geqslant}\widehat{R}_n  \bigr)={\mathbb{P}}\bigl( R_n  {\geqslant}\Phi_a^{-1}(\widehat{R}_n)  \bigr) {\leqslant}\delta$$ which is exactly inequality , completing the proof of Corollary \[C-OSL\].

Appendix A\
Two keystone lemmas {#appendix-a-two-keystone-lemmas .unnumbered}
===================

Our first lemma deals with a sharp upper bound on the Hermite generating function associated with a centered random variable $X$.

\[L-HERMITE\] Let $X$ be a square integrable random variable with mean zero and variance $\sigma^2$. For all $t\in {\mathbb{R}}$, denote $$\label{DEFL}
L(t)={\mathbb{E}}\Bigl[\exp\Bigl(tX-\frac{at^2}{2}X^2\Bigr)\Bigr]$$ with $a>1/8$. Then, for all $t\in {\mathbb{R}}$, $$\label{MAJLD}
L(t){\leqslant}1+\frac{b(a)t^2}{2}\sigma^2,$$ where $$\label{DEFBA}
b(a) = \frac{2a(1 - 2a +2\sqrt{a(a+1)})}{8a-1}.$$

The proof of Lemma \[L-HERMITE\] relies on the following Hermite inequality, see also Proposition 12 in @Delyon2009 for the special value $a=1/3$. For all $x\in {\mathbb{R}}$, we have $$\label{HERMITE}
\exp\Bigl(x-\frac{ax^2}{2}\Bigr){\leqslant}1 + x + \frac{b(a)x^2}{2}.$$ As a matter of fact, let $$\label{VARPHI}
\varphi_a(x)= \log \Bigl( 1 + x + \frac{bx^2}{2} \Bigr) - x + \frac{ax^2}{2},$$ where $b=b(a)$. It is of course necessary to assume that $b>1/2$ which ensures that $1+x+bx^2/2$ is positive whatever the value of $x$ is. We clearly have $$\label{DVARPHI}
\varphi_a^{\prime}(x) = \Bigl( 1 + x + \frac{bx^2}{2} \Bigr)^{-1}xP_{a,b}(x),$$ where the second degree polynomial $P_{a,b}$ is given by $$P_{a,b}(x)=   \frac{abx^2}{2} +  \frac{(2a-b)x}{2} + a+b-1.$$ Hereafter, we assume that $a>1/8$ and $b\neq 1-a$. The only positive root of the discriminant of $P_{a,b}$ is given by $b=b(a)$. As soon as $b{\geqslant}b(a)$, we have for all $x \in {\mathbb{R}}$, $P_{a,b}(x) {\geqslant}0$. Consequently, we deduce from that the function $\varphi_a$ reaches its minimum for $x=0$. Since $\varphi_a^{\prime}(0)=0$ and $\varphi_a(0)=0$, we find that for all $x \in {\mathbb{R}}$, $\varphi_a(x) {\geqslant}0$ which immediately leads to . Therefore, we obtain from that for all $t \in {\mathbb{R}}$, $$L(t)={\mathbb{E}}\Bigl[\exp\Bigl(tX-\frac{at^2}{2}X^2\Bigr)\Bigr] {\leqslant}{\mathbb{E}}\Bigl[ 1 + tX + \frac{b(a)t^2X^2}{2} \Bigr]
= 1 + \frac{b(a) t^2}{2}\sigma^2$$ which is exactly what we wanted to prove.

Our second exponential supermartingale lemma is as follows.

\[L-SUPERMG\] Let $(M_n)$ be a locally square integrable real martingale. For all $t\in {\mathbb{R}}$ and $n {\geqslant}0$, denote $$\label{DEFVN}
V_n(t)=\exp\Bigl(tM_n-\frac{at^2}{2}[M]_n - \frac{b(a)t^2}{2} \!{<\!\!M\!\!>}_n\Bigr)$$ with $a>1/8$. Then, $(V_n(t))$ is a positive supermartingale such that ${\mathbb{E}}[V_n(t)] {\leqslant}1$.

For all $t \in {\mathbb{R}}$ and for all $n{\geqslant}1$, we clearly have $$V_n(t)=V_{n-1}(t)\exp\Bigl(t\Delta M_n - \frac{at^2}{2}\Delta [M]_n - \frac{b(a)t^2}{2} \Delta \!{<\!\!M\!\!>}_n\Bigr),$$ where $\Delta M_n=M_n-M_{n-1}$, $\Delta [M]_n=\Delta M_n^2$ and $\Delta \!{<\!\!M\!\!>}_n={\mathbb{E}}[\Delta M_n^2|{\mathcal{F}}_{n-1}]$. Hence, we deduce from Lemma \[L-HERMITE\] that for all $t\in {\mathbb{R}}$, $$\begin{aligned}
{\mathbb{E}}[V_n(t)|{\mathcal{F}}_{n-1}] &{\leqslant}& V_{n-1}(t)\exp\Bigl( - \frac{b(a)t^2}{2}\Delta \!{<\!\!M\!\!>}_n\Bigr)\Bigl(1+\frac{b(a)t^2}{2}\Delta \! {<\!\!M\!\!>}_n\Bigr),\\
&{\leqslant}&  V_{n-1}(t)\end{aligned}$$ via the elementary inequality $1+x {\leqslant}\exp(x)$. Consequently, for all $t\in {\mathbb{R}}$, $(V_n(t))$ is a positive supermartingale satisfying for all $n{\geqslant}1$, ${\mathbb{E}}[V_n(t)]{\leqslant}{\mathbb{E}}[V_{n-1}(t)]$, which implies that ${\mathbb{E}}[V_n(t)]{\leqslant}{\mathbb{E}}[V_0(t)]=1$.

Appendix B\
Proofs of the main results {#appendix-b-proofs-of-the-main-results .unnumbered}
==========================

<span>**Proof of Theorem \[T-CIWA\].**</span> For any positive $x$ and $y$, let $$A_n=\Bigl\{|M_n|{\geqslant}x, aS_n(a) {\leqslant}y\Bigr\}$$ with $aS_n(a)= a[M]_n + b(a) \!{<\!\!M\!\!>}_n$. We have the decomposition $A_n=A_n^+\cup A_n^-$ where $$A_n^+ =\Bigl\{M_n{\geqslant}x, aS_n(a) {\leqslant}y\Bigr\} \hspace{1cm} \text{and} \hspace{1cm}
A_n^-=\Bigl\{M_n{\leqslant}\!-x, aS_n(a) {\leqslant}y\Bigr\}.$$ It follows from Markov's inequality together with Lemma \[L-SUPERMG\] that for all positive $t$, $$\begin{aligned}
{\mathbb{P}}(A_n^+)&{\leqslant}&{\mathbb{E}}\Bigl[\exp\Bigl(tM_n - tx\Bigr){\mathrm{I}}_{A_n^+}\Bigr],\\
&{\leqslant}&{\mathbb{E}}\Bigl[\exp\Bigl(tM_n - \frac{t^2}{2}aS_n(a)\Bigr)\exp\Bigl(\frac{t^2}{2}aS_n(a)- tx \Bigr){\mathrm{I}}_{A_n^+}\Bigr],\\
&{\leqslant}&\exp\Bigl(\frac{t^2y}{2}- tx\Bigr) {\mathbb{E}}[V_n(t)], \\
&{\leqslant}& \exp\Bigl(\frac{t^2y}{2}- tx\Bigr).\end{aligned}$$ Hence, by taking the optimal value $t=x/y$ in the above inequality, we find that $${\mathbb{P}}(A_n^+){\leqslant}\exp\Bigl(-\frac{x^2}{2y}\Bigr).$$ We also obtain the same upper bound for ${\mathbb{P}}(A_n^-)$ which ensures that $$\label{UBPAN}
{\mathbb{P}}(A_n){\leqslant}2 \exp\Bigl(-\frac{x^2}{2y}\Bigr).$$ Finally, inequality clearly leads to replacing $y$ by $ay$. $\videbox$  

\
<span>**Proof of Theorem \[T-CISNWA\].**</span> For any positive $x$ and $y$, let $$B_n=\Bigl\{|M_n| {\geqslant}x S_n(a), S_n(a) {\geqslant}y \Bigr\}=B_n^+\cup B_n^-,$$ where $$B_n^+ = \Bigl\{ M_n{\geqslant}xS_n(a), S_n(a) {\geqslant}y \Bigr \}
\hspace{0.5cm} \text{and} \hspace{0.5cm}
B_n^- = \Bigl\{ M_n {\leqslant}\!- xS_n(a), S_n(a) {\geqslant}y \Bigr \}.$$ We have for all positive $t$, $$\begin{aligned}
\label{UBPBN1}
{\mathbb{P}}(B_n^+) &{\leqslant}& {\mathbb{E}}\Bigl[\exp\Bigl(\frac{t}{2}M_n - \frac{tx}{2}S_n(a) \Bigr){\mathrm{I}}_{B_n^+}\Bigr], \nonumber \\
&{\leqslant}&{\mathbb{E}}\Bigl[\exp\Bigl(\frac{t}{2}M_n - \frac{t^2}{4}aS_n(a)\Bigr)
\!\exp\Bigl(\frac{t}{4}(ta- 2x)S_n(a)\Bigr){\mathrm{I}}_{B_n^+}\!\Bigr]\!.\end{aligned}$$ Consequently, we find from with the particular choice $t=x/a$ that $${\mathbb{P}}(B_n^+) {\leqslant}\exp\Bigl(-\frac{x^2y}{4a}\Bigr) {\mathbb{E}}[ \sqrt{V_n(t)} {\mathrm{I}}_{B_n^+}].$$ Hence, we deduce from Cauchy-Schwarz's inequality together with Lemma \[L-SUPERMG\] that $${\mathbb{P}}(B_n^+) {\leqslant}\exp\Bigl(-\frac{x^2y}{4a}\Bigr) \sqrt{{\mathbb{P}}(B_n^+)}$$ which leads to $$\label{UBPBN2}
{\mathbb{P}}(B_n^+){\leqslant}\exp\Bigl(-\frac{x^2y}{2a}\Bigr).$$ By the same token, we obtain the same upper bound holds for ${\mathbb{P}}(B_n^-)$ which clearly implies . Furthermore, for any positive $x$, let $$C_n=\Bigl\{|M_n|{\geqslant}x S_n(a) \Bigr\}=C_n^+\cup C_n^-,$$ where $$C_n^+ = \Bigl \{M_n{\geqslant}x S_n(a) \Bigr\}
\hspace{0.5cm} \text{and} \hspace{0.5cm}
C_n^- = \Bigl \{M_n{\leqslant}\!-x S_n(a)  \Bigr\}.$$ By Holder's inequality, we have for all positive $t$ and $q>1$, $$\begin{aligned}
\label{MGINEGDC1}
{\mathbb{P}}(C_n^+)&{\leqslant}&{\mathbb{E}}\Bigl[\exp\Bigl(\frac{t}{q}M_n - \frac{tx}{q}S_n(a)\Bigr){\mathrm{I}}_{C_n^+}\Bigr],\nonumber \\
&{\leqslant}&{\mathbb{E}}\Bigl[\exp\Bigl(\frac{t}{q}M_n - \frac{t^2a}{2q}S_n(a)\Bigr) \exp\Bigl(\frac{t}{2q}(ta- 2x)S_n(a)\Bigr){\mathrm{I}}_{C_n^+}\Bigr],\nonumber \\
&{\leqslant}&{\mathbb{E}}\Bigl[\bigl(V_n(t)\bigr)^{1/q} \exp\Bigl(\frac{t}{2q}(ta- 2x)S_n(a)\Bigr)\Bigr],\nonumber \\
&{\leqslant}&\left({\mathbb{E}}\Bigl[\exp\Bigl(\frac{tp}{2q}(ta- 2x)S_n(a)\Bigr)\Bigr]\right)^{1/p}\!\!.\end{aligned}$$ Consequently, as $p/q=p-1$, we can deduce from with the optimal value $t=x/a$ that $${\mathbb{P}}(C_n^+){\leqslant}\inf_{p>1}\left({\mathbb{E}}\Bigl[\exp\Bigl(-\frac{(p-1)x^2S_n(a)}{2a}\Bigr)\Bigr]\right)^{1/p}\!\!\!\!.$$ We find the same upper bound for ${\mathbb{P}}(C_n^-)$, completing the proof of Theorem \[T-CISNWA\]. $\videbox$  

\
<span>**Proof of Theorem \[T-CISNMISS\].**</span> We already saw from Lemma \[L-SUPERMG\] that for all $t \in {\mathbb{R}}$, $${\mathbb{E}}\Bigl[ \exp\Bigl(tA_n-\frac{t^2}{2}B_n^2\Bigr)\Bigr] {\leqslant}1$$ where $A_n=M_n$ and $B_n^2=a[M]_n +b(a) \!{<\!\!M\!\!>}_n$. It means that the pair of random variables $(A_n,B_n)$ safisties the canonical assumption in @DLPPang2009. Consequently, Theorem \[T-CISNMISS\] immediately follows from Theorem 2.1 in @DLPPang2009. $\videbox$

<span>10</span>

Weighted sums of certain dependent random variables. (1967), 357–367.

On large deviations in the <span>G</span>aussian autoregressive process: stable, unstable and explosive cases. , 2 (2001), 299–316.

. SpringerBriefs in Mathematics. Springer, Cham, 2015.

Large deviations for quadratic forms of stationary <span>G</span>aussian processes. , 1 (1997), 75–90.

Exponential inequalities for self-normalized martingales with applications. , 5 (2008), 1848–1869.

Marked and weighted empirical processes of residuals with applications to robust regressions. (2018).

. Oxford University Press, Oxford, 2013. A nonasymptotic theory of independence, With a foreword by Michel Ledoux.

On the generalization ability of on-line learning algorithms. , 9 (2004), 2050–2057.

Improved risk tail bounds for on-line algorithms. , 1 (2008), 386–390.

. Cambridge University Press, Cambridge, 2006.

A general class of exponential inequalities for martingales and ratios. , 1 (1999), 537–564.

Pseudo-maximization and self-normalized processes. (2007), 172–192.

Exponential inequalities for self-normalized processes with applications. (2009), 372–381.

Exponential inequalities for sums of weakly dependent variables. (2009), no. 28, 752–779.

A growth model, a game, an algebra, <span>L</span>agrange inversion, and characteristic classes. , 1 (1991), 95–119 (1993).

On <span>B</span>ernstein-type inequalities for martingales. , 1 (2001), 109–117.

Exponential inequalities for martingales with applications. , 1 (2015), 1–22.

Bernard <span>F</span>riedman's urn. (1965), 956–970.

On tail probabilities for martingales. (1975), 100–118.

Introduction to online convex optimization. , 3-4 (2016), 157–325.

Probability inequalities for sums of bounded random variables. (1963), 13–30.

Analysis of the forward search using some new results for martingales and empirical processes. , 2 (2016), 1131–1183.

Asymptotic theory of outlier detection algorithms for linear time series regression models. , 2 (2016), 321–348.

Large deviation methods for approximate probabilistic inference. (1998), 311–319.

Subdiffusive fluctuations for internal diffusion limited aggregation. , 1 (1995), 71–86.

Internal diffusion limited aggregation. , 4 (1992), 2117–2140.

On the <span>B</span>ennett-<span>H</span>oeffding inequality. , 1 (2014), 15–27.

Extensions of the <span>H</span>oeffding-<span>A</span>zuma inequalities. (2013), no. 54, 6.

The limiting distribution of the serial correlation coefficient in the explosive case. (1958), 1188–1197.

{'source': 'arXiv_out/1810'}