Quantitative limit theorems for generalized P\'olya urns with applications to random tree models

We establish novel quantitative limit theorems for the asymptotic distribution of colours in a generalized Pólya urn.

Concretely, we construct explicit rates of convergence for the proportion of balls of each colour in the urn, both in square-mean and almost surely, under a general condition on the replacement matrix.

As an application, we revisit three models of random recursive trees studied by Janson (Random Structures & Algorithms 26 (2005), 69--83): random recursive trees, random plane recursive trees, and random recursive $d$-ary trees.

For each model, we show that the corresponding outdegree statistics can be cast as generalized Pólya urns, and thereby obtain explicit rates of convergence, both in $L^2$ and almost surely, for the proportion of nodes of each outdegree.

In all three cases, the rates we obtain are of order $O(1/n)$ in $L^2$ and almost surely, and are uniform in the outdegree under consideration.