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

Research paper by James C. Fu, Yu-Fei Hsieh

Indexed on: 03 Oct '13Published on: 03 Oct '13Published in: Methodology and computing in applied probability


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.