Ulam’s Problem And Hammersley’s Process
Groeneboom, Piet
Ann. Probab., Tome 29 (2001) no. 1, p. 683-690 / Harvested from Project Euclid
Text on Project Euclid
PDF
Alt PDF
Let $L_n$ be the length of the longest increasing subsequence of a random permutation of the numbers $1,\ldots, n$, for the uniform distribution on the set of permutations. Hammersley's interacting particle process, implicit in Hammersley (1972), has been used in Aldous and Diaconis (1995) to provide a “soft” hydrodynamical argument for proving that $\lim_{n \to \infty} EL_n / \sqrt{n} = 2$. We show in this note that the latter result is in fact an immediate consequence of properties of a random 2­dimensional signed measure, associated with Hammersley’s process.
Publié le : 2001-04-14
Classification:  Longest increasing subsequence, ,,  Ulam's problem,  Hammersley's process,  60C05,  60K35,  60F05 
@article{1008956689,
     author = {Groeneboom, Piet},
     title = {Ulam's Problem And Hammersley's Process},
     journal = {Ann. Probab.},
     volume = {29},
     number = {1},
     year = {2001},
     pages = { 683-690},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1008956689}
}

Groeneboom, Piet. Ulam’s Problem And Hammersley’s Process. Ann. Probab., Tome 29 (2001) no. 1, pp.  683-690. http://gdmltest.u-ga.fr/item/1008956689/