Premium
Asymptotic degree distribution in random recursive trees
Author(s) -
Janson Svante
Publication year - 2004
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20046
Subject(s) - mathematics , combinatorics , mathematical proof , asymptotic distribution , vertex (graph theory) , limit (mathematics) , random graph , discrete mathematics , type (biology) , distribution (mathematics) , degree (music) , graph , statistics , mathematical analysis , ecology , physics , geometry , estimator , acoustics , biology
The distributions of vertex degrees in random recursive trees and random plane recursive trees are shown to be asymptotically normal. Formulas are given for the asymptotic variances and covariances of the number of vertices with given outdegrees. We also give functional limit theorems for the evolution as vertices are added. The proofs use some old and new results about generalized Pólya urn models. We consider generalized Pólya urns with infinitely many types, but reduce them to the finite type case. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2005