Exponential tail bounds for max-recursive sequences

Ludger Rueschendorf (Mathematical Stochastics)
Eva-Maria Schopp (Mathematical Stochastics)

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).

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 266-277

Publication Date: November 11, 2006

DOI: 10.1214/ECP.v11-1227

References

  1. D. J. Aldous and A. Bandyopadhyay. A survey of max-type recursive distributional equations. Ann. Appl. Probab. 15 (2005), no. 2, 1047-1110. MR2134098
  2. L. Devroye. On the probabilistic worst-case time of "find". Mathematical analysis of algorithms. Algorithmica 31 (2001), no. 3, 291-303. MR1855252 (2002h:68038)
  3. L. Devroye. Laws of large numbers and tail inequalities for random tries and PATRICIA trees. Probabilistic methods in combinatorics and combinatorial optimization. J. Comput. Appl. Math. 142 (2002), no. 1, 27-37. MR1910516 (2003b:60036)
  4. R. Grübel and U. Rösler. Asymptotic distribution theory for Hoare's selection algorithm. Adv. in Appl. Probab. 28 (1996), no. 1, 252-269. MR1372338 (96j:68047)
  5. P. Jagers and U. Rösler. Fixed points of max-recursive sequences. M. Drmota et al. (Editor), Mathematics and Computer Science III, 325-338, Birkhäuser, Basel (2004).
  6. S. Janson. Asymptotics for tails and moments. Report Mathematisches Forschungsinstitut Oberwolfach 41 (2004).
  7. Y. Kasahara. Tauberian theorems of exponential type. J. Math. Kyoto Univ. 18 (1978), no. 2, 209-219. MR0501841 (80g:40008)
  8. R. Neininger and L. Rüschendorf. Analysis of algorithms by the contraction method: additive and max-recursive sequences. J.-D. Deuschel and A. Greven (Editors), Interacting stochastic systems, 435-450, Springer, Berlin (2005). MR2118586 (2005j:68140)
  9. S. T. Rachev and L. Rüschendorf. Probability metrics and recursive algorithms. Adv. in Appl. Probab. 27 (1995), no. 3, 770-799. MR1341885 (96m:60005)
  10. L. Rüschendorf. On stochastic recursive equations of sum- and max-type. J. Appl. Probab. 43 (2006), 687-703.
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.