The Distribution of the Length of the Longest Increasing Subsequence in Random Permutations of Arbitrary Multi-sets

被引：1

作者：

Al-Meanazel, Ayat ^{[1
]}

Johnson, Brad C. ^{[2
]}

机构：

[1] Al al Bayt Univ, Dept Math, POB 130040, Mafraq 25113, Jordan

[2] Univ Manitoba, Dept Stat, Winnipeg, MB R3T 2N2, Canada

来源：

METHODOLOGY AND COMPUTING IN APPLIED PROBABILITY | 2020年 / 22卷 / 03期

关键词：

Markov chain; Impedding; Permutation; Increasing subsequence; Distribution; Arbitrary multi-sets;

D O I：

10.1007/s11009-019-09753-1

中图分类号：

O21 [概率论与数理统计]; C8 [统计学];

学科分类号：

020208 ; 070103 ; 0714 ;

摘要：

The distribution of the length of the longest increasing subsequence in random permutations of arbitrary multi-sets is obtained using the finite Markov chain imbedding technique (FMCI). A numerical examples are provided to aid in understanding.

引用

页码：1009 / 1021

页数：13

共 14 条

[1] DISTRIBUTIONS OF NUMBERS OF FAILURES AND SUCCESSES UNTIL THE 1ST CONSECUTIVE K SUCCESSES [J].

AKI, S ;

HIRANO, K .

ANNALS OF THE INSTITUTE OF STATISTICAL MATHEMATICS, 1994, 46 (01) :193-202

[2] Longest increasing subsequences: From patience sorting to the Baik-Deift-Johansson theorem [J].

Aldous, D ;

Diaconis, P .

BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 1999, 36 (04) :413-432

[3] HAMMERSLEYS INTERACTING PARTICLE PROCESS AND LONGEST INCREASING SUBSEQUENCES [J].

ALDOUS, D ;

DIACONIS, P .

PROBABILITY THEORY AND RELATED FIELDS, 1995, 103 (02) :199-213

[4]

[Anonymous], 2000, Analysis, geometry, number theory: the mathematics of Leon Ehrenpreis

[5] NATURAL SORTING OVER PERMUTATION SPACES [J].

BAER, RM ;

BROCK, P .

MATHEMATICS OF COMPUTATION, 1968, 22 (102) :385-&

[6] On the distribution of the length of the longest increasing subsequence of random permutations [J].

Baik, J ;

Deift, P ;

Johansson, K .

JOURNAL OF THE AMERICAN MATHEMATICAL SOCIETY, 1999, 12 (04) :1119-1178

[7]

CHRYSSAPHINOU O, 1993, APPLICATIONS OF FIBONACCI NUMBERS, VOL 5, P103

[8]

Erdos P, 1935, Compositio Math., V2, P463

[9] On the Distribution of the Length of the Longest Increasing Subsequence in a Random Permutation [J].

Fu, James C. ;

Hsieh, Yu-Fei .

METHODOLOGY AND COMPUTING IN APPLIED PROBABILITY, 2015, 17 (02) :489-496

[10] DISTRIBUTION-THEORY OF RUNS - A MARKOV-CHAIN APPROACH [J].

FU, JC ;

KOUTRAS, MV .

JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION, 1994, 89 (427) :1050-1058

← 1 2 →