×

On tail bounds for random recursive trees. (English) Zbl 1251.60009

A stochastic recursion of the following form is studied: \[ X_n\overset{D}{=}\sum_{1}^b A_i(I_n)X_{I_{n,i}}^{(i)} + d(I_n,Z),\quad n\geq 2. \] Here \(X_n, X_n^{(1)},\ldots, X_n^{(b)}\) are i.i.d. random variables,\( d: {\mathcal R}^b\times {\mathcal R}^b\rightarrow {\mathcal R}^k,\) \(A_i\) are deterministic functions,\(Z\in {\mathcal R}^b_{\geq 0}\) are random vectors and \(Z, I_n,X_n, X_n^{(1)},\ldots, X_n^{(b)}\) are mutually independent. Finally, \(\overset{D}{=}\) denotes the equality in distribution. Such recursion arises in probabilistic analysis of algorithms and random trees. The focus of the paper is on bounding the probabilities of the tails \(\mathbb P(X_{n_j}>t).\)

MSC:

60C05 Combinatorial probability
05C05 Trees
05C80 Random graphs (graph-theoretic aspects)
60E15 Inequalities; stochastic orderings
PDFBibTeX XMLCite
Full Text: DOI Euclid

References:

[1] Ali Khan, T. and Neininger, R. (2004). Probabilistic analysis for randomized game tree evaluation. In Mathematics and Computer Science. III , Birkhäuser, Basel, pp. 163-174. · Zbl 1094.68093 · doi:10.1007/978-3-0348-7915-6_17
[2] Ali Khan, T. and Neininger, R. (2007). Tail bounds for the Wiener index of random trees. In 2007 Conf. Analysis of Algorithms (AofA ’07 Discrete Math. Theoret. Comput. Sci. Proc. AH ), Assoc. Discrete Math. Theoret. Comput. Sci., Nancy, pp. 279-289. · Zbl 1192.68198
[3] Bergeron, F., Flajolet, P. and Salvy, B. (1992). Varieties of increasing trees. In CAAP ’92 (Rennes, 1992; Lecture Notes Comput. Sci. 581 ), ed. J.-C. Raoult, Springer, Berlin, pp. 24-48.
[4] Broutin, N. and Devroye, L. (2006). Large deviations for the weighted height of an extended class of trees. Algorithmica 46 , 271-297. · Zbl 1106.68027 · doi:10.1007/s00453-006-0112-x
[5] Broutin, N., Devroye, L., McLeish, E. and de la Salle, M. (2008). The height of increasing trees. Random Structures Algorithms 32 , 494-518. · Zbl 1148.05024 · doi:10.1002/rsa.20202
[6] Fill, J. A. and Janson, S. (2001). Approximating the limiting Quicksort distribution. Random Structures Algorithms 19 , 376-406. · Zbl 0990.68053 · doi:10.1002/rsa.10007
[7] Fill, J. A. and Janson, S. (2009). Precise logarithmic asymptotics for the right tails of some limit random variables for random trees. Ann. Combinatorics 12 , 403-416. · Zbl 1232.60021 · doi:10.1007/s00026-009-0006-0
[8] Janson, S. and Chassaing, P. (2004). The center of mass of the ISE and the Wiener index of trees. Electron. Commun. Prob. 9 , 178-187. · Zbl 1060.60095 · doi:10.1214/ECP.v9-1088
[9] Knessl, C. and Szpankowski, W. (1999). Quicksort algorithm again revisited. Discrete Math. Theoret. Comput. Sci. 3 , 43-64. · Zbl 0947.68042
[10] Lindvall, T. (1992). Lectures on the Coupling Method . John Wiley, New York. · Zbl 0850.60019
[11] McDiarmid, C. J. H. and Hayward, R. B. (1996). Large deviations for Quicksort. J. Algorithms 21 , 476-507. · Zbl 0863.68059 · doi:10.1006/jagm.1996.0055
[12] Munsonius, G. O. (2010). Limit theorems for functionals of recursive trees. Doctoral Thesis, University of Freiburg, Germany. Available at http://www.freidok.uni-freiburg.de/volltexte/7472/. · Zbl 1190.68096
[13] Munsonius, G. O. (2010). The total Steiner \(k\)-distance for \(b\)-ary recursive trees and linear recursive trees. In 21st Internat. Conf. Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA ’10 Discrete Math. Theoret. Comput. Sci. Proc. AH ), Assoc. Discrete Math. Theoret. Comput. Sci., Nancy, pp. 527-548. · Zbl 1355.68067
[14] Pittel, B. (1994). Note on the heights of random recursive trees and random \(m\)-ary search trees. Random Structures Algorithms 5 , 337-347. · Zbl 0790.05077 · doi:10.1002/rsa.3240050207
[15] Rösler, U. (1991). A limit theorem for “Quicksort”. RAIRO Inf. Théor. Appl. 25 , 85-100. · Zbl 0718.68026
[16] Rüschendorf, L. and Schopp, E.-M. (2007). Exponential bounds and tails for additive random recursive sequences. Discrete Math. Theoret. Comput. Sci. 9 , 333-352. · Zbl 1158.60309
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.