Title: Longest increasing subsequence and cycle structure of Mallows permutation models with L1 and L2 distances.
Abstract: Introduced by Mallows in statistical ranking theory, the Mallows permutation model is a class of non-uniform probability measures on permutations. The general model depends on a distance metric on the symmetric group. This talk focuses on Mallows permutation models with L1 and L2 distances, which possess spatial structure and are also known as “spatial random permutations” in the mathematical physics literature.
A natural question from probabilistic combinatorics is: Picking a random permutation from either of the models, what does it “look like”? This may involve various features of the permutation, such as the length of the longest increasing subsequence and the cycle structure. In this talk, I will explain how multi-scale analysis and the hit and run algorithm—a Markov chain for sampling from both models—can be used to establish limit theorems for these features.