Scaling limits of random Pólya trees (Q2413245): Difference between revisions

A Galton-Watson tree is a random rooted tree in which the number of children of each node is chosen according to a fixed distribution. A Pólya tree is a random rooted tree in which the number of children of each node is chosen from a fixed set, considered up to symmetry. The distribution of random Galton-Watson trees with finite variance on the child distribution, conditioned to have \(n\) vertices, converges in distribution to the continuum random tree in the natural Gromov-Hausdorff metric [\textit{D. Aldous}, Ann. Probab. 21, No. 1, 248--289 (1993; Zbl 0791.60009)]. There are sub-Gaussian tail bounds for the width and height of such trees [\textit{L. Addario-Berry} et al., ibid. 41, No. 2, 1072--1087 (2013; Zbl 1278.60128)]. The authors use Boltzmann samplers to construct a random Pólya tree on \(n\) vertices, which show that it is essentially a large Galton-Watson tree, with small subtrees of \(O(\log n)\) vertices attached to each vertex. Therefore, the Pólya tree converges in distribution to the continuum random tree, and it has analogous sub-Gaussian tail bounds for the height and width.