On the Distribution of the Length of the Longest Increasing Subsequence in a Random Permutation

James C. Fu and Yu-Fei Hsieh ()
Additional contact information
James C. Fu: University of Manitoba
Yu-Fei Hsieh: University of Manitoba

Methodology and Computing in Applied Probability, 2015, vol. 17, issue 2, 489-496

Abstract: 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.

Keywords: Longest increasing subsequence; Insertion procedure; Finite Markov chain imbedding; Random permutation; 60E05; 60J10 (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s11009-013-9376-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:metcap:v:17:y:2015:i:2:d:10.1007_s11009-013-9376-1

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/11009

DOI: 10.1007/s11009-013-9376-1

Access Statistics for this article

Methodology and Computing in Applied Probability is currently edited by Joseph Glaz

More articles in Methodology and Computing in Applied Probability from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().