Uniform recursive trees: Branching structure and simple random downward walk ✩

As models for spread of epidemics, family trees, etc., various authors have used a random tree called the uniform recursive tree. Its branching structure and the length of simple random downward walk (SRDW) on it are investigated in this paper. On the uniform recursive tree of size n, we first give the distribution law of ζn,m, the number of m-branches, whose asymptotic distribution is the Poisson distribution with parameter λ = 1 m. We also give the joint distribution of the numbers of various branches and their covariance matrix. On Ln, the walk length of SRDW, we first give the exact expression of P(Ln = 2). Finally, the asymptotic behavior of Ln is given.  2005 Elsevier Inc. All rights reserved