Abstract
The distribution of the longest increasing subsequence in a random permutation has attracted many researchers in statistics, computer sciences and mathematics. There are considerable manuscripts studying the distribution especially for large n. In this short manuscript, we provide a simple probabilistic approach to obtain the exact distribution of the length of the longest increasing subsequence of a random permutation, based on the insertion procedure and the finite Markov chain imbedding technique.
Similar content being viewed by others
References
Aldous D, Diaconis P (1995) Hammersley’s interacting particle process and longest increasing subsequences. Probab Theory Related Fields 103(2):199–213
Aldous D, Diaconis P (1999) Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem. Bull Am Math Soc (NS) 36(4):413–432
Baer RM, Brock P (1968) Natural sorting over permutation spaces. Math Comput 22:385–410
Baik J, Deift P, Johansson K (1999) On the distribution of the length of the longest increasing subsequence of random permutations. J Am Math Soc 12(4):1119–1178
Fu J (2012) On the distribution of the number of occurrences of an order-preserving pattern of length three in a random permutation. Methodol Comput Appl Probab 14:831–842
Fu JC (1995) Exact and limiting distributions of the number of successions in a random permutation. Ann Inst Stat Math 47(3):435–446
Logan BF, Shepp LA (1977) A variational problem for random Young tableaux. Adv Math 26(2):206–222
Odlyzko AM, Rains EM (1998) On longest increasing subsequences in random permutations. Technical report, AT&T Labs
Schensted C (1961) Longest increasing and decreasing subsequences. Can J Math 13:179–191
Ulam SM (1961) Monte Carlo calculations in problems of mathematical physics. In: Modern mathematics for the engineer: second series. McGraw-Hill, New York, pp 261–281
Vershik AM, Kerov SV (1977) Asymptotics of the plancherel measure of the symmetric group and the limiting form of young tables. Soviet Math Dokl 18:527–531. Translation of Dokl Acad Nauk SSSR 233:1024–1027
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Fu, J.C., Hsieh, YF. On the Distribution of the Length of the Longest Increasing Subsequence in a Random Permutation. Methodol Comput Appl Probab 17, 489–496 (2015). https://doi.org/10.1007/s11009-013-9376-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11009-013-9376-1