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

We investigate the asymptotic behaviour of the longest increasing subsequence upper L Subscript n L n Lₙ 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ₙ grows like 2 StartRoot n EndRoot 2 n 2√n . For any discrete distribution, we characterize the asymptotic order of upper L Subscript n L n Lₙ 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 ) O(1) and o left parenthesis StartRoot n EndRoot right parenthesis o ( n ) o(√n) , depending on the tail behaviour of the distribution. We can then easily deduce the asymptotics of upper L Subscript n L n Lₙ for a completely arbitrary distribution.