This morning, I submitted the final version of my paper Discrete minimax estimation with trees (Devroye and Reddad, 2019), which is to appear in the Electronic Journal of Statistics. I think this paper is conceptually quite interesting, and I’m very happy with the final result, so in this post I’ll describe some of the main ideas present in the work.

When programmers hear the phrase “random tree,” they most likely think of a random binary search tree, i.e., a binary search tree built from the insertion of a uniformly random permutation of \(n\) keys—denote such a tree by \(\mathrm{BST}_n\). A mathematician might instead think that a ``random tree’’ is more likely to be a uniformly random tree taken from some class, like the set of all ordered binary trees with \(n\) nodes—denote such a tree by \(\mathrm{UNIF}_n\). Of course, neither would be wrong. It should be clear, though, that these two distributions on the space of binary trees are quite different. In particular, most undergraduate students of computer science learn, through the study of comparison-based sorting algorithms, that \[ \mathbf{E}\{\mathrm{height}(\mathrm{BST}_n)\} = \varTheta(\log n) , \] and some will learn that \[ \mathbf{E}\{\mathrm{height}(\mathrm{UNIF}_n)\} = \varTheta(\sqrt{n}) . \] Though random binary search trees might seem more immediately relevant to programmers, uniformly random binary trees are part of a bigger picture which is comparatively more versatile in the probabilistic analysis of algorithms. To this end, we introduce the concept of Galton-Watson trees.