Limit theorems for longest monotone subsequences in random Mallows permutations
From MaRDI portal
Abstract: We study the lengths of monotone subsequences for permutations drawn from the Mallows measure. The Mallows measure was introduced by Mallows in connection with ranking problems in statistics. Under this measure, the probability of a permutation is proportional to where is a positive parameter and is the number of inversions in . In our main result we show that when , the limiting distribution of the longest increasing subsequence (LIS) is Gaussian, answering an open question in [Bhatnagar and Peled, PTRF, 2015]. This is in contrast to the case when where the limiting distribution of the LIS when scaled appropriately is the GUE Tracy-Widom distribution. We also obtain a law of large numbers for the length of the longest decreasing subsequence (LDS) and identify the precise constant in the order of the expectation, answering a further open question in [Bhatnagar and Peled, PTRF, 2015].
Recommendations
- Lengths of monotone subsequences in a Mallows permutation
- The length of the longest increasing subsequence of a random Mallows permutation
- The length of the longest common subsequence of two independent Mallows permutations
- A central limit theorem for descents of a Mallows permutation and its inverse
- On the distribution of the length of the longest increasing subsequence of random permutations
Cites work
- scientific article; zbMATH DE number 44579 (Why is no real title available?)
- scientific article; zbMATH DE number 3630761 (Why is no real title available?)
- scientific article; zbMATH DE number 847276 (Why is no real title available?)
- scientific article; zbMATH DE number 2205552 (Why is no real title available?)
- scientific article; zbMATH DE number 3073499 (Why is no real title available?)
- A central limit theorem for the length of the longest common subsequences in random words
- A variational problem for random Young tableaux
- Analysis of systematic scan Metropolis algorithms using Iwahori-Hecke algebra techniques
- Basics of Applied Stochastic Processes
- Central limit theorem for first-passage percolation time across thin cylinders
- Current fluctuations for TASEP: A proof of the Prähofer-Spohn conjecture
- Hammersley's interacting particle process and longest increasing subsequences
- Lengths of monotone subsequences in a Mallows permutation
- Limiting curves for i.i.d. records
- Longest Increasing and Decreasing Subsequences
- Metric methods for analyzing partially ranked data
- Mixing times of the biased card shuffling and the asymmetric exclusion process
- NON-NULL RANKING MODELS. I
- On Increasing Subsequences of I.I.D. Samples
- On adding a list of numbers (and other one-dependent determinantal processes)
- On the Representations of the Symmetric Group
- On the cycle structure of Mallows permutations
- On the distribution of the largest eigenvalue in principal components analysis
- On the distribution of the length of the longest increasing subsequence of random permutations
- Permutations, matrices, and generalized Young tableaux
- Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices
- Phase uniqueness for the Mallows measure on permutations
- Probability models and statistical analyses for ranking data. Papers presented at the AMS-IMS-SIAM conference, Amherst, MA, USA, June 1990
- Probability: A Graduate Course
- The asymptotics of monotone subsequences of involutions
- The length of the longest increasing subsequence of a random Mallows permutation
- The two-sided infinite extension of the Mallows model for random permutations
- Thermodynamic limit for the Mallows model on \(S_n\)
- q-exchangeability via quasi-invariance
Cited in
(26)- Thermodynamic limit for the Mallows model on \(S_n\)
- Lengths of monotone subsequences in a Mallows permutation
- Arcsine laws for random walks generated from random permutations with applications to genomics
- Mallows permutations and finite dependence
- Block size in geometric(\(p\))-biased permutations
- The limit of the empirical measure of the product of two independent Mallows permutations
- Regenerative random permutations of integers
- The length of the longest common subsequence of two independent Mallows permutations
- Poisson percolation on the square lattice
- On the cycle structure of Mallows permutations
- A central limit theorem for descents of a Mallows permutation and its inverse
- Comparing the inversion statistic for distribution-biased and distribution-shifted permutations with the geometric and the GEM distributions
- Limits of Mallows trees
- Cycles in Mallows random permutations
- Statistical enumeration of groups by double cosets
- On the limiting distribution for the length of the longest alternating sequence in a random permutation
- Longest increasing path within the critical strip
- Thresholds for patterns in random permutations with a given number of inversions
- The height of Mallows trees
- The length of the longest increasing subsequence of a random Mallows permutation
- Mallows permutations as stable matchings
- First passage percolation on hyperbolic groups
- Asymptotic normality of consecutive patterns in permutations encoded by generating trees with one‐dimensional labels
- Permutations avoiding 312 and another pattern, Chebyshev polynomials and longest increasing subsequences
- Clustering of consecutive numbers in permutations under Mallows distributions and super-clustering under general \(p\)-shifted distributions
- Power-law bounds for increasing subsequences in Brownian separable permutons and homogeneous sets in Brownian cographons
This page was built for publication: Limit theorems for longest monotone subsequences in random Mallows permutations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1700399)
