MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $X_1, ..., X_n$ be i.i.d. sub-Gaussian random variables with mean $0$ and variance $1$. That is, we have $Pr[|X_i| > t] \leq \exp(1-t^2/K^2)$ for all $t>0$ and a parameter $K$.

Then we can use Bernsein-type inequalities to prove deviation bounds for the summation $S := \sum_{i=1}^n X_i^2$ (after appropriate shifting). Namely, we can prove, for an absolute constant $c > 0$,

$Pr[S > n+t] \leq 2 \exp(-c\min(t^2/(K^4 n), t/K^2))$.

Now suppose that, instead, we wish to derive deviation bounds for the summation $S_2 := \sum_{i=1}^n X_i^4$. Obviously,

$Pr[S_2 > t] \leq Pr[S > \sqrt{t}]$ since $S_2 \leq S^2$, and one can use the above Bernstein-type bound for $S$. But is it possible to do better? Are there tighter concentration bounds for summation of powers of independent sub-exponential random variables?

share|cite|improve this question
Could you please take the time to revisit your post carefully and make some edits? Several statements are incorrect. I am unsure at this point if this is due to (a) some inadvertently unstated assumptions (e.g., that the $X_i \geq 0$), (b) multiple typos or (c) something more conceptual being missed here. I don't want to make any assumptions, so I'll leave it to you to make the needed edits. Cheers. – cardinal May 10 '13 at 1:48
I added the assumption that the $X_i$ are centered variables (zero expectation). I don't catch any other missing points. You may assume that $X_i \geq 0$ but I don't think that's necessary. Is there anything specific that doesn't make sense? – Mahdi Cheraghchi May 10 '13 at 2:12
By the way, the setting is exactly the same as Proposition 5.16 on Page 14 of the following: – Mahdi Cheraghchi May 10 '13 at 2:13
Yes, I am familiar with R. Vershynin's work; the way you gave the first bound was a dead giveaway that this was the paper you were looking at. :-) Consider the case $X_i \in \{-1,+1\}$ with probability $1/2$ each. Certainly this satisfies your conditions, but $n = S_2 \leq S^2$ is false, in general. (Take $n=2$, for instance.) As a second example, take $X_i$ to be standard normal and consider $n = 1$ to see that $\mathbb P(S_2 > t) \leq \mathbb P(S > \sqrt{t})$ is false even when $S_2 \leq S^2$. – cardinal May 10 '13 at 13:07
Dear Mahdi, I appreciate the edits and I am trying to be helpful, so let me encourage you to reread my first comment and take it to heart. It now appears that all three of the issues mentioned in that comment are in play here. Regarding your most recent edit and comment: (a) Your edit is incorrect and does not match Prop. 5.16 or the associated Cor. 5.17, (b) my standard normal example is entirely relevant and intended, as you will see if you examine it more carefully and (c) though somewhat immaterial thusfar, a normal random variable is most certainly subexponential (as is its square)! – cardinal May 10 '13 at 19:19

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.