×

Exponential tail bounds for max-recursive sequences. (English) Zbl 1128.60011

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

Citations:

Zbl 0421.40009