The height of Mallows trees

Abstract

Random binary search trees are obtained by recursively inserting the elements $\sigma (1),\sigma (2),\dots ,\sigma (n)$ of a uniformly random permutation $\sigma$ of $[n]=\{1,\dots ,n\}$ into a binary search tree data structure. Devroye (1986) proved that the height of such trees is asymptotically of order $c^{\ast }\log n$, where $c^{\ast }=4.311\dots$ is the unique solution of $c\log ((2e)/c)=1$ with $c\ge 2$. In this paper, we study the structure of binary search trees $T_{n,q}$ built from Mallows permutations. A $\text{Mallows}(q)$ permutation is a random permutation of $[n]=\{1,\dots ,n\}$ whose probability is proportional to $q^{\text{Inv}(\sigma )}$, where $\text{Inv}(\sigma )=\#\{i<j:\sigma (i)>\sigma (j)\}$. This model generalizes random binary search trees, since $\text{Mallows}(q)$ permutations with $q=1$ are uniformly distributed. The laws of $T_{n,q}$ and $T_{n,q^{-1}}$ are related by a simple symmetry (switching the roles of the left and right children), so it suffices to restrict our attention to $q\le 1$. We show that, for $q\in [0,1]$, the height of $T_{n,q}$ is asymptotically $(1+o(1))(c^{\ast }\log n+n(1-q))$ in probability. This yields three regimes of behaviour for the height of $T_{n,q}$, depending on whether $n(1-q)/\log n$ tends to zero, tends to infinity, or remains bounded away from zero and infinity. In particular, when $n(1-q)/\log n$ tends to zero, the height of $T_{n,q}$ is asymptotically of order $c^{\ast }\log n$, like it is for random binary search trees. Finally, when $n(1-q)/\log n$ tends to infinity, we prove stronger tail bounds and distributional limit theorems for the height of $T_{n,q}$.

52 pages