4
$\begingroup$

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\left(-c\min\left(t^2/(K^4 n), t/K^2\right)\right).$$

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?

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ 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. $\endgroup$
    – cardinal
    Commented May 10, 2013 at 1:48
  • $\begingroup$ 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? $\endgroup$
    – MCH
    Commented May 10, 2013 at 2:12
  • $\begingroup$ By the way, the setting is exactly the same as Proposition 5.16 on Page 14 of the following: arxiv.org/pdf/1011.3027v7.pdf $\endgroup$
    – MCH
    Commented May 10, 2013 at 2:13
  • $\begingroup$ 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$. $\endgroup$
    – cardinal
    Commented May 10, 2013 at 13:07
  • 2
    $\begingroup$ 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)! $\endgroup$
    – cardinal
    Commented May 10, 2013 at 19:19

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .