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 条

[1] On the Distribution of the Length of the Longest Increasing Subsequence in a Random Permutation
Fu, James C.
Hsieh, Yu-Fei
METHODOLOGY AND COMPUTING IN APPLIED PROBABILITY, 2015, 17 (02) : 489 - 496
[2] The Length of the Longest Increasing Subsequence of a Random Mallows Permutation
Carl Mueller
Shannon Starr
Journal of Theoretical Probability, 2013, 26 : 514 - 540
[3] The Length of the Longest Increasing Subsequence of a Random Mallows Permutation
Mueller, Carl
Starr, Shannon
JOURNAL OF THEORETICAL PROBABILITY, 2013, 26 (02) : 514 - 540
[4] On the distribution of the length of the longest increasing subsequence of random permutations
Baik, J
Deift, P
Johansson, K
JOURNAL OF THE AMERICAN MATHEMATICAL SOCIETY, 1999, 12 (04) : 1119 - 1178
[5] Large deviations for the longest alternating and the longest increasing subsequence in a random permutation avoiding a pattern of length three
Pinsky, Ross G.
ELECTRONIC COMMUNICATIONS IN PROBABILITY, 2024, 29
[6] The longest increasing subsequence in a random permutation and a unitary random matrix model
Johansson, K
MATHEMATICAL RESEARCH LETTERS, 1998, 5 (1-2) : 63 - 82
[7] On the length of the longest subsequence avoiding an arbitrary pattern in a random permutation
Albert, M. H.
RANDOM STRUCTURES & ALGORITHMS, 2007, 31 (02) : 227 - 238
[8] The Distribution of the Length of the Longest Increasing Subsequence in Random Permutations of Arbitrary Multi-sets
Al-Meanazel, Ayat
Johnson, Brad C.
METHODOLOGY AND COMPUTING IN APPLIED PROBABILITY, 2020, 22 (03) : 1009 - 1021
[9] The Distribution of the Length of the Longest Increasing Subsequence in Random Permutations of Arbitrary Multi-sets
Ayat Al-Meanazel
Brad C. Johnson
Methodology and Computing in Applied Probability, 2020, 22 : 1009 - 1021
[10] Large deviations of the length of the longest increasing subsequence of random permutations and random walks
Boerjes, Joern
Schawe, Hendrik
Hartmann, Alexander K.
PHYSICAL REVIEW E, 2019, 99 (04)

← 1 2 3 4 5 →