Let $R\_1, R\_2, \cdots$ be i.i.d. Rademacher random variables (taking values $-1,+1$ w.p. $0.5$). At time $k$, their average is $\frac{1}{k}\sum\_{i=1}^k R\_i$. One can imagine after $k\geq n$ for some $n$, this average becomes quite close to zero. It is interesting to characterize the maximum deviation of the average after time $n$: 
$$ Y\_n = \sup\_{k\geq n} \frac{1}{k}\sum\_{i=1}^k R\_i.$$
Since $Y\_n$ converges to $0$ as $n$ grows, the characterization should be in terms of $n$.
The answer can be upper bounds on either $\mathbb{E}[Y\_n]$ or $\mathbb{P}(Y\_n \geq t)$. 


Specifically, is it possible to have a finite sample bound on the term $\mathbb{P}(Y\_n \geq t)$? 


### A few remarks:


* My guess is that $Y\_n = \tilde{O}\_p(\frac{1}{\sqrt{n}})$ , where $\tilde{O}\_p$ omits some $\log n$ factor. Yet given the simplicity of the problem, it is desirable to get the exact answer.
* This is related to the question [Expected supremum of average?](https://mathoverflow.net/questions/147270/expected-supremum-of-average) The difference is there the $sup$ is taken over $1 \leq k \leq n$, where a constant bound can be obtained. Here we are interested in how fast $Y\_n$ approaches zero as $n$ grows. Hence the bound should depend on $n$.
* A concrete example is as follows. Consider a sequence of coin tosses $T\_1, T\_2, \cdots$. The running estimate of the head probability at time $k$ is $\frac{1}{k} \sum\_{i=1}^k I\_{\{T\_i=head\}}$. Then $Y\_n = \sup\_{k\geq n} \frac{1}{k} \sum\_{i=1}^k I\_{\{T\_i=head\}}$ is the maximum estimation error of head probability after toss $n$.



Concentration inequalities on the supremum of average after time $n$
$\newcommand{\ep}{\epsilon}
\newcommand{\R}{\mathbb{R}}
\newcommand{\E}{\operatorname{\mathsf E}} 
\newcommand{\PP}{\operatorname{\mathsf P}}$ 


Let $S\_k:=\sum\_{i=1}^k R\_i$ and $K\_j:=\{n\_j,\dots,n\_{j+1}\}$, where $n\_j:=n2^{j-1}$. For $x>0$, 
\begin{align\*}
 \PP(Y\_n> x)=\PP(\sup\_{k\ge n}\frac{S\_k}k> x)
 &=\PP(\exists k\ge n\ S\_k> kx) \\ 
 &\le\sum\_{j=1}^\infty\PP(\exists k\in K\_j\ S\_k> kx) \\ 
 &\le\sum\_{j=1}^\infty\PP(\max\_{1\le k\le n\_{j+1}}\ S\_k> n\_j x) \\ 
 &\le\sum\_{j=1}^\infty \inf\_{h\ge0}e^{-hn\_j x}\E e^{hS\_{n\_{j+1}}} \\ 
 &\le\sum\_{j=1}^\infty \inf\_{h\ge0}\exp\{-hn\_j x+n\_{j+1}h^2/2\} 
 =\sum\_{j=1}^\infty p\_j, 
\end{align\*}
where 
\begin{equation}
 p\_j:=\exp\{-\frac{n\_j^2 x^2}{2n\_{j+1}}\}=\exp\{-2^{j-3}n x^2 \}. 
\end{equation}
Here are details on the above multi-line display. The third inequality there is an instance of [Doob's submartingale inequality](https://en.wikipedia.org/wiki/Doob%27s_martingale_inequality) applied to the submartingale $(e^{hS\_n})$ -- which is a submartingale by virtue of Jensen's inequality applied to the convex function $e^{h\cdot}$ and because $(S\_n)$ is a martingale. The fourth inequality in the above multi-line display follows because 
$\E e^{hS\_n}\le \exp\{nh^2/2\}$, which is easy to prove -- cf. e.g. the last three lines in the multi-line display in [the proof of Hoeffding's inequality](https://en.wikipedia.org/wiki/Hoeffding%27s_inequality).


Noting that $p\_{j+1}/p\_j\le p\_1$ for $j\ge1$ and letting $x=u/\sqrt n$ for $u>0$, we get 
\begin{equation}
 \PP(Y\_n> u/\sqrt n)\le\frac{p\_1}{1-p\_1}
 =\frac{e^{-u^2/4}}{1-e^{-u^2/4}}\to0
\end{equation}
if $u\to\infty$. So, $Y\_n=O\_P(1/\sqrt n)$. 


On the other hand, 
\begin{equation}
 \PP(Y\_n> u/\sqrt n)\ge \PP(\frac{S\_n}n> u/\sqrt n)\to1-\Phi(u)>0
\end{equation}
for any real $u$, where $\Phi$ is the standard normal cdf. So, the rate $Y\_n=O\_P(1/\sqrt n)$ is sharp. 


