Recursive random variables with subgaussian distributions

Summary We consider sequences of random variables with distributions that satisfy recurrences as they appear for quantities on random trees, random combinatorial structures and recursive algorithms. We study the tails of such random variables in cases where after normalization convergence to the normal distribution holds. General theorems implying subgaussian distributions are derived. Also cases are discussed with non-Gaussian tails. Applications to the probabilistic analysis of algorithms and data structures are given.