On the Asymptotic Internal Path Length and the Asymptotic Wiener Index of Random Split Trees

Goetz Olaf Munsonius (University of Frankfurt)

Abstract


The random split tree introduced by Devroye (1999) is considered. We derive a second order expansion for the mean of its internal path length and furthermore obtain a limit law by the contraction method. As an assumption we need the splitter having a Lebesgue density and mass in every neighborhood of 1. We use properly stopped homogeneous Markov chains, for which limit results in total variation distance as well as renewal theory are used. Furthermore, we extend this method to obtain the corresponding results for the Wiener index.

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

Pages: 1020-1047

Publication Date: June 1, 2011

DOI: 10.1214/EJP.v16-889

References

  1. T. Ali Khan and R. Neininger. Tail bounds for the Wiener index of random trees. In 2007 Conference on Analysis of Algorithms, AofA 07, 279-289, Discrete Math. Theor. Comput. Sci. Proc., AH, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2007. MR2509528 (2010i:60027)
  2. F. Bergeron, P. Flajolet, B. Salvy. Varieties of increasing trees. CAAP '92 (Rennes, 1992), 24-48, Lecture Notes in Comput. Sci., 581, Springer, Berlin, 1992. MR1251994 (94j:68233)
  3. P. J. Bickel, D. A. Freedman. Some asymptotic theory for the bootstrap. Ann. Statist. 9 (1981), no. 6, 1196-1217. MR0630103 (83a:62051)
  4. N. Broutin and C. Holmgren. The total path length of split trees. preprint, 2011. http://arxiv.org/abs/1102.2541,
  5. V. Bruhn. Eine Methode zur asymptotischen Behandlung einer Klasse von Rekursionsgleichungen mit einer Anwendung in der stochastischen Analyse des Quicksort-Algorithmus. PhD thesis, University of Kiel, Germany, 1996.
  6. H.-H. Chern, H.-K. Hwang. Transitional behaviors of the average cost of Quicksort with median-of-(2t+1). Algorithmica 29 (2001), no. 1-2, 44-69. MR1887298 (2003k:68044)
  7. L. Devroye. Universal limit laws for depths in random trees. SIAM J. Comput. 28 (1999), no. 2, 409-432 (electronic). MR1634354 (2000e:68073)
  8. R. P. Dobrow, J. A. Fill. Total path length for random recursive trees. Combin. Probab. Comput. 8 (1999), no. 4, 317-333. MR1723646 (2000k:60016)
  9. L. C. Evans, R. F. Gariepy. Measure theory and fine properties of functions. CRC Press, Boca Raton, FL, 1992. MR1158660 (93f:28001)
  10. J. A. Fill, S. Janson. Quicksort asymptotics. J. Algorithms 44 (2002), no. 1, 4-28. MR1932675 (2003m:68032)
  11. P. Flajolet, G. Labelle, L. Laforest, B. Salvy. Hypergeometrics and the cost structure of quadtrees. Random Structures Algorithms 7 (1995), no. 2, 117-144. MR1369059 (96m:68034)
  12. D. Griffeath. A maximal coupling for Markov chains. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 31 (1974/75), 95-106. MR0370771 (51 #6996)
  13. A. Gut. Stopped random walks. Limit theorems and applications. Springer-Verlag, New York, 1988. MR0916870 (88m:60085)
  14. C. Holmgren. Novel characteristics of split trees by use of renewal theory. 2010. submitted.
  15. S. Janson. The Wiener index of simply generated random trees. Random Structures Algorithms 22 (2003), no. 4, 337-358. MR1980963 (2004b:05186)
  16. H. M. Mahmoud. On the average internal path length of m-ary search trees. Acta Inform. 23 (1986), no. 1, 111-117. MR0845626 (87i:68008)
  17. H. M. Mahmoud, B. Pittel. Analysis of the space of search trees under the random insertion algorithm. J. Algorithms 10 (1989), no. 1, 52-75. MR0987097 (90a:68012)
  18. C. J. H. McDiarmid, R. B. Hayward. Large deviations for Quicksort. J. Algorithms 21 (1996), no. 3, 476-507. MR1417660 (97g:68052)
  19. G. O. Munsonius and L. Rüschendorf. Limit theorems for depths and distances in weighted random b-ary recursive trees. 2010. submitted.
  20. R. Neininger. On a multivariate contraction method for random recursive structures with applications to Quicksort. Random Structures Algorithms 19 (2001), no. 3-4, 498-524. MR1871564 (2002m:68020)
  21. R. Neininger. The Wiener index of random trees. Combin. Probab. Comput. 11 (2002), no. 6, 587-597. MR1940122 (2003k:05046)
  22. R. Neininger, L. Rüschendorf. On the internal path length of d-dimensional quad trees. Random Structures Algorithms 15 (1999), no. 1, 25-41. MR1698407 (2000h:60034)
  23. M. Régnier. A limiting distribution for quicksort. RAIRO Inform. Théor. Appl. 23 (1989), no. 3, 335-343. MR1020478 (90k:68132)
  24. U. Rösler. A limit theorem for "Quicksort". RAIRO Inform. Théor. Appl., 25 (1991), no. 1, 85-100. MR1104413 (92f:68028)
  25. U. Rösler. On the analysis of stochastic divide and conquer algorithms. Algorithmica 29 (2001), no. 1-2, 238-261. MR1887306 (2003b:68217)


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