Cycle structure of Mallows permutation model with the L¹ distance

2023/12/26 by Chenyang Zhong, Zhong, Chenyang · 1 citation
Computer Science · Mathematics · #Advanced Statistical Methods and Models #Bayesian Methods and Mixture Models #Census and Population Estimation #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.2312.15833

openalex publication_date 2023/12/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Introduced by Mallows as a ranking model in statistics, Mallows permutation model is a class of non-uniform probability distributions on the symmetric group S_n. The model depends on a distance metric on S_n and a scale parameter β. In this paper, we take the distance metric to be the L¹ distance (also known as Spearman's footrule in the statistics literature), and investigate the cycle structure of random permutations drawn from Mallows permutation model with the L¹ distance. We focus on the parameter regime where β>0. We show that the expected length of the cycle containing a given point is of order min\max\β^-2,1\,n\, and the expected diameter of the cycle containing a given point is of order min\e^-2βmax\β^-2,1\, n-1\. Moreover, when β≪ n^{-1\slash 2}, the sorted cycle lengths (in descending order) normalized by n converge in distribution to the Poisson-Dirichlet law with parameter 1. The proofs of the results rely on the hit and run algorithm, a Markov chain for sampling from the model.

Cited by

• Heights of butterfly trees

Related

• The length of the longest increasing subsequence of Mallows permutation models with L¹ and L² distances
• Mallows permutation models with L¹ and L² distances I: hit and run algorithms and mixing times
• On the Cycle Structure of Mallows Permutations
• Optimal Learning of Mallows Block Model
• Cycles in Mallows random permutations