On the cycle structure of Mallows permutations

DOI10.1214/17-AOP1202MaRDI QIDQ1746151zbMATH OpenOpenAlexWikidataFDO

Authors Alexey Gladkich, Ron Peled

Publication date 24 April 2018

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

Full work available at URL https://arxiv.org/abs/1601.06991, https://projecteuclid.org/euclid.aop/1520586277

zbMATH Keywords

phase transitionlocalizationcycle structuredelocalizationrandom band matricesPoisson-Dirichlet lawMallows permutationsmacroscopic cycles

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Random matrices (probabilistic aspects) (60B20) Central limit and other weak theorems (60F05) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Combinatorial probability (60C05) Exactly solvable models; Bethe ansatz (82B23) Phase transitions (general) in equilibrium statistical mechanics (82B26)

Abstract: We study the length of cycles of random permutations drawn from the Mallows distribution. Under this distribution, the probability of a permutation $piinmathbb{S}_n$ is proportional to $q^{extrminv(pi)}$ where $0<qle1$ and $extrminv(pi)$ is the number of inversions in $pi$. We show that the expected length of the cycle containing a given point is of order $min(1-q{)}^{-2},n$. This marks the existence of two asymptotic regimes: with high probability, when $n$ tends to infinity with $(1-q{)}^{-2}lln$ then all cycles have size $o(n)$ whereas when $n$ tends to infinity with $(1-q{)}^{-2}ggn$ then macroscopic cycles, of size proportional to $n$, emerge. In the second regime, we prove that the distribution of normalized cycle lengths follows the Poisson-Dirichlet law, as in a uniformly random permutation. The results bear formal similarity with a conjectured localization transition for random band matrices. Further results are presented for the variance of the cycle lengths, the expected diameter of cycles and the expected number of cycles. The proofs rely on the exact sampling algorithm for the Mallows distribution and make use of a special diagonal exposure process for the graph of the permutation.

Recommendations

• Cycles in Mallows random permutations
• A central limit theorem for descents of a Mallows permutation and its inverse
• Lengths of monotone subsequences in a Mallows permutation
• Fixed points and cycle structure of random permutations
• The length of the longest increasing subsequence of a random Mallows permutation

Cites work

• scientific article; zbMATH DE number 5994989 (Why is no real title available?)
• scientific article; zbMATH DE number 6016068 (Why is no real title available?)
• scientific article; zbMATH DE number 2046051 (Why is no real title available?)
• Analysis of systematic scan Metropolis algorithms using Iwahori-Hecke algebra techniques
• Compositions of random transpositions
• Emergence of giant cycles and slowdown transition in random transpositions and \(k\)-cycles
• Fixed points and cycle structure of random permutations
• Generating a random permutation with random transpositions
• Improved lower bound on thermodynamic pressure of the spin 1/2 Heisenberg ferromagnet
• Infinite cycles in the random stirring model on trees
• Lengths of monotone subsequences in a Mallows permutation
• Limit theorems for longest monotone subsequences in random Mallows permutations
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Mixing times of the biased card shuffling and the asymmetric exclusion process
• NON-NULL RANKING MODELS. I
• Noisy sorting without resampling
• On adding a list of numbers (and other one-dependent determinantal processes)
• Percolation transition in the Bose gas: II
• Permutations with fixed pattern densities
• Phase uniqueness for the Mallows measure on permutations
• Random permutations and related topics
• Sharp phase transition in the random stirring model on trees
• Spatial random permutations and Poisson-Dirichlet law of cycle lengths
• The Poisson-Dirichlet distribution and related topics. Models and asymptotic behaviors
• The length of the longest increasing subsequence of a random Mallows permutation
• The random interchange process on the hypercube
• The sampling theory of selectively neutral alleles
• The two-sided infinite extension of the Mallows model for random permutations
• Thermodynamic limit for the Mallows model on \(S_n\)
• q-exchangeability via quasi-invariance

Cited in

(28)

• Thermodynamic limit for the Mallows model on \(S_n\)
• Lengths of monotone subsequences in a Mallows permutation
• A view from the bridge spanning combinatorics and probability
• Arcsine laws for random walks generated from random permutations with applications to genomics
• Strongly correlated random interacting processes. Abstracts from the workshop held January 28 -- February 3, 2018
• Regenerative random permutations of integers
• Poisson percolation on the square lattice
• Limit theorems for longest monotone subsequences in random Mallows permutations
• Double coset Markov chains
• A central limit theorem for descents of a Mallows permutation and its inverse
• Comparing the inversion statistic for distribution-biased and distribution-shifted permutations with the geometric and the GEM distributions
• Phase uniqueness for the Mallows measure on permutations
• Limits of Mallows trees
• Cycles in Mallows random permutations
• Existence of a phase transition of the interchange process on the Hamming graph
• Statistical enumeration of groups by double cosets
• Large deviation principle for random permutations
• Finite automata, probabilistic method, and occurrence enumeration of a pattern in words and permutations
• Critical parameter of random loop model on trees
• The band structure of a model of spatial random permutation
• Quasi-polynomial time approximation schemes for assortment optimization under Mallows-based rankings
• Permutations avoiding a pattern of length three under Mallows distributions
• The height of Mallows trees
• Limit distributions for Euclidean random permutations
• The length of the longest increasing subsequence of a random Mallows permutation
• Mallows permutations as stable matchings
• Clustering of consecutive numbers in permutations under Mallows distributions and super-clustering under general \(p\)-shifted distributions
• Ewens sampling and invariable generation

This page was built for publication: On the cycle structure of Mallows permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1746151)