Suppose $X_1, X_2, \ldots, X_n$ are independent and each has the same distribution with a sub-exponential random variable $X$ (for example, $X$ is the square of a standard normal Gaussian variable). Can I obtain a concentration inequality for the square of sub-exponential $X_i$, say,

$$\mathbb{P}\left( \frac{1}{n} \left( X_1^2+\cdots+X_n^2 \right) \ge \mathbb{E}\left[X^2\right] + t \right) \le C \exp\left( - n \cdot \min\left( C_1 t^2, C_2 t, C_3 \sqrt{t} \right) \right),$$

where $C, C_1, C_2, C_3$ are constants?

This problem arises in my research.


Actually, for i.i.d. sub-Gaussian random variables $Y_i\ (i=1,\ldots,n)$, I knew that

$$\mathbb{P}\left( \frac{1}{n} \left(Y_1+\cdots+Y_n\right) \ge \mathbb{E}\left[Y\right] + t \right) \le \exp\left( - n\cdot C_1 t^2 \right).$$

Besides, since $Y_i^2\ (i=1,2,\ldots,n)$ are sub-exponential, I also knew that

$$\mathbb{P}\left( \frac{1}{n} \left(Y_1^2+\cdots+Y_n^2\right)\ge \mathbb{E}\left[ Y^2 \right] + t \right) \le \exp\left( - n\cdot \min(C_1 t^2, C_2 t) \right).$$

These two inequalities can be proved by a Chernoff bound, since the moment generating functions of $Y$ (sub-Gaussian) and $Y^2$ (sub-exponential) both exist.

However, I want to know whether there is an inequality like

$$\mathbb{P}\left( \frac{1}{n} \left( Y_1^4+\cdots+Y_n^4 \right) \ge \mathbb{E}\left[Y^4\right] + t \right) \le C \exp\left( - n \cdot \min\left( C_1 t^2, C_2 t, C_3 \sqrt{t} \right) \right),$$

even though the moment generating function of $Y^4$ (square of sub-exponential) does not exist.

  • $\begingroup$ Have you checked Eq. (2.20), on p.20 of this? ["High-dimensional statistics: A non-asymptotic viewpoint," by M. Wainwright. Chapter 2, 2015.]; or Proposition 5.16 of these notes ["Introduction to the non-asymptotic analysis of random matrices", Roman Vershynin, 2011] $\endgroup$
    – Clement C.
    Feb 13 '16 at 2:52
  • $\begingroup$ For the square of a standard Gaussian r.v., which is subexponential with parameters $(2,4)$, you should also have a look at Examples 2.4 and 2.5 of the first reference given. $\endgroup$
    – Clement C.
    Feb 13 '16 at 3:02
  • $\begingroup$ @ClementC. Thank you very much for your reponse! I guess that you meant there actually "exists" a concentration inequality for sub-exponential variables. However, what I wonder is whether there exists an inequality for "the square of sub-exponential variables". See my remark above, edited just know. $\endgroup$
    – elimpalm
    Feb 13 '16 at 7:25
  • 3
    $\begingroup$ No. $P(\frac {X_1^2}n\ge t)=\Omega(\exp(-\lambda \sqrt t\sqrt n))$. Once your variable is strongly not-sub-exponential, the max of the sum is achieved for a single large deviation probability of which no longer scales as $\exp(-\alpha n)$. $\endgroup$
    – A.S.
    Feb 16 '16 at 23:40
  • 2
    $\begingroup$ Having said that, you should be able to find a $\exp(-C\sqrt n \sqrt t)$ type of bound with some polynomial pre-factor. $\endgroup$
    – A.S.
    Feb 16 '16 at 23:54

No. For non-negative i.i.d. $Y_i$, $$P(Y_1\ge (\mu+t)n)\le P\Bigg(\sum_{i=1}^n Y_i\ge (\mu+t)n\Bigg)\le\exp(-nf(t))$$ implies that $Y_1$ is sub-exponential and a square of a sub-exponential is not guaranteed to be sub-exponential.

However you can obtain $$P(X_1^2+\dots+X_n^2>nt)\sim nP(X_1^2>nt)=n\exp(-\lambda\sqrt {nt})$$ for $X_i\sim \exp(\lambda)$ which you can extend to all subexponential $X_i$ that have exponential tails.

  • 1
    $\begingroup$ How do you get the bound for the squared exponential distribution? $\endgroup$ Dec 12 '18 at 20:59
  • $\begingroup$ Could you please provide more details on the $P(X_1^2+\cdots+X_n^2 > nt) \sim nP(X_1^2>nt)$ part? I'm trying to figure out the induction. Thanks! $\endgroup$
    – TomHall
    May 15 '20 at 14:06
  • $\begingroup$ This is the known/standard fact from the general theory of heavy tailed distributions. Roughly, the sum is dominated by the heaviest one. $\endgroup$
    – Maciej S.
    Sep 13 '20 at 20:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.