subexponential

Subexponential may refer to two related concepts in mathematics and computer science.

In probability theory, a distribution F on the nonnegative real line is called subexponential if it is heavy-tailed and, for independent and identically distributed random variables X1, X2, ..., with distribution F, the tail of their sum satisfies P(X1 + ... + Xn > x) ~ n P(X > x) as x → ∞ for every n ≥ 2. Equivalently, the tail of the n-fold convolution F^{*n} satisfies overline{F^{*n}}(x) ~ n overline{F}(x) as x → ∞. Subexponential distributions form a subclass of heavy-tailed distributions, in which the probability of a large sum is asymptotically governed by a single large summand rather than by many moderate contributions. Common examples include Pareto, lognormal, and Weibull distributions with shape parameter in (0, 1); regularly varying tails are typically subexponential as well. The exponential distribution is not subexponential, and many light-tailed distributions such as the normal or gamma do not belong to this class. The class is closed under convolution: if F is subexponential, then F^{*m} is subexponential for all m ≥ 1. Subexponential models are widely used in risk theory, insurance, and queueing, where they describe aggregate losses and waiting times driven by rare, large events.

In computer science, subexponential also describes running times of algorithms. A subexponential time algorithm has time complexity exp(o(n)) in the input size n, meaning it grows faster than any polynomial but slower than any fixed-base exponential, and can be significant for certain NP-hard problems under specialized models or assumptions.