Concentration inequalities on the supremum of average after time $n$

Question

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

Answer 1

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