Limits of descent-biased trees
Abstract
We investigate scaling and local limits of random trees biased according to their number of descents. A descent in a rooted labeled tree t is a parent-child pair such that the label of the parent is greater than the label of the child, and the total number of descents is denoted by des(t). For n ≥ 1 and qn ≥ 0, we consider the probability measure on trees of size n where each tree t is chosen with a probability proportional to qndes(t). We study the resulting random tree 𝒯n(qn) properly rescaled as n → ∞, and focus on two regimes for the bias parameter qn. When qn = q ∈ (0,1] is fixed, we prove that 𝒯n(q) converges in distribution to the Brownian Continuum Random Tree. When qn = a/n for some fixed a > 0, we prove that 𝒯n(qn) converges in distribution to a random non-trivial dendron constructed from a Poisson-Dirichlet sequence. We complement these results with a description of the Benjamini-Schramm local limit of 𝒯n(qn) in all regimes of parameters. Our proofs rely on analytic combinatorics to find the asymptotics of certain statistics of the tree, and on a probabilistic analysis of the structure of descent-biased random trees.
Related
- Total Path Length in Power-Weight Recursive Trees: Martingale Limits and Global Fluctuations
- Biased random walk on a locally infinite Galton-Watson tree
- Asymptotic Analysis of the Biased van der Pol Equation
- An Island-Based Parallel Biased Random-Key Genetic Algorithm for the Three-Dimensional Trailer Loading Problem
- Towards Optimal Inventory Control under Censored Demand: A Biased Sample-Average Approximation Approach
BibTeX
@misc{dubach2026limits,
title = {{Limits of descent-biased trees}},
author = {Victor Dubach and Paul Thévenin and Stephan Wagner},
howpublished = {HAL},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.15451},
eprint = {2609.15451},
archivePrefix = {arXiv},
url = {https://hal.science/hal-05754228v1},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Limits of descent-biased trees
AU - Victor Dubach
AU - Paul Thévenin
AU - Stephan Wagner
PY - 2026
DA - 2026/09/14
PB - HAL
DO - 10.48550/arxiv.2609.15451
UR - https://hal.science/hal-05754228v1
AB - We investigate scaling and local limits of random trees biased according to their number of descents. A descent in a rooted labeled tree t is a parent-child pair such that the label of the parent is greater than the label of the child, and the total number of descents is denoted by des(t). For n ≥ 1 and q_n ≥ 0, we consider the probability measure on trees of size n where each tree t is chosen with a probability proportional to q_n^des(t). We study the resulting random tree 𝒯_n^(q_n) properly rescaled as n → ∞, and focus on two regimes for the bias parameter q_n. When q_n = q ∈ (0,1] is fixed, we prove that 𝒯_n^(q) converges in distribution to the Brownian Continuum Random Tree. When q_n = a/n for some fixed a > 0, we prove that 𝒯_n^(q_n) converges in distribution to a random non-trivial dendron constructed from a Poisson-Dirichlet sequence. We complement these results with a description of the Benjamini-Schramm local limit of 𝒯_n^(q_n) in all regimes of parameters. Our proofs rely on analytic combinatorics to find the asymptotics of certain statistics of the tree, and on a probabilistic analysis of the structure of descent-biased random trees.
ER -