Ulam's problem and Hammersley's process

• 成果类型: Article
• 署名作者: Groeneboom, P
• 署名单位: Delft University of Technology; Vrije Universiteit Amsterdam
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/aop/1008956689
• 发表日期: 2001
• 页码: 683-690
• 关键词: longest increasing subsequences

摘要

Let L-n be the length of the longest increasing subsequence of a random permutation of the numbers 1,..., 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 --> infinity) ELn/rootn = 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.