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

被引：0
作者：
James C. Fu
Yu-Fei Hsieh
机构：
[1] University of Manitoba,Department of Statistics
来源：
Methodology and Computing in Applied Probability | 2015年 / 17卷
关键词：
Longest increasing subsequence; Insertion procedure; Finite Markov chain imbedding; Random permutation; 60E05; 60J10;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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.
引用
收藏
页码：489 / 496
页数：7
相关论文
共 50 条
[31]   On the limiting law of the length of the longest common and increasing subsequences in random words [J].
Breton, Jean-Christophe ;
Houdre, Christian .
STOCHASTIC PROCESSES AND THEIR APPLICATIONS, 2017, 127 (05) :1676-1720
[32]   Finding longest common increasing subsequence for two different scenarios of non-random input sequences [J].
Bai, YS ;
Weems, BP .
FCS '05: Proceedings of the 2005 International Conference on Foundations of Computer Science, 2005, :64-70
[33]   A linear space algorithm for computing a longest common increasing subsequence [J].
Sakai, Yoshifumi .
INFORMATION PROCESSING LETTERS, 2006, 99 (05) :203-207
[34]   A concentration bound for the longest increasing subsequence of a randomly chosen involution [J].
Kiwi, Marcos .
DISCRETE APPLIED MATHEMATICS, 2006, 154 (13) :1816-1823
[35]   Parallel Longest Increasing Subsequence and van Emde Boas Trees [J].
Gu, Yan ;
Men, Ziyang ;
Shen, Zheqi ;
Sun, Yihan ;
Wan, Zijin .
PROCEEDINGS OF THE 35TH ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES, SPAA 2023, 2023, :327-340
[36]   THE LENGTH OF THE LONGEST COMMON SUBSEQUENCE OF TWO INDEPENDENT MALLOWS PERMUTATIONS [J].
Jin, Ke .
ANNALS OF APPLIED PROBABILITY, 2019, 29 (03) :1311-1355
[37]   Finding Maximum Noncrossing Subset of Nets Using Longest Increasing Subsequence [J].
Deng, Xinguo ;
Zhong, Rui .
KNOWLEDGE DISCOVERY AND DATA MINING, 2012, 135 :759-+
[38]   A work-optimal CGM algorithm for the longest increasing subsequence problem [J].
Garcia, T ;
Myoupo, JF ;
Semé, D .
PDPTA'2001: PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED PROCESSING TECHNIQUES AND APPLICATIONS, 2001, :563-569
[39]   A note on randomized streaming space bounds for the longest increasing subsequence problem [J].
Chakrabarti, Amit .
INFORMATION PROCESSING LETTERS, 2012, 112 (07) :261-263
[40]   ON THE RATE OF APPROXIMATION IN FINITE-ALPHABET LONGEST INCREASING SUBSEQUENCE PROBLEMS [J].
Houdre, Christian ;
Talata, Zsolt .
ANNALS OF APPLIED PROBABILITY, 2012, 22 (06) :2539-2559
12345