No CrossRef data available.
Article contents
Central Limit Theorems for Additive Tree Parameters with Small Toll Functions
Published online by Cambridge University Press: 08 September 2014
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 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.
Information
- 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
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
[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
[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
[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
You have
Access
- 19
- Cited by