Peichao Peng, J. Michael Steele
Published 2015-09-15Version 1
We find a two term asymptotic expansion for the optimal expected value of a sequentially selected monotone subsequence from a random permutation of length n. A striking feature of this expansion is that tells us that the expected value of optimal selection from a random permutation is quantifiably larger than optimal sequential selection from an independent sequences of uniformly distributed random variables; specifically, it is larger by at least (1/6)log n +O(1).
Increasing subsequences of linear size in random permutations and the Robinson-Schensted tableaux of permutons
Optimal Sequential Selection of a Unimodal Subsequence of a Random Sequence
Poisson limit for the number of cycles in a random permutation and the number of segregating sites
![QR code for arXiv:1509.04617 [math.PR]](http://oss.arxitics.com/images/favicon.svg)