Hit and run algorithms and Mallows permutation models with L1 and L2 distances

Introduced by Mallows in statistical ranking theory, Mallows permutation model is a class of non-uniform probability measures on the symmetric group that are biased towards the identity. The general model depends on a distance metric that can be chosen from a host of metrics on permutations. In this talk, I will focus on Mallows permutation models with L1 and L2 distances — respectively known as Spearman's footrule and Spearman's rank correlation in the statistics literature. The models have been widely applied in statistics and physics, but have mostly resisted analysis because the normalizing constants are "uncomputable". In the first part of the talk, I will explain how we can sample from both the L1 and L2 models using hit and run algorithms, which are a unifying class of Markov chain Monte Carlo algorithms that include the celebrated Swendsen–Wang algorithm. A natural question from probabilistic combinatorics is: pick a random permutation from either of the models, what does it "look like"? This may involve various features of the permutation, such as the band structure and the length of the longest increasing subsequence. In the second part of the talk, I will explain how multi-scale analysis and hit and run algorithms can be used to prove theorems regarding such questions.