Hostname: page-component-586b7cd67f-t8hqh Total loading time: 0 Render date: 2024-11-26T23:52:40.902Z Has data issue: false hasContentIssue false
  • English
  • Français

Central Limit Theorems for Additive Tree Parameters with Small Toll Functions

Published online by Cambridge University Press:  08 September 2014

STEPHAN WAGNER
STEPHAN WAGNER*
Affiliation:
Department of Mathematical Sciences, Stellenbosch University, 7602 Stellenbosch, South Africa (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

We call a tree parameter additive if it can be determined recursively as the sum of the parameter values of all branches, plus a certain toll function. In this paper, we prove central limit theorems for very general toll functions, provided that they are bounded and small on average. Simply generated families of trees are considered as well as Pólya trees, recursive trees and binary search trees, and the results are illustrated by several examples of parameters for which we prove normal or log-normal limit laws.

Keywords

Primary 60C05Secondary 05A1605C0505C8060F05
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 24 , Special Issue 1: Honouring the Memory of Philippe Flajolet - Part 3 , January 2015 , pp. 329 - 353
Copyright
Copyright © Cambridge University Press 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Aldous, D. (1991) Asymptotic fringe distributions for general families of random trees. Ann. Appl. Probab. 1 228–266.Google Scholar
[2] Baron, G. and Drmota, M. (1993) Distribution properties of induced subgraphs of trees. Ars Combin. 35 193–213.Google Scholar
[3] Bergeron, F., Flajolet, P. and Salvy, B. (1992) Varieties of increasing trees. In CAAP'92: Rennes 1992, Vol. 581 of Lecture Notes in Computer Science, Springer, pp. 24–48.CrossRefGoogle Scholar
[4] Devroye, L. (1991) Limit laws for local counters in random binary search trees. Random Struct. Alg. 2 303–315.CrossRefGoogle Scholar
[5] Devroye, L. (2002/2003) Limit laws for sums of functions of subtrees of random binary search trees. SIAM J. Comput. 32 152–171.Google Scholar
[6] Dobrow, R. P. and Fill, J. A. (1999) Total path length for random recursive trees. Combin. Probab. Comput. 8 317–333.CrossRefGoogle Scholar
[7] Drmota, M. (2009) Random Trees, Springer.Google Scholar
[8] Drmota, M. and Gittenberger, B. (1999) The distribution of nodes of given degree in random trees. J. Graph Theory 31 227–253.Google Scholar
[9] Drmota, M. and Gittenberger, B. (2010) The shape of unlabeled rooted random trees. Europ. J. Combin. 31 2028–2063.Google Scholar
[10] 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
[11] Fill, J. A. (1996) On the distribution of binary search trees under the random permutation model. Random Struct. Alg. 8 1–25.Google Scholar
[12] Fill, J. A., Flajolet, P. and Kapur, N. (2005) Singularity analysis, Hadamard products, and tree recurrences. J. Comput. Appl. Math. 174 271–313.Google Scholar
[13] Fill, J. A. and Kapur, N. (2004) Limiting distributions for additive functionals on Catalan trees. Theoret. Comput. Sci. 326 69–102.Google Scholar
[14] Flajolet, P., Gourdon, X. and Marténez, C. (1997) Patterns in random binary search trees. Random Struct. Alg. 11 223–244.3.0.CO;2-2>CrossRefGoogle Scholar
[15] Flajolet, P. and Sedgewick, R. (2009) Analytic Combinatorics, Cambridge University Press.Google Scholar
[16] Fuchs, M. (2012) Limit theorems for subtree size profiles of increasing trees. Combin. Probab. Comput. 21 412–441.Google Scholar
[17] Harary, F. and Palmer, E. M. (1973) Graphical Enumeration, Academic Press.Google Scholar
[18] Hwang, H.-K. (1998) On convergence rates in the central limit theorems for combinatorial structures. Europ. J. Combin. 19 329–343.Google Scholar
[19] Hwang, H.-K. and Neininger, R. (2002) Phase change of limit laws in the Quicksort recurrence under varying toll functions. SIAM J. Comput. 31 1687–1722.Google Scholar
[20] Jamison, R. E. (1983) On the average number of nodes in a subtree of a tree. J. Combin. Theory Ser. B 35 207–223.Google Scholar
[21] Janson, S. (2003) The Wiener index of simply generated random trees. Random Struct. Alg. 22 337–358.Google Scholar
[22] Janson, S. (2005) Asymptotic degree distribution in random recursive trees. Random Struct. Alg. 26 69–83.Google Scholar
[23] Klazar, M. (1997) Twelve countings with rooted plane trees. Europ. J. Combin. 18 195–210.CrossRefGoogle Scholar
[24] Klazar, M. (1997) Addendum: ‘Twelve countings with rooted plane trees’. Europ. J. Combin. 18 739–740.Google Scholar
[25] Mahmoud, H. M. (1991) Limiting distributions for path lengths in recursive trees. Probab. Engrg Inform. Sci. 5 53–59.Google Scholar
[26] Meir, A. and Moon, J. W. (1978) On the altitude of nodes in random trees. Canad. J. Math. 30 997–1015.Google Scholar
[27] Meir, A. and Moon, J. W. (1983) On subtrees of certain families of rooted trees. Ars Combin. 16 305–318.Google Scholar
[28] Meir, A. and Moon, J. W. (1998) On the log-product of the subtree-sizes of random trees. Random Struct. Alg. 12 197–212.Google Scholar
[29] Meir, A. and Moon, J. W. (2002) On centroid branches of trees from certain families. Discrete Math. 250 153–170.Google Scholar
[30] Moon, J. W. (1985) On the expected distance from the centroid of a tree. Ars Combin. 20 (A) 263–276.Google Scholar
[31] Moon, J. W. (1997) On the number of induced subgraphs of trees. Discrete Math. 167/168 487–496.CrossRefGoogle Scholar
[32] Otter, R. (1948) The number of trees. Ann. of Math. (2) 49 583–599.CrossRefGoogle Scholar
[33] Robinson, R. W. and Schwenk, A. J. (1975) The distribution of degrees in a large random tree. Discrete Math. 12 359–372.Google Scholar
[34] Takács, L. (1991) Conditional limit theorems for branching processes. J. Appl. Math. Stochastic Anal. 4 263–292.Google Scholar
[35] Takács, L. (1992) On the total heights of random rooted trees. J. Appl. Probab. 29 543–556.Google Scholar
[36] Vince, A. and Wang, H. (2010) The average order of a subtree of a tree. J. Combin. Theory Ser. B 100 161–170.Google Scholar
[37] Wagner, S. (2012) Additive tree functionals with small toll functions and subtrees of random trees. In 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms: AofA'12, DMTCS Proc. AQ, pp. 67–80.Google Scholar