×

zbMATH — the first resource for mathematics

On martingale tail sums for the path length in random trees. (English) Zbl 1364.05067
Summary: For a martingale \((X_{n})\) converging almost surely to a random variable \(X\), the sequence \((X_{n}-X)\) is called martingale tail sum. Recently, R. Neininger [Random Struct. Algorithms 46, No. 2, 346–361 (2015; Zbl 1327.68086)] proved a central limit theorem for the martingale tail sum of Régnier’s martingale for the path length in random binary search trees. R. Grübel and Z. Kabluchko [Ann. Appl. Probab. 26, No. 6, 3659–3698 (2016; Zbl 1367.60028)] gave an alternative proof also conjecturing a corresponding law of the iterated logarithm. We prove the central limit theorem with convergence of higher moments and the law of the iterated logarithm for a family of trees containing binary search trees, recursive trees and plane-oriented recursive trees.

MSC:
05C80 Random graphs (graph-theoretic aspects)
05C05 Trees
60G42 Martingales with discrete parameter
60F05 Central limit and other weak theorems
Software:
Quicksort
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Biggins, Uniform convergence of martingales in the branching random walk, Ann Probab 20 pp 137– (1992) · Zbl 0748.60080 · doi:10.1214/aop/1176989921
[2] P. Bindjeme J. A. Fill Exact L 2 -distance from the limit for QuickSort key comparisons (extended abstract) 2012 339 348 · Zbl 1296.68039
[3] Broutin, Large deviations for the weighted height of an extended class of trees, Algorithmica 46 pp 271– (2006) · Zbl 1106.68027 · doi:10.1007/s00453-006-0112-x
[4] Broutin, The total path length of split trees, Ann Appl Probab 22 pp 1745– (2012) · Zbl 1254.05037 · doi:10.1214/11-AAP812
[5] Chauvin, The profile of binary search trees, Ann Appl Probab 11 pp 1042– (2001) · Zbl 1012.60038 · doi:10.1214/aoap/1015345394
[6] Chauvin, Martingales and profile of binary search trees, Electron J Probab 10 pp 420– (2005) · Zbl 1109.60059 · doi:10.1214/EJP.v10-257
[7] Devroye, Universal limit laws for depths in random trees, SIAM J Comput 28 pp 409– (1999) · Zbl 0915.68089 · doi:10.1137/S0097539795283954
[8] Dobrow, Total path length for random recursive trees, Combin Probab Comput 8 pp 317– (1999) · Zbl 0946.05077 · doi:10.1017/S0963548399003855
[9] R. P. Dobrow R. T. Smythe Poisson approximations for functionals of random trees 9 1996 79 92 · Zbl 0855.60025
[10] Drmota, Random trees, An interplay between combinatorics and probability (2009) · Zbl 1170.05022
[11] Drmota, A functional limit theorem for the profile of search trees, Ann Appl Probab 18 pp 288– (2008) · Zbl 1143.68019 · doi:10.1214/07-AAP457
[12] Fill, Quicksort asymptotics, J Algorithms 44 pp 4– (2002) · Zbl 1011.68028 · doi:10.1016/S0196-6774(02)00216-X
[13] Flajolet, Hypergeometrics and the cost structure of quadtrees, Random Struct Algorithms 7 pp 117– (1995) · Zbl 0834.68013 · doi:10.1002/rsa.3240070203
[14] Fuchs, A note on the Quicksort asymptotics, Random Struct Algorithms 46 pp 677– (2015) · Zbl 1332.68039 · doi:10.1002/rsa.20524
[15] Grübel, A functional central limit theorem for branching random walks, almost sure weak convergence, and applications to random trees, Ann Appl Probab · Zbl 1367.60028
[16] Hall, The convergence of moments in the martingale central limit theorem, Z Wahrsch Verw Gebiete 44 pp 253– (1978) · Zbl 0369.60026 · doi:10.1007/BF00534213
[17] Heyde, On central limit and iterated logarithm supplements to the martingale convergence theorem, J Appl Probab 14 pp 758– (1977) · Zbl 0385.60033 · doi:10.1017/S0021900200105297
[18] Hoare, Quicksort, Comput J 5 pp 10– (1962) · doi:10.1093/comjnl/5.1.10
[19] Jabbour-Hattab, Martingales and large deviations for binary search trees, Random Struct Algorithms 19 pp 112– (2001) · Zbl 0983.60034 · doi:10.1002/rsa.1023
[20] Katona, Width of a scale-free tree, J Appl Probab 42 pp 839– (2005) · Zbl 1079.05090 · doi:10.1017/S0021900200000814
[21] Klenke, Probability theory, A comprehensive course (2014)
[22] Knuth, The art of computer programming: Sorting and searching 3 (1973) · Zbl 0302.68010
[23] Mahmoud, Limiting distributions for path lengths in recursive trees, Probab Engrg Inform Sci 5 pp 53– (1991) · Zbl 1134.68361 · doi:10.1017/S0269964800001881
[24] Mahmoud, Distances in random plane-oriented recursive trees, J Comput Appl Math 41 pp 237– (1992) · Zbl 0768.05029 · doi:10.1016/0377-0427(92)90252-S
[25] Mahmoud, Evolution of random search trees, Wiley-Interscience series in discrete mathematics and optimization (1992)
[26] Mahmoud, Pólya Urn Models, Texts in statistical science series (2009)
[27] McDiarmid, Large deviations for quicksort, J Algorithms 21 pp 476– (1996) · Zbl 0863.68059 · doi:10.1006/jagm.1996.0055
[28] Munsonius, On the asymptotic internal path length and the asymptotic Wiener index of random split trees, Electron J Probab 16 pp 1020– (2011) · Zbl 1226.60038 · doi:10.1214/EJP.v16-889
[29] Munsonius, Limit theorems for depths and distances in weighted random b-ary recursive trees, J Appl Probab 48 pp 1060– (2011) · Zbl 1234.05058
[30] Neininger, On the internal path length of d-dimensional quad trees, Random Struct Algorithms 15 pp 25– (1999) · Zbl 0927.68030 · doi:10.1002/(SICI)1098-2418(199908)15:1<25::AID-RSA2>3.0.CO;2-R
[31] Neininger, Rates of convergence for Quicksort, J Algorithms 44 pp 51– (2002) · Zbl 1010.68049 · doi:10.1016/S0196-6774(02)00206-7
[32] Neininger, Refined quicksort asymptotics, Random Struct Algorithms 46 pp 346– (2015) · Zbl 1327.68086 · doi:10.1002/rsa.20497
[33] Neveu, Mathematical foundations of the calculus of probability (1965) · Zbl 0137.11301
[34] Neveu, Discrete-parameter martingales, Translated from the French by T. P. Speed, revised edition, North-Holland Mathematical Library, Vol. 10 (1975) · Zbl 0345.60026
[35] Pittel, Note on the heights of random recursive trees and random m,-ary search trees, Random Struct Algorithms 5 pp 337– (1994) · Zbl 0790.05077 · doi:10.1002/rsa.3240050207
[36] Régnier, A limiting distribution for quicksort, RAIRO Inform Théor Appl 23 pp 335– (1989) · Zbl 0677.68072 · doi:10.1051/ita/1989230303351
[37] Rényi, On mixing sequences of random variables, Acta Math Acad Sci Hungar 9 pp 389– (1958) · Zbl 0104.36301 · doi:10.1007/BF02020270
[38] Rogers, Diffusions, Markov processes, and martingales, Volume 1: Foundations, Cambridge Mathematical Library (2000)
[39] Rösler, A limit theorem for ”Quicksort, RAIRO Inform Théor Appl 25 pp 85– (1991) · Zbl 0718.68026 · doi:10.1051/ita/1991250100851
[40] Schopp, A functional limit theorem for the profile of b-ary trees, Ann Appl Probab 20 pp 907– (2010) · Zbl 1208.60030 · doi:10.1214/09-AAP640
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.