THE HEIGHT OF MALLOWS TREES
成果类型：
Article
署名作者：
Addario-Berry, Louigi; Corsini, Benoit
署名单位：
McGill University
刊物名称：
ANNALS OF PROBABILITY
ISSN/ISSBN：
0091-1798
DOI：
10.1214/20-AOP1503
发表日期：
2021
页码：
2220-2271
关键词：
摘要：
Random binary search trees are obtained by recursively inserting the elements sigma(1), sigma(2),..., sigma(n) of a uniformly random permutation s of [n] = {1,..., n} into a binary search tree data structure. Devroye (J. Assoc. Comput. Mach. 33 (1986) 489-498) proved that the height of such trees is asymptotically of order c* log n, where c* = 4.311... is the unique solution of c log((2e)/c) = 1 with c >= 2. In this paper, we study the structure of binary search trees T-n,T- q built from Mallows permutations. A Mallows(q) permutation is a random permutation of [n] = {1,..., n} whose probability is proportional to q(Inv(sigma)), where Inv(sigma) = vertical bar{i < j : sigma(i) > sigma(j)}vertical bar. This model generalizes random binary search trees, since Mallows(q) permutations with q = 1 are uniformly distributed. The laws of T-n,T- q and T-n,T- 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 <= 1. We show that, for q is an element of [0, 1], the height of T-n,T- q is asymptotically (1 + o(1))(c * log n + n(1 - q)) in probability. This yields three regimes of behaviour for the height of Tn, 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 Tn, q is asymptotically of order c* 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,T- q.