Hostname: page-component-848d4c4894-2pzkn Total loading time: 0 Render date: 2024-06-01T16:17:57.712Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Variety of Shapes on the Fringe of a Random Recursive Tree

Part of: Graph theory Limit theorems Combinatorial probability

Published online by Cambridge University Press:  14 July 2016

Qunqiang Feng  and
Hosam M. Mahmoud
Qunqiang Feng*
Affiliation:
University of Science and Technology of China
Hosam M. Mahmoud*
Affiliation:
The George Washington University
*
∗Postal address: Department of Statistics and Finance, University of Science and Technology of China, Hefei 230026, China. Email address: fengqq@ustc.edu.cn
∗∗Postal address: Department of Statistics, The George Washington University, Washington, DC 20052, USA. Email address: hosam@gwu.edu
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We consider a variety of subtrees of various shapes lying on the fringe of a recursive tree. We prove that (under suitable normalization) the number of isomorphic images of a given fixed tree shape on the fringe of the recursive tree is asymptotically Gaussian. The parameters of the asymptotic normal distribution involve the shape functional of the given tree. The proof uses the contraction method.

Keywords

Random treerecurrencecontraction method

MSC classification

Secondary: 05C05: Trees 60C05: Combinatorial probability 60F05: Central limit and other weak theorems
Type
Research Article
Information
Journal of Applied Probability , Volume 47 , Issue 1 , March 2010 , pp. 191 - 200
Copyright
Copyright © Applied Probability Trust 2010 

References

Bergeron, F., Flajolet, P. and Salvy, B. (1992). Varieties of increasing trees. In CAAP '92 (Lecture Notes Comput. 581), Springer, Berlin, pp. 24–48.Google Scholar
Chern, H.-H., Hwang, H.-K. and Tsai, T.-H. (2002). An asymptotic theory for Cauchy–Euler differential equations with applications to the analysis of algorithms. J. Algorithms 44, 177–225.Google Scholar
Chyzak, F., Drmota, M., Klausner, T. and Kok, G. (2008). The distribution of patterns in random trees. Combinatorics Prob. Comput. 17, 21–59.Google Scholar
Dobrow, R. P. and Fill, J. A. (1996). Multiway trees of maximum and minimum probability under the random permutation model. Combinatorics Prob. Comput. 5, 351–371.CrossRefGoogle Scholar
Feng, Q., Mahmoud, H. M. and Panholzer, A. (2008). Phase changes in subtree varieties in random recursive and binary search trees. SIAM J. Discrete Math. 22, 160–184.CrossRefGoogle Scholar
Fill, J. A. (1996). On the distribution of binary search trees under the random permutation model. Random Structures Algorithms 8, 1–25.Google Scholar
Fill, J. A. and Kapur, N. (2005). Transfer theorems and asymptotic distributional results for m-ary search trees. Random Structures Algorithms 26, 359–391.CrossRefGoogle Scholar
Flajolet, P., Gourdon, X. and Martínez, C. (1997). Patterns in random binary search trees. Random Structures Algorithms 11, 223–244.Google Scholar
Knuth, D. E. (1998). The Art of Computer Programming III. Sorting and Searching, 2nd edn. Addison-Wesley, Reading, MA.Google Scholar
Mahmoud, H. M. (1992). Evolution of Random Search Trees. John Wiley, New York.Google Scholar
Mahmoud, H. M., Smythe, R. T. and Régnier, M. (1997). Analysis of Boyer-Moore-Horspool string-matching heuristic. Random Structures Algorithms 10, 169–186.3.0.CO;2-T>CrossRefGoogle Scholar
Neininger, R. (2001). On a multivariate contraction method for random recursive structures with applications to Quicksort. Random Structures Algorithms 19, 498–524.Google Scholar
Neininger, R. (2002). The Wiener index of random trees. Combinatorics Prob. Comput. 11, 587–597.Google Scholar
Neininger, R. and Rüschendorf, L. (2004). A general limit theorem for recursive algorithms and combinatorial structures. Ann. Appl. Prob. 14, 378–418.CrossRefGoogle Scholar
Rachev, S. T. and Rüschendorf, L. (1995). Probability metrics and recursive algorithms. Adv. Appl. Prob. 27, 770–799.Google Scholar
Régnier, M. and Szpankowski, W. (1998) On pattern frequency occurrences in a Markovian sequence. Average-case analysis of algorithms. Algorithmica 22, 631–649.CrossRefGoogle Scholar
Rösler, U. (1991). A limit theorem for “Quicksort”. RAIRO Inform. Théor. Appl. 25, 85–100.CrossRefGoogle Scholar
Rösler, U. (2001). On the analysis of stochastic divide and conquer algorithms. Algorithmica 29, 238–261.Google Scholar
Rösler, U. and Rüschendorf, L. (2001). The contraction method for recursive algorithms. Algorithmica 29, 3–33.Google Scholar
Smythe, R. T. and Mahmoud, H. M. (1995). A survey of recursive trees. Theory Prob. Math. Statist. 51, 1–27.Google Scholar
Van der Hofstad, R., Hooghiemstra, G. and Van Mieghem, P. (2002). On the covariance of the level sizes in random recursive trees. Random Structures Algorithms 20, 519–539.Google Scholar