On exponentially height-penalized random trees

Abstract

Given $n\in \mathbb{N}$ and $\hat{I}¼\in \mathbb{R}$, a $\textit{$μ$-height-biasedtreeofsize$n$}$ is a random plane tree ${\mathbf{T}}_n$ with $n$ vertices with law given by $\mathbb{P}(\mathbf{T}=t)\propto e^{-\hat{I}¼h(t)}$, where $t$ ranges over fixed plane trees with $n$ vertices, and $h(t)$ is the height of $t$. Fix a sequence $(\hat{I}{¼}_n{)}_{n\ge 1}$ of real numbers, and for $n\ge 1$ let ${\mathbf{T}}_n$ be a $\hat{I}¼$-height-biased tree of size $n$. Durhuus and Ünel (2023) described the asymptotic behaviour of $h({\mathbf{T}}_n)$ when $\hat{I}{¼}_n\equiv \hat{I}¼\in \mathbb{R}$ is fixed. In this work, we extend their results to arbitrary sequences of positive parameters depending on $n$. Most notably, we show that such a tree behaves like a height-biased Continuum Random Tree (CRT) when $\hat{I}{¼}_n$ is of order $1/\sqrt{n}$; that its height is asymptotically $(2\ddot{I}{€}^{2}n/\hat{I}{¼}_n{)}^{1/3}$ when $\hat{I}{¼}_n$ is of larger order than $1/\sqrt{n}$ and of smaller order than $n$; and that its height converges to a fixed constant when $\hat{I}{¼}_n$ is of order at least $n$, with some random jumps under specific conditions on $\hat{I}{¼}_n$. We additionally prove various results on second order behaviours, and large deviation principles for the height, for different regimes of $\hat{I}{¼}_n$. Finally, we describe new statistics of these trees, covering their widths, their root degrees, and the local structure around their roots.

53 pages, 3 figures