Infra-exponential

See also: Time complexity § Sub-exponential time

A growth rate is said to be infra-exponential or subexponential if it is dominated by all exponential growth rates, however great the doubling time. A continuous function with infra-exponential growth rate will have a Fourier transform that is a Fourier hyperfunction.^[1]

Examples of subexponential growth rates arise in the analysis of algorithms, where they give rise to sub-exponential time complexity, and in the growth rate of groups, where a subexponential growth rate implies that a group is amenable.

A positive-valued, unbounded probability distribution ${\displaystyle {\cal {D}}}$ may be called subexponential if its tails are heavy enough so that^{[2]: Definition 1.1}

${\displaystyle \lim _{x\to +\infty }{\frac {{\mathbb {P}}(X_{1}+X_{2}>x)}{{\mathbb {P}}(X>x)}}=2,\qquad X_{1},X_{2},X\sim {\cal {D}},\qquad X_{1},X_{2}{\hbox{ independent.}}}$

See Heavy-tailed distribution § Subexponential distributions. Contrariwise, a random variable may also be called subexponential if its tails are sufficiently light to fall off at an exponential or faster rate.

References

1. Fourier hyperfunction in the Encyclopedia of Mathematics
2. "Subexponential distributions", Charles M. Goldie and Claudia Klüppelberg, pp. 435-459 in A Practical Guide to Heavy Tails: Statistical Techniques for Analysing Heavy Tailed Distributions, eds. R. Adler, R. Feldman and M. S. Taggu, Boston: Birkhäuser, 1998, ISBN 978-0817639518.