# Concentration inequalities on the supremum of average

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)$.

### 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 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. 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$.

We can use the law of the iterated logarithms. We have $$\frac{\sqrt n}{\sqrt{\log\log n} }Y_n \geqslant \frac 1{\sqrt{n\log\log n}}\sum_{i=1}^n R_i$$ hence $$\sqrt 2\leqslant \limsup_{n\to+\infty} \frac{\sqrt n}{\sqrt{\log\log n} }Y_n .$$
The function $x\in (x_0,+\infty) \mapsto x^{-1} \log \log x$ is decreasing
for an $x_0$ chosen large enough hence $$\left\lvert Y_n\right\rvert\leqslant \sup_{i\geqslant n}\frac 1{\sqrt{i\log\log i}}\left\lvert \sum_{l=1}^iR_l\right\rvert\sqrt{\frac{\log\log i}{ i }} \leqslant \sup_{i\geqslant n}\frac 1{\sqrt{i\log\log i}}\left\lvert \sum_{l=1}^iR_l\right\rvert\sqrt{\frac{\log\log n}{ n }}\leqslant S \sqrt{\frac{\log\log n}{ n }},$$ where $S=\sup_{i\geqslant 1}\frac 1{\sqrt{i\log\log i}}\left\lvert \sum_{l=1}^iR_l\right\rvert$, which is almost surely finite.