Refine search
Actions for selected content:
1 results
Longest increasing subsequences for distributions with atoms, and an inhomogeneous Hammersley process
- Part of
-
- Journal:
- Combinatorics, Probability and Computing , First View
- Published online by Cambridge University Press:
- 26 October 2026, pp. 1-28
-
- Article
-
- You have access
- Open access
- HTML
- Export citation
-
We investigate the asymptotic behaviour of the longest increasing subsequence
$L_n$ in a sequence of i.i.d. random variables, for an arbitrary distribution. If the common distribution is atomless then a famous result by Hammersley and Veršik-Kerov states that 
$L_n$ grows like 
$2\sqrt {n}$. For any discrete distribution, 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 
$\mathcal{O}(1)$ and 
$o(\sqrt {n})$, depending on the tail behaviour of the distribution. We can then easily deduce the asymptotics of 
$L_n$ for a completely arbitrary distribution.
