Hostname: page-component-586b7cd67f-vdxz6 Total loading time: 0 Render date: 2024-11-24T22:37:07.109Z Has data issue: false hasContentIssue false
  • English
  • Français

Gibbs' Measures on Combinatorial Objects and the Central Limit Theorem for an Exponential Family of Random Trees

Published online by Cambridge University Press:  27 July 2009

Michael Steele
Michael Steele
Affiliation:
Program in Engineering Statistics Princeton University Princeton, New Jersey
Get access Rights & Permissions [Opens in a new window]

Abstract

A model for random trees is given which provides an embedding of the uniform model into an exponential family whose natural parameter is the expected number of leaves. The model is proved to be analytically and computationally tractable. In particular, a central limit theorem (CLT) for the number of leaves of a random tree is given which extends and sharpens Rényi's CLT for the uniform model. The method used is general and is shown to provide tractable exponential families for a variety of combinatorial objects.

Type
Articles
Information
Probability in the Engineering and Informational Sciences , Volume 1 , Issue 1 , January 1987 , pp. 47 - 59
Copyright
Copyright © Cambridge University Press 1987

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

Aldous, D. (1986). On the Markov chain simulation method for uniform combinatorial distributions and simulated annealing. Technical Report No. 60, Department of Statistics, University of California, Berkeley, California.Google Scholar
Bender, E. A. (1973). Central and local limit theorems applied to asymptotic enumeration. J. Combinatorial Theory A 15: 91–111.CrossRefGoogle Scholar
Cayley, A. (1889). A theorem on trees. Quarterly Journal of Pure and Applied Mathematics 23: 376–378.Google Scholar
Canfield, E. R. (1980). Application of the Berry–Essen inequality to combinatorial estimates. J. Combinatorial Theory A 28: 17–25.CrossRefGoogle Scholar
Feller, W. (1971). An Introduction to Probability Theory and its Applications, Vol. II, Second Edition, Wiley, New York, p. 544.Google Scholar
Godsil, C. D. (1981a). Hermite polynomials and a duality relation for matching polynomials. Combinatorica 1: 257–262.CrossRefGoogle Scholar
Godsil, C. D. (1981b). Matching behavior is asymptotically normal. Combinatorica 1: 369–376.CrossRefGoogle Scholar
Godsil, C. D. and Gutman, I. (1981). On the theory of matching polynomials. J. Graph Theory 5: 137–144.CrossRefGoogle Scholar
Harper, L. H. (1967). Stirling behavior is asymptotically normal. Ann. Math. Statis. 38: 410–414.CrossRefGoogle Scholar
Heilmann, O. J. and Lieb, E. H. (1972). The theory of monomer-dimer systems. Comm. Math. Phys. 22: 190–232.CrossRefGoogle Scholar
Kilpatrick, S., Gelatt, C., and Vecchi, M. (1983). Optimization by simulated annealing. Science 220: 671–680.CrossRefGoogle Scholar
Knuth, D. (1968). Another enumeration of trees. Canadian J. of Math. 20: 1077–1086.CrossRefGoogle Scholar
Lovász, L. (1979). Combinatorial Problems and Exercises, North-Holland, Amsterdam, The Netherlands, p. 29.Google Scholar
Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., and Teller, E. (1953). Equations of state calculation by fast computing machines. J. Chem. Physics 21: 1087–1092.CrossRefGoogle Scholar
Moon, J. W. (1970). Counting Labeled Trees Canadian Mathematical Monographs, No. 1, Alberta, Canada, p. 5.Google Scholar
Nijenhuis, A. and Wilf, H. (1978). Combinatorial Algorithms, Academic Press, New York, p. 35–39.Google Scholar
Petrov, V. V. (1975). Sums of Independent Random Variables, Springer-Verlag, New York, p. 111.Google Scholar
Pólya, G. and Szegö, G. (1976). Problems and Theorems in Analysis II, Springer-Verlag, New York, p. 45.CrossRefGoogle Scholar
Prüfer, A. (1918). Neuer Beweis eines Satzes uber Permutationen. Archly für Mathematik und Physik 27: 142–144.Google Scholar
Rényi, A. (1959). Some remarks on the theory of trees. MTA Mat. Kut. Int. Kozl. 4: 73–85.Google Scholar