The degree profile of Pólya trees

Abstract

We investigate the profile of random Pólya trees of size $n$ when only nodes of degree $d$ are counted in each level. It is shown that, as in the case where all nodes contribute to the profile, the suitably normalized profile process converges weakly to a Brownian excursion local time. Moreover, we investigate the joint distribution of the number of nodes of degree $d_1$ and $d_2$ in the levels of the tree.

31 pages, 3 figures

References in corpus (2)

• A functional limit theorem for the profile of search trees
• Width and mode of the profile for some random trees of logarithmic height