Degree distribution in the lower levels of the
uniform recursive tree

Abstract. In this note we consider the \(k\)th level of the uniform random recursive tree after \(n\) steps, and prove that the proportion of nodes with degree greater than \(t\log n\) converges to \((1-t)^k\) almost surely, as \(n\to\infty\), for every \(t\in(0,1)\). In addition, we show that the number of degree \(d\) nodes in the first level is asymptotically Poisson distributed with mean \(1\); moreover, they are asymptotically independent for \(d=1,2,\dots\).

Key words and phrases. Random recursive tree, permutation, degree distribution, Poisson distribution, method of moments.