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 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\text{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.