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

Abstract

We investigate the asymptotic behaviour of the longest increasing subsequence

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

upper L Subscript n L n $L_n$

grows like

2 StartRoot n EndRoot 2 n $2\sqrt {n}$

. For any discrete distribution, we characterize the asymptotic order of

upper L Subscript n L n $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

script upper O left parenthesis 1 right parenthesis O ( 1 ) $\mathcal{O}(1)$

and

o left parenthesis StartRoot n EndRoot right parenthesis o ( n ) $o(\sqrt {n})$

, depending on the tail behaviour of the distribution. We can then easily deduce the asymptotics of

upper L Subscript n L n $L_n$

for a completely arbitrary distribution.