×

zbMATH — the first resource for mathematics

A weakly 1-stable distribution for the number of random records and cuttings in split trees. (English) Zbl 1213.05037
Summary: We study the number of random records in an arbitrary split tree (or, equivalently, the number of random cuttings required to eliminate the tree). We show that a classical limit theorem for the convergence of sums of triangular arrays to infinitely divisible distributions can be used to determine the distribution of this number. After normalization the distributions are shown to be asymptotically weakly 1-stable. This work is a generalization of our earlier results for the random binary search tree in C. Holmgren [“Random records and cuttings in binary search trees,” Comb. Probab. Comput. 19, No. 3, 391–424 (2010; Zbl 1215.05162), which is one specific case of split trees. Other important examples of split trees include \(m\)-ary search trees, quad trees, medians of \((2k+1)\)-trees, simplex trees, tries, and digital search trees.

MSC:
05C05 Trees
05C80 Random graphs (graph-theoretic aspects)
68W40 Analysis of algorithms
68P10 Searching and sorting
68R10 Graph theory (including graph drawing) in computer science
60C05 Combinatorial probability
60F05 Central limit and other weak theorems
68P05 Data structures
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Asmussen, S. (1987). Applied Probability and Queues . John Wiley, Chichester. · Zbl 0624.60098
[2] Beljaev, Ju. K. and Maksimov, V. M. (1963). Analytical properties of a generating function for the number of renewals. Theoret. Prob. Appl. 8 , 108-112. · Zbl 0202.47102
[3] Bourdon, J. (2001). Size and path length of Patricia tries: dynamical sources context. Random Structures Algorithms 19 , 289-315. · Zbl 1016.68029
[4] Broutin, N. and Holmgren, C. (2011). The total path length of split trees. Submitted. · Zbl 1254.05037
[5] Caliebe, A. (2003). Symmetric fixed points of a smoothing transformation. Adv. Appl. Prob. 35 , 377-394. · Zbl 1036.60014
[6] Caliebe, A. and Rösler, U. (2003). Fixed points with finite variance of a smoothing transformation. Stoch. Process. Appl. 107 , 105-129. · Zbl 1075.60503
[7] Devroye, L. (1998). Universal limit laws for depths in random trees. SIAM J. Comput. 28 , 409-432. · Zbl 0915.68089
[8] Devroye, L. (2005). Applications of Stein’s method in the analysis of random binary search trees. In Stein’s Method and Applications (Lecture Notes Ser. Inst. Math. Sci. Natl. Univ. Sing. 5 ), Singapore University Press, pp. 247-297.
[9] Drmota, M., Iksanov, A., Möhle, M. and Rösler, U. (2009). A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree. Random Structures Algorithms 34 , 319-336. · Zbl 1187.05068
[10] Feller, W. (1971). An Introduction to Probability Theory and Its Applications , Vol. II, 2nd edn. John Wiley, New York. · Zbl 0219.60003
[11] Fill, J. A. and Janson, S. (2002). Quicksort asymptotics. J. Algorithms 44 , 4-28. · Zbl 1011.68028
[12] Fill, J. A. and Kapur, N. (2004). Limiting distributions for additive functionals on Catalan trees. Theoret. Comput. Sci. 326 , 69-102. · Zbl 1071.68102
[13] Flajolet, P., Roux, M. and Vallée, B. (2010). Digital trees and memoryless sources: from arithmetics to analysis. To appear in Discrete Math. Theoret. Comput. Sci. · Zbl 1355.68062
[14] Gut, A. (1988). Stopped Random Walks . Springer, New York. · Zbl 0634.60061
[15] Gut, A. (2005). Probability: A Graduate Course . Springer, New York. · Zbl 1076.60001
[16] Holmgren, C. (2010). A weakly 1-stable limiting distribution for the number of random records and cuttings in split trees. Preprint. Available at http://arxiv.org/abs/1005.4590v1. · Zbl 1215.05162
[17] Holmgren, C. (2010). Novel characteristics of split trees by use of renewal theory. Preprint. Available at http://arxiv.org/abs/1005.4594v1. · Zbl 1215.05162
[18] Holmgren, C. (2010). Random records and cuttings in binary search trees. Combinatorics Prob. Comput. 19 , 391-424. · Zbl 1215.05162
[19] Iksanov, A. and Meiners, M. (2010). Exponential rate of almost-sure convergence of intrinsic martingales in supercritical branching random walks. J. Appl. Prob. 47 , 513-525. · Zbl 1203.60129
[20] Iksanov, A. and Möhle, M. (2007). A probabilistic proof of a weak limit law for the number of cuts needed to isolate the root of a random recursive tree. Electron. Commun. Prob. 12 , 28-35. · Zbl 1133.60012
[21] Janson, S. (2004). Random records and cuttings in complete binary trees. In Mathematics and Computer Science. III , Birkhäuser, Basel, pp. 241-253. · Zbl 1063.60018
[22] Janson, S. (2006). Random cutting and records in deterministic and random trees. Random Structures Algorithms 29, 139-179. · Zbl 1120.05083
[23] Janson, S., Łuczak, T. and Rucinski, A. (2000). Random Graphs . Wiley-Interscience, New York.
[24] Kallenberg, O. (2002). Foundations of Modern Probability , 2nd edn. Springer, New York. · Zbl 0996.60001
[25] Mahmoud, H. (1986). On the average internal path length of \(m\)-ary search trees. Acta Informatica 23 , 111-117. · Zbl 0567.68038
[26] Mahmoud, H. and Pittel, B. (1989). Analysis of the space of search trees under the random insertion algorithm. J. Algorithms 10 , 52-75. · Zbl 0685.68060
[27] Meir, A. and Moon, J. W. (1970). Cutting down random trees. J. Austral. Math. Soc. 11 , 313-324. · Zbl 0196.27602
[28] Neininger, R. and Rüschendorf, L. (1999). On the internal path length of \(d\)-dimensional quad trees. Random Structures Algorithms 15 , 25-41. · Zbl 0927.68030
[29] Panholzer, A. (2003). Non-crossing trees revisited: cutting down and spanning subtrees. In Discrete Random Walks (Paris, 2003), Association of Discrete Mathematics and Theoretical Computer Science, Nancy, pp. 265-276. · Zbl 1073.60503
[30] Panholzer, A. (2006). Cutting down very simple trees. Quaest. Math. 29 , 211-227. · Zbl 1120.05020
[31] Rösler, U. (2001). On the analysis of stochastic divide and conquer algorithms. Algorithmica 29 , 238-261. · Zbl 0967.68168
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.