4
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ There can be no exponential upper bound with only the first two finite moments. $\endgroup$
    – Iosif Pinelis
    Commented Aug 14, 2019 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$
    – Yuval Peres
    Commented Aug 14, 2019 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$
    – Kevin P. Costello
    Commented Aug 14, 2019 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
    Commented Aug 15, 2019 at 4:08

1 Answer 1

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .