Probabilistic analysis of bucket recursive trees

AbstractWe introduce the bucket recursive tree, a generalization of recursive trees. The tree grows from a succession of integer labels that join the multitype nodes of the tree according to a stochastic rule. We study the multivariate structure of the tree and obtain a multivariate central limit theorem for the joint distribution of the number of nodes of different types for trees with bucket size b ⩽ 26. For trees with b > 26 a phase change in the distribution is detected and the central limit theorem does not hold. Recent results on the extended Pólya urn models (Smythe, 1995) provide the basic tool to reach these results. Two kinds of distances are also studied: The tree height and the depth of the nth label. Strong laws for the height are obtained via a technique based on introducing “ghost nodes”, then removing them. The ghost nodes create a companion tree that relates our tree to Biggins' (1976) first- and last-birth problem in a multitype process. A weak law for the depth is obtained by formulating and asymptotically manipulating the depth probability generating function