Longest increasing subsequences for distributions with atoms, and an inhomogeneous Hammersley process

2025/07/08 by Basdevant, Anne-Laure, Gerin, Lucas, Marivain, Maxime
#Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2507.05775

Abstract

A famous result by Hammersley and Versik-Kerov states that the length L_n of the longest increasing subsequence among n iid continuous random variables grows like 2√(n). We investigate here the asymptotic behavior of L_n for distributions with atoms. For purely discrete random variables, we characterize the asymptotic order of L_n through a variational problem and provide explicit estimates for classical distributions. The proofs rely on a coupling with an inhomogeneous version of the discrete-time continuous-space Hammersley process. This reveals that, in contrast to the continuous case, the discrete setting exhibits a wide range of growth rates between O(1) and o(√(n)), depending on the tail behavior of the distribution. We can then easily deduce the asymptotics of L_n for a completely arbitrary distribution.

Citations

• The Ulam-Hammersley problem for multiset permutations
• Order of the variance in the discrete Hammersley process with boundaries
• Discrete Hammersley's Lines with sources and sinks
• On the Longest Increasing Subsequence for Finite and Countable Alphabets
• Multiclass processes, dual points and M/M/1 queues
• Hammersley’s process with sources and sinks
• Discrete orthogonal polynomial ensembles and the Plancherel measure
• Concentration of Measure and Isoperimetric Inequalities in Product\n Spaces

Related

• Asymptotics of the Longest Increasing Subsequence in Random Permutations
• Asymptotic expansions relating to the lengths of longest monotone subsequences of involutions
• On the Longest Increasing Subsequence for Finite and Countable Alphabets
• Finite size corrections relating to distributions of the length of longest increasing subsequences
• On increasing subsequences of iid samples