2023/03/16 by Chenyang Zhong, Zhong, Chenyang · 1 citation
Economics, Econometrics and Finance · Mathematics · #Advanced Statistical Methods and Models #Combinatorics (math.CO) #FOS: Mathematics #Game Theory and Voting Systems #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.2303.09688
openalex publication_date 2023/03/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Introduced by Mallows in statistical ranking theory, Mallows permutation model is a class of non-uniform probability measures on the symmetric group Sn that depend on a distance metric d(σ,τ) on Sn and a scale parameter β. Taking the distance metric to be the L1 and L2 distances--which are respectively known as Spearman's footrule and Spearman's rank correlation in the statistics literature--leads to Mallows permutation models with L1 and L2 distances. In this paper, we study the length of the longest increasing subsequence of random permutations drawn from Mallows permutation models with L1 and L2 distances. For both models and various regimes of the scale parameter β, we determine the typical order of magnitude of the length of the longest increasing subsequence and establish a law of large numbers for this length. For Mallows permutation model with the L1 distance, when β∼ θn-1 for some fixed θ>0, the typical length of the longest increasing subsequence is of order √(n); when n-1≪ β≪ 1, this typical length is of order n√β. For Mallows permutation model with the L2 distance, when β∼ θn-2 for some fixed θ>0, the typical length of the longest increasing subsequence is of order √(n); when n-2≪ β≪ 1, this typical length is of order nβ(1)/(4).