2
$\begingroup$

Suppose $X_1,...,X_N$ are $N$ i.i.d random variables with heavy tailed distributions. For example, $E[X_i^p]\leq 1$ for some $p\geq 1$. Are there some concentration inequalities to bound the tail

$$P(\sum_{i=1}^N X_i>t)$$

for $t>0$?

If $X_i$ are sub-Gaussian or sub-exponential, than standard concentration inequalities such as Chernoff bounds and Hoeffding's inequality work well. So how about only requiring $E[X_i^p]$ to be bounded?

$\endgroup$
0

1 Answer 1

2
$\begingroup$

The standard way to proceed here is by right-tail truncation (see e.g. Section 1 of Nagaev's paper), as follows.

Suppose that $EX_i=0$ for all $i$; the condition that the $X_i$'s are identically distributed will not be used in this answer. Let $S_N:=\sum_{i=1}^N X_i$. Let $T_N:=\sum_{i=1}^N Y_i$, where $Y_i:=X_i\,1(X_i\le b)$ for some real $b>0$. Then \begin{align} P(S_N\ge t)&\le P(\max_{i=1}^N X_i>b)+P(T_N\ge t) \\ &\le\sum_{i=1}^N P(X_i>b)+P(T_N\ge t). \tag{0}\label{0} \end{align}

Finally, to upper-bound $P(T_N\ge t)$ for real $t\ge0$, one can use e.g. Hoeffding's bound (2.9), to get $$\begin{align} P(T_N\ge t) &\le\exp\Big(-\frac tb\, g\Big(\frac{B^2}{bt}\Big)\Big) \tag{10}\label{10} \\ &\le\Big(\frac{B^2}{bt}\Big)^{ct/b}, \tag{20}\label{20} \end{align}$$ where $B:=\sqrt{\sum_{i=1}^N EX_i^2}$, $g(u):=(1+u)\ln(1+\frac1u)-1$, and $c:=\min_{0<u<1}\dfrac{g(u)}{\ln\frac1u}=0.707\ldots$. In particular, choosing $b=ct/p$ for an arbitrary real $p>0$, from \eqref{20} we get $$P(T_N\ge t)\le\Big(\frac pc \frac{B^2}{t^2}\Big)^p. \tag{30}\label{30}$$

The bound in \eqref{10} is the best bound in its terms based on the Bernstein--Chernoff inequality. Other, similar, more general, and/or better results can be found e.g. in mentioned Section 1 of of Nagaev's paper and in this paper; see also references therein.


Another bound on $P(S_N\ge t)$ for real $t>0$ can be obtained from the Rosenthal inequality -- see e.g. this question and this answer: $$P(S_N\ge t)\le\frac{E|S_N|^p}{t^p} \le \frac{K(p)}{t^p}\,(A_p+B^p)$$ for real $p\ge2$, where $K(p)$ is a real number depending only on $p$ and $A_p:=\sum_{i=1}^N E|X_i|^p$. (Actually, the Rosenthal bound can be derived from \eqref{0} and \eqref{30}.)

For $p\in[1,2]$, one can similarly use the von Bahr--Esseen inequality, to get $$P(S_N\ge t)\le\frac{E|S_N|^p}{t^p} \le \frac{L(p)}{t^p}\,A_p,$$ where $L(p)\in[1,2]$ depends only on $p$.

$\endgroup$
2
  • $\begingroup$ Thanks for this great solution. $\endgroup$
    – jkfds
    Commented Mar 14 at 8:27
  • $\begingroup$ @jkfds : I am glad you liked the answer. In such a case, these guidelines may be relevant. $\endgroup$ Commented Mar 15 at 2:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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