 |
|
|
| | | | | |
|
|
|
|
|
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: PDF
Pages: 266-277
Published on: November 11, 2006
|
Bibliography
-
D. J. Aldous and A. Bandyopadhyay. A survey of max-type recursive distributional equations.
Ann. Appl. Probab. 15 (2005), no. 2, 1047-1110.
MR2134098
-
L. Devroye. On the probabilistic worst-case time of "find".
Mathematical analysis of algorithms.
Algorithmica 31 (2001), no. 3, 291-303.
MR1855252 (2002h:68038)
-
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)
-
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)
-
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).
-
S. Janson.
Asymptotics for tails and moments.
Report Mathematisches Forschungsinstitut Oberwolfach 41 (2004).
-
Y. Kasahara.
Tauberian theorems of exponential type.
J. Math. Kyoto Univ. 18 (1978), no. 2, 209-219.
MR0501841 (80g:40008)
-
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)
-
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)
-
L. Rüschendorf.
On stochastic recursive equations of sum- and max-type.
J. Appl. Probab. 43 (2006), 687-703.
|
|
|
|
|
|
|
|
| | | | |
Electronic Communications in Probability. ISSN: 1083-589X |
|
Context