Cycle structure of Mallows permutation model with the \(L^1\) distance

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 \(\beta\). In this paper, we take the distance metric to be th...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2023-12
Main Author: Zhong, Chenyang
Format: Article
Language:English
Subjects:
Algorithms
Dirichlet problem
Markov chains
Mathematical models
Parameters
Permutations
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 \(\beta\). In this paper, we take the distance metric to be the \(L^1\) 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^1\) distance. We focus on the parameter regime where \(\beta>0\). We show that the expected length of the cycle containing a given point is of order \(\min\{\max\{\beta^{-2},1\},n\}\), and the expected diameter of the cycle containing a given point is of order \(\min\{e^{-2\beta}\max\{\beta^{-2},1\}, n-1\}\). Moreover, when \(\beta\ll 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.
ISSN:2331-8422