# Concentration inequality for the law of iterated logarithm

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.

• There can be no exponential upper bound with only the first two finite moments. Aug 14, 2019 at 17:50
• 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$. Aug 14, 2019 at 19:51
• 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}$. Aug 14, 2019 at 21:55
• 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. Aug 15, 2019 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$$.