×

A family of random trees with random edge lengths. (English) Zbl 0934.05117

The authors consider random trees with edge lengths. The underlying trees have \(n\) labeled vertices and, possibly, additional unlabeled vertices of degree 3. A probability distribution on the space of these trees is defined in terms of an arbitrary sequence of \(n\) nonnegative constants. Explicit formulas are derived for the distribution of quantities associated with these trees such as degree sequence and total edge length, among other things.

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C05 Trees
05C30 Enumeration in graph theory
60C05 Combinatorial probability
05C07 Vertex degrees
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] and Handbook of Mathematical Functions, Dover, New York, 1965.
[2] Aldous, Ann Probab 21 pp 248– (1993) · Zbl 0791.60009 · doi:10.1214/aop/1176989404
[3] and Inhomogeneous continuum random trees and the entrance boundary of the additive coalescent, Technical Report 525, Dept. Statistics, U.C. Berkeley, 1998. To appear in PTRF. Available via homepage .
[4] Aldous, Ann Probab 26 pp 1703– (1998) · Zbl 0936.60064 · doi:10.1214/aop/1022855879
[5] and Random Generation of Trees, Kluwer, Dordrecht, 1995. · doi:10.1007/978-1-4757-6353-9
[6] and Limit distributions and random trees derived from the birthday problem with unequal probabilities. Technical Report 523, Dept. Statistics, U.C. Berkeley, 1998. To appear in Electronic J Probab. Available via .
[7] Cayley, Quarterly J Pure Appl Math 23 pp 376– (1889)
[8] Durrett, J Theoret Probab 4 pp 223– (1991) · Zbl 0718.60099 · doi:10.1007/BF01047004
[9] Gilbert, SIAM J Appl Math. 16 pp 1– (1968) · Zbl 0159.22001 · doi:10.1137/0116001
[10] and The Steiner Tree Problem, Vol. 53 of Annals of Discrete Mathematics, North Holland, Amsterdam, 1992.
[11] The Art of Computer Programming, Addison-Wesley, Reading, MA, 1968, Vol. 1.
[12] Maddison, Evolution 45 pp 1184– (1991) · doi:10.1111/j.1558-5646.1991.tb04385.x
[13] Evolution of Random Search Trees, Wiley, New York, 1992. · Zbl 0762.68033
[14] Counting Labelled Trees, Canadian Mathematical Congress, 1970, Canadian Mathematical Monographs No. 1.
[15] Pitman, Probab Theory Relat Fields 102 pp 145– (1995) · Zbl 0821.60047 · doi:10.1007/BF01213386
[16] Abel-Cayley-Hurwitz multinomial expansions associated with random mappings, forests and subsets, Technical Report 498, Dept. Statistics, U.C. Berkeley, 1997. Available via .
[17] Pitman, Bernoulli 3 pp 79– (1997) · Zbl 0882.60081 · doi:10.2307/3318653
[18] The asymptotic behavior of the Hurwitz binomial distribution, Technical Report 500, Dept. Statistics, U.C. Berkeley, 1997. Available via . To appear in Combinatorics, Probab, Computing.
[19] The multinomial distribution on rooted labeled forests, Technical Report 499, Dept. Statistics, U.C. Berkeley, 1997. Available via .
[20] Pitman, J Comb Theory A 85 pp 165– (1999) · Zbl 0918.05042 · doi:10.1006/jcta.1998.2919
[21] ?On the enumeration of trees,? in and (Editors), Combinatorial Structures and their Applications. Gordon and Breach, New York, 1970, pp. 355-360.
[22] Probability Theory and Combinatorial Optimization, Number 69 in CBMS-NSF Regional Conference Series in Applied Math SIAM, 1997.
[23] Tavaré, Theoret Population Biol 26 pp 119– (1984) · Zbl 0555.92011 · doi:10.1016/0040-5809(84)90027-3
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.