The height of Mallows trees

DOI10.1214/20-AOP1503zbMath1479.05050arXiv2007.13728OpenAlexW3202988040MaRDI QIDQ2057202

Louigi Addario-Berry, Benoît Corsini

Publication date: 8 December 2021

Published in: The Annals of Probability (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2007.13728

zbMATH Keywords

random treesbinary search treesrandom permutationsMallows permutationsheights of treesMallows trees

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Permutations, words, matrices (05A05) Strong limit theorems (60F15) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Combinatorial probability (60C05) Probability measures on groups or semigroups, Fourier transforms, factorization (60B15)

Related Items (3)

Differential privacy in constant function market makers ⋮ Cycles in Mallows random permutations ⋮ The height of record‐biased trees

Cites Work

• Fixed points and cycle structure of random permutations
• The length of the longest increasing subsequence of a random Mallows permutation
• Convergence in law of the minimum of a branching random walk
• The two-sided infinite extension of the Mallows model for random permutations
• Trickle-down processes and their boundaries
• Branching random walks. École d'Été de Probabilités de Saint-Flour XLII -- 2012
• \(q\)-exchangeability via quasi-invariance
• Martingales and profile of binary search trees
• On growing random binary trees
• Postulates for subadditive processes
• The first birth problem for an age-dependent branching process
• Limit theorems for longest monotone subsequences in random Mallows permutations
• On the cycle structure of Mallows permutations
• Minima in branching random walks
• Lengths of monotone subsequences in a Mallows permutation
• Some Probabilistic Aspects of Set Partitions
• NON-NULL RANKING MODELS. I
• The height of a random binary search tree
• An analytic approach to the height of binary search trees II
• Thermodynamic limit for the Mallows model on Sn
• A note on the height of binary search trees
• Newton's Identities
• The first- and last-birth problems for a multitype age-dependent branching process
• Probability
• Phase uniqueness for the Mallows measure on permutations
• Mixing times of the biased card shuffling and the asymmetric exclusion process
• The probability of avoiding consecutive patterns in the Mallows distribution
• The height of increasing trees
• The height of increasing trees
• Analysis of systematic scan Metropolis algorithms using Iwahori-Hecke algebra techniques

This page was built for publication: The height of Mallows trees