Large deviations for the longest alternating and the longest increasing subsequence in a random permutation avoiding a pattern of length three

被引:0
作者
Pinsky, Ross G. [1 ]
机构
[1] Technion Israel Inst Technol, Haifa, Israel
关键词
large deviations; pattern avoiding permutation; longest increasing subsequence; longest alternating subsequence;
D O I
10.1214/24-ECP579
中图分类号
O21 [概率论与数理统计]; C8 [统计学];
学科分类号
020208 ; 070103 ; 0714 ;
摘要
We calculate the large deviations for the length of the longest alternating subsequence and for the length of the longest increasing subsequence in a uniformly random permutation that avoids a pattern of length three. We treat all six patterns in the case of alternating subsequences. In the case of increasing subsequences, we treat two of the three patterns for which a classical large deviations result is possible. The same rate function appears in all six cases for alternating subsequences. This rate function is in fact the rate function for the large deviations of the sum of IID symmetric Bernoulli random variables. The same rate function appears in the two cases we treat for increasing subsequences. This rate function is twice the rate function for alternating subsequences.
引用
收藏
页数:12
相关论文
共 14 条
[1]   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
[2]   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
[3]  
Bona M., 2012, Combinatorics of Permutations, V2nd
[4]  
DEMBO A., 1998, Applications of Mathematics, V2nd
[5]   On increasing subsequences of IID samples [J].
Deuschel, JD ;
Zeitouni, O .
COMBINATORICS PROBABILITY & COMPUTING, 1999, 8 (03) :247-263
[6]  
Deutsch E., 2002, J. Combin., V9
[7]  
Firro G, 2007, ELECTRON J COMB, V14
[8]   VARIATIONAL PROBLEM FOR RANDOM YOUNG TABLEAUX [J].
LOGAN, BF ;
SHEPP, LA .
ADVANCES IN MATHEMATICS, 1977, 26 (02) :206-222
[9]  
ROMIK D, 2015, Institute of Mathematical Statistics Textbooks, V4
[10]   Large deviations for increasing sequences on the plane [J].
Seppalainen, T .
PROBABILITY THEORY AND RELATED FIELDS, 1998, 112 (02) :221-244