SearchPublisher and Institutes
You are here: Home :: Area NEM :: Mathematics :: Stochastics :: Statistics
Ralph Neininger
Recursive random variables with subgaussian distributions
Keywords: tail bound, large deviation principle, recursion, analysis of algorithms, subgaussian distribution
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.
Statistics & Decisions, Oldenbourg Wissenschaftsverlag
Print ISSN: 0721-2631
Volume: 23, 02/2005
Pages: 131 - 146