Concentration inequalities on the supremum of average after time $n$ 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? 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$.
 A: $\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 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.
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. 
