A Lower Tail Bound For Sums of Fat-Tailed Distributions

A Lower Tail Bound For Sums of Fat-Tailed Distributions

I needed to estimate the probability that ∑nxi≥t\sum^n x_i \geq t where xi∼Pareto(α)x_i \sim \text{Pareto}\Big(\alpha). Because there’s no MGF defined, the usual tricks don’t apply. Instead, I came up with a (sometimes) useful lower bound for the tails of sums of fat-tailed distributions. I claim that for identically distributed, positive-valued RVs:

P[∑nxi≥t]≥supm∈[1,n](nm)P[xi≥t/m]mP[xi<t/m]n−m\begin{equation} P\big[\sum^n x_i \geq t] \geq \text{sup}\limits_{m \in [1, n]} {n \choose m} P\left[ x_i \geq t/m \right]^m P\left[ x_i \lt t/m \right]^{n - m} \end{equation}

We start with the following (very loose) inequality. Thinking about this geometrically, the RHS of the first equation below represents an n-dimensional cube in the half-space where ∑nxi≥t\sum^n x_i \geq t. This bound can be improved if we consider that the inequality holds when we replace nn and t/nt/n on the RHS with any of (1,t),(2,t/2),…,(n,t/n)(1, t), (2, t/2), \ldots, (n, t/n). In the case where nn variables each take value t/nt/n the n-dimensional cube just touches the plane dividing ℝn\mathbb{R}^n.

P[∑nxi≥t]≥P[xi≥t/n]n\begin{equation} P\big[\sum^n x_i \geq t] \geq P\left[ x_i \geq t/n\right]^n \end{equation}

P[∑nxi≥t]≥supm∈[1,n]P[xi≥t/m]m\begin{equation} P\big[\sum^n x_i \geq t] \geq \text{sup}\limits_{m \in [1, n]} P\left[ x_i \geq t/m \right]^m \end{equation}

The original claim can be thought of as a partition of ℝn\mathbb{R}^n into 2n2^n disjoint regions. For any value of mm, the subset of {0,1}n\{0, 1\}^n with mm bits set resides entirely in the half-space where ∑nxi≥t\sum^n x_i \geq t. The set defined on the RHS is a subset of the region we care about. 🎉

𝐍.𝐁\textbf{N.B} — To illustrate that this bound is sometimes useful, consider the following example with n,m,t:=6,1,100n, m, t := 6, 1, 100 and f(x)=0.6366/(1+x2)f(x) = 0.6366/\left(1\ +\ x^{2}\right). This is, for all intents and purposes, the absolute value of the standard Cauchy. For reference, simulation gives us P[Σnxi>100]≈0.04375P[\Sigma^n x_i > 100] \approx 0.04375.

(nm)(1−∫0tmf(x)dx)m(∫0tmf(x)dx)n−m≈0.03699\begin{equation} { n \choose m}\left(\ 1-\int_{0}^{\frac{t}{m}}f\left(x\right)\ dx\right)^{m}\left(\ \int_{0}^{\frac{t}{m}}f\left(x\right)\ dx\right)^{n-m} \approx 0.03699 \end{equation}