Timeline for Concentration inequality for the law of iterated logarithm
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 15, 2019 at 18:06 | answer | added | Iosif Pinelis | timeline score: 6 | |
| Aug 15, 2019 at 4:08 | comment | added | Somabha | 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 14, 2019 at 21:55 | comment | added | Kevin P. Costello | 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 19:51 | comment | added | Yuval Peres | 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 17:51 | history | edited | YCor | CC BY-SA 4.0 |
removed capitals
|
| Aug 14, 2019 at 17:50 | comment | added | Iosif Pinelis | There can be no exponential upper bound with only the first two finite moments. | |
| Aug 14, 2019 at 17:25 | history | asked | Somabha | CC BY-SA 4.0 |