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


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

  • $\begingroup$ This is a nice answer. Thanks! It is possible to have a finite sample bound on the term $\mathbb{P}(Y_n \geq t)$? $\endgroup$ – Martin Zhang Mar 21 '18 at 20:23
  • $\begingroup$ I think one can get such a bound by following the lines of the proof of the law of the iterated logarithm. $\endgroup$ – Iosif Pinelis Mar 21 '18 at 20:38
  • 1
    $\begingroup$ I have added some details to the answer. $\endgroup$ – Iosif Pinelis Mar 22 '18 at 2:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.