Cycles in Mallows random permutations

DOI10.1002/RSA.21169MaRDI QIDQ6063350zbMATH OpenOpenAlexFDO

Authors Jimmy He, Tobias Müller

Publication date 7 November 2023

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

cycle countsMallows distributionrandom permutations

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial probability (60C05) Central limit and other weak theorems (60F05)

Abstract: We study cycle counts in permutations of $1,dots,n$ drawn at random according to the Mallows distribution. Under this distribution, each permutation $piin{S}_n$ is selected with probability proportional to $q^{extinv(pi)}$, where $q>0$ is a parameter and $extinv(pi)$ denotes the number of inversions of $pi$. For $ell$ fixed, we study the vector $(C_1(P{i}_n),dots,C_{e}ll(P{i}_n))$ where $C_i(pi)$ denotes the number of cycles of length $i$ in $pi$ and $P{i}_n$ is sampled according to the Mallows distribution. Here we show that if $0<q<1$ is fixed and $noinfty$ then there are positive constants $m_i$ such that each $C_i(P{i}_n)$ has mean $(1+o(1))cdot{m}_{i}cdotn$ and the vector of cycle counts can be suitably rescaled to tend to a joint Gaussian distribution. Our results also show that when $q>1$ there is striking difference between the behaviour of the even and the odd cycles. The even cycle counts still have linear means, and when properly rescaled tend to a multivariate Gaussian distribution. For the odd cycle counts on the other hand, the limiting behaviour depends on the parity of $n$ when $q>1$. Both $(C_1(P{i}_{2n}),C_3(P{i}_{2n}),dots)$ and $(C_1(P{i}_{2n+1}),C_3(P{i}_{2n+1}),dots)$ have discrete limiting distributions -- they do not need to be renormalized -- but the two limiting distributions are distinct for all $q>1$. We describe these limiting distributions in terms of Gnedin and Olshanski's bi-infinite extension of the Mallows model. We also investigate these limiting distributions, and study the behaviour of the constants involved in the Gaussian limit laws. We for example show that as $qdownarrow1$ the expected number of 1-cycles tends to $1/2$ -- which, curiously, differs from the value corresponding to $q=1$. In addition we exhibit an interesting "oscillating" behaviour in the limiting probability measures for $q>1$ and $n$ odd versus $n$ even.

Recommendations

• scientific article; zbMATH DE number 3844715
• On the cycle structure of Mallows permutations
• The cycle structure of random permutations
• On the number of cycles in a random permutation
• Cycle structure of random permutations with cycle weights
• scientific article; zbMATH DE number 1808170

Cites work

• q-exchangeability via quasi-invariance
• A problem of the Allocation of Particles in Cells and Cycles of Random Permutations
• Analysis of systematic scan Metropolis algorithms using Iwahori-Hecke algebra techniques
• Arcsine laws for random walks generated from random permutations with applications to genomics
• scientific article; zbMATH DE number 6016068 (Why is no real title available?)
• scientific article; zbMATH DE number 3840948 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 2117212 (Why is no real title available?)
• scientific article; zbMATH DE number 765034 (Why is no real title available?)
• scientific article; zbMATH DE number 3104489 (Why is no real title available?)
• Lengths of monotone subsequences in a Mallows permutation
• Limit theorems for longest monotone subsequences in random Mallows permutations
• Mallows permutations and finite dependence
• Mallows permutations as stable matchings
• 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
• On adding a list of numbers (and other one-dependent determinantal processes)
• On the cycle structure of Mallows permutations
• Pattern avoidance for random permutations
• Permutations avoiding a pattern of length three under Mallows distributions
• Phase uniqueness for the Mallows measure on permutations
• Regenerative random permutations of integers
• Stochastic processes. Theory for applications.
• The height of Mallows trees
• The length of the longest common subsequence of two independent Mallows permutations
• The length of the longest increasing subsequence of a random Mallows permutation
• The probability of avoiding consecutive patterns in the Mallows distribution
• The two-sided infinite extension of the Mallows model for random permutations
• Thermodynamic limit for the Mallows model on S_n

Cited in

(17)

• On the cycle structure of Mallows permutations
• Clustering of consecutive numbers in permutations under Mallows distributions and super-clustering under general \(p\)-shifted distributions
• A central limit theorem for descents of a Mallows permutation and its inverse
• Lengths of monotone subsequences in a Mallows permutation
• \(G\) method in action: fast exact sampling from set of permutations of order \(n\) according to Mallows model through Cayley metric
• The Mallows measures on the hyperoctahedral group
• Regenerative random permutations of integers
• Fixed points and cycle structure of random permutations
• The two-sided infinite extension of the Mallows model for random permutations
• Phase uniqueness for the Mallows measure on permutations
• The probability of avoiding consecutive patterns in the Mallows distribution
• Limits of Mallows trees
• Classical patterns in Mallows permutations
• Logical limit laws for Mallows random permutations
• The global and local limit of the continuous-time Mallows process
• Boundary statistics for the six-vertex model with DWBC
• Heights of butterfly trees

This page was built for publication: Cycles in Mallows random permutations

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