On the cycle structure of Mallows permutations

DOI10.1214/17-AOP1202zbMATH Open1430.60015arXiv1601.06991OpenAlexW2963697835WikidataQ130185189 ScholiaQ130185189MaRDI QIDQ1746151FDOQ1746151

Authors: Alexey Gladkich, Ron Peled 

Publication date: 24 April 2018

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

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.

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

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

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)

Cites Work

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

Cited In (24)

• Thermodynamic limit for the Mallows model on \(S_n\)
• 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
• Finite Automata, Probabilistic Method, and Occurrence Enumeration of a Pattern in Words and Permutations
• 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
• Ewens Sampling and Invariable Generation
• 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
• 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
• Mallows permutations as stable matchings
• Clustering of consecutive numbers in permutations under Mallows distributions and super-clustering under general \(p\)-shifted distributions

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)