Can I read Mallows permutation models with $L^1$ and $L^2$ distances I: hit and run algorithms and mixing times on EtoBox?

Mallows permutation models with $L^1$ and $L^2$ distances I: hit and run algorithms and mixing times by Zhong, Chenyang is a scholarly article available to read on EtoBox.

What is Mallows permutation models with $L^1$ and $L^2$ distances I: hit and run algorithms and mixing times about?

Mallows permutation model, introduced by Mallows in statistical ranking theory, is a class of non-uniform probability measures on the symmetric group $S_n$. The model depends on a distance metric $d(\sigma,\tau)$ on $S_n$, which can be chosen from a host of metrics on permutations. In this paper, we focus on Mallows permutation models with $L^1$ and $L^2$ distances, respectively known in the statistics literature as Spearman's footrule and Spearman's rank correlation. Unlike most of the random permutation models that have been analyzed in the literature, Mallows permutation models with $L^1$ and $L^2$ distances do not have an explicit expression for their normalizing constants. This poses challenges to the task of sampling from these Mallows models. In this paper, we consider hit and run algorithms for sampling from both models. Hit and run algorithms are a unifying class of Markov chain Monte Carlo (MCMC) algorithms including the celebrated Swendsen-Wang and data augmentation algorithms. For both models, we show order $\log{n}$ mixing time upper bounds for the hit and run algorithms. This demonstrates much faster mixing of the hit and run algorithms compared to local MCMC algorith

Author

Zhong, Chenyang

Published

2021

Language

EN