The following question arose in one of my research projects. Before stating it, let me give a short background. We all know the law of iterated logarithm. It states that if $X_1,\ldots,X_n$ are i.i.d. mean $0$, variance $1$ random variables and if $S_n := X_1 + \ldots + X_n$, then almost surely, $$\limsup_{n\rightarrow \infty} \frac{\pm S_n}{\sqrt{2n\log \log n}}=1~.$$ My question is as follows:

Is there a finite sample exponential concentration inequality for the quantity $\left|S_n/\sqrt{2n\log\log n}\right|?$ That is, suppose that $t > 1$ is fixed. Then can we bound the probability something like:$$\mathbb{P}\left(\left|\frac{S_n}{\sqrt{2n\log \log n}}\right|> t\right) \leq e^{-n^\alpha}$$ for some $\alpha > 0$?

Any help will be greatly appreciated.

  • 1
    $\begingroup$ There can be no exponential upper bound with only the first two finite moments. $\endgroup$ Aug 14 '19 at 17:50
  • 2
    $\begingroup$ Even if you assume the summands $X_i $ are bounded, the best you can get is an upper bound which is a negative power of $\log n$. $\endgroup$ Aug 14 '19 at 19:51
  • 1
    $\begingroup$ To expand on Yuval Peres' comment: Let the $X_i$ be $1$ or $-1$, each with probability $1/2$ and let $n$ be even. Then you can compute $P(S_n=2k)$ directly as $$2^{-n} \binom{n}{n/2+k} = 2^{-n} \binom{n}{n/2} \prod_{j=1}^k \frac{n/2-j+1}{n/2+j}.$$ Asymptotics for the central binomial coefficient give that the first two terms are together of order $n^{-1/2}$, and for $k <<n$ the product is $$\prod_{j=1}^k \left(1-\frac{2j+1}{n/2+j}\right) = \prod_{j=1}^k \exp\left( -(1+o(1)) \frac{2j+1}{n/2}\right),$$ which is of order $e^{-C k^2/n}$. If $k=t \sqrt{n\log \log n}$ this is $(\log n)^{-C t^2}$. $\endgroup$ Aug 14 '19 at 21:55
  • $\begingroup$ Thanks losif, Yuval and Kevin. If instead, I had the $X_i$'s to be Rademacher ($\pm 1$ valued with equal probability), is it true that I need a power $\alpha$ at least $1$ to get the concentration bound: $\mathbb{P}(|S_n| > n^\alpha) \leq C e^{-n}$? I mean, the $e^{-n}$ bound is the right concentration rate for $S_n/n > t$ for fixed $t$, right? Of course Hoeffding gives this bound, but I want to be sure that this is indeed the tightest in the Rademacher case here. $\endgroup$
    – Somabha
    Aug 15 '19 at 4:08

As was noted in the comments by Yuval and Kevin, even if $X_1$ is bounded, the best upper bound on the probability in question is a negative power of $\ln n$. To get such a bound (and even an asymptotics), it is actually enough to assume that $E|X_1|^k<\infty$ for some $k>2$. Indeed, a theorem due to S. Nagaev states this:

Suppose that $X_1,X_2,\dots$ are zero-mean unit-variance iid random variables, with $S_n:=\sum_1^n X_i$. Let $Z\sim N(0,1)$. Take any real $k>2$. Then the condition $E|X_1|^k<\infty$ is sufficient for the asymptotic relation $P(S_n\ge z\sqrt n)\sim P(Z\ge z)$ (as $n\to\infty$) to hold in the zone $0\le z\le\sqrt{(\frac k2-1)\ln n}$ and necessary for this relation to hold in the zone $0\le z\le\sqrt{(k+1)\ln n}$.

So, assuming that indeed $E|X_1|^k<\infty$ for some $k>2$, and letting $z=t\sqrt{2\ln\ln n}$, we see that $$P\Big(\Big|\frac{S_n}{\sqrt{2n\ln\ln n}}\Big|> t\Big) \sim P(Z\ge z)\sim\frac1{z\sqrt{2\pi}}e^{-z^2/2} =\frac1{2t\sqrt{\pi\ln\ln n}}(\ln n)^{-t^2} $$ for each $t>0$ as $n\to\infty$.


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.