@article{ECP1227,
author = {Ludger Rueschendorf and Eva-Maria Schopp},
title = {Exponential tail bounds for max-recursive sequences},
journal = {Electron. Commun. Probab.},
fjournal = {Electronic Communications in Probability},
volume = {11},
year = {2006},
keywords = {recursive algorithm, exponential bounds, divide and conquer algorithm, probabilistic analysis of algorithms},
abstract = {Exponential tail bounds are derived for solutions of max-recursive equations and for max-recursive random sequences, which typically arise as functionals of recursive structures, of random trees or in recursive algorithms. In particular they arise in the worst case analysis of divide and conquer algorithms, in parallel search algorithms or in the height of random tree models. For the proof we determine asymptotic bounds for the moments or for the Laplace transforms and apply a characterization of exponential tail bounds due to Kasahara (1978).},
pages = {no. 28, 266-277},
issn = {1083-589X},
doi = {10.1214/ECP.v11-1227},
url = {http://ecp.ejpecp.org/article/view/1227}}