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

Source abstract

Abstract We investigate the asymptotic behaviour of the longest increasing subsequence upper L Subscript n L n $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 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.