Rueschendorf, Ludger; Schopp, Eva-Maria Exponential tail bounds for max-recursive sequences. (English) Zbl 1128.60011 Electron. Commun. Probab. 11, 266-277 (2006). Summary: 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 Y. Kasahara [J. Math. Kyoto Univ. 18, 209–219 (1978; Zbl 0421.40009)]. MSC: 60C05 Combinatorial probability 68Q25 Analysis of algorithms and problem complexity 68W40 Analysis of algorithms 60E15 Inequalities; stochastic orderings Keywords:worst case analysis; divide and conquer algorithms; parallel search algorithms; exponential tail bounds Citations:Zbl 0421.40009 × Cite Format Result Cite Review PDF Full Text: DOI EuDML