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.


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.