Sequential selection of a monotone subsequence from a random permutation

Peng, Peichao; Steele, J.

doi:10.1090/proc/13104

Sequential selection of a monotone subsequence from a random permutation

Authors: Peichao Peng and J. Michael Steele
Journal: Proc. Amer. Math. Soc. 144 (2016), 4973-4982
MSC (2010): Primary 60C05, 60G40, 90C40; Secondary 60F99, 90C27, 90C39
DOI: https://doi.org/10.1090/proc/13104
Published electronically: April 20, 2016
MathSciNet review: 3544544
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: 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 it tells us that the expected value of optimal selection from a random permutation is quantifiably larger than optimal sequential selection from an independent sequence of uniformly distributed random variables; specifically, it is larger by at least $(1/6) \log n +O(1)$.

References

A. Arlotto, E. Mossel, and J. M. Steele, Quickest online selection of an increasing subsequence of specified size, to appear in Random Structures and Algorithms (eprint arXiv:1412.7985) (2015).
Alessandro Arlotto, Vinh V. Nguyen, and J. Michael Steele, Optimal online selection of a monotone subsequence: a central limit theorem, Stochastic Process. Appl. 125 (2015), no. 9, 3596–3622. MR 3357621, DOI 10.1016/j.spa.2015.03.009
R. M. Baer and P. Brock, Natural sorting over permutation spaces, Math. Comp. 22 (1968), 385–410. MR 228216, DOI 10.1090/S0025-5718-1968-0228216-8
Jinho Baik, Percy Deift, and Kurt Johansson, On the distribution of the length of the longest increasing subsequence of random permutations, J. Amer. Math. Soc. 12 (1999), no. 4, 1119–1178. MR 1682248, DOI 10.1090/S0894-0347-99-00307-0
Dimitri P. Bertsekas and Steven E. Shreve, Stochastic optimal control, Mathematics in Science and Engineering, vol. 139, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1978. The discrete time case. MR 511544
F. Thomas Bruss and Freddy Delbaen, Optimal rules for the sequential selection of monotone subsequences of maximum expected length, Stochastic Process. Appl. 96 (2001), no. 2, 313–342. MR 1865761, DOI 10.1016/S0304-4149(01)00122-3
F. Thomas Bruss and Freddy Delbaen, A central limit theorem for the optimal selection process for monotone subsequences of maximum expected length, Stochastic Process. Appl. 114 (2004), no. 2, 287–311. MR 2101246, DOI 10.1016/j.spa.2004.09.002
F. Thomas Bruss and James B. Robertson, “Wald’s lemma” for sums of order statistics of i.i.d. random variables, Adv. in Appl. Probab. 23 (1991), no. 3, 612–623. MR 1122878, DOI 10.2307/1427625
E. G. Coffman Jr., L. Flatto, and R. R. Weber, Optimal selection of stochastic intervals under a sum constraint, Adv. in Appl. Probab. 19 (1987), no. 2, 454–473. MR 889945, DOI 10.2307/1427427
William Feller, An introduction to probability theory and its applications. Vol. II. , 2nd ed., John Wiley & Sons, Inc., New York-London-Sydney, 1971. MR 0270403
Amos Fiat and Gerhard J. Woeginger (eds.), Online algorithms, Lecture Notes in Computer Science, vol. 1442, Springer-Verlag, Berlin, 1998. The state of the art; Papers from the Workshop on the Competitive Analysis of On-line Algorithms held in Schloss Dagstuhl, June 1996. MR 1673029, DOI 10.1007/BFb0029561
Alexander V. Gnedin, Sequential selection of an increasing subsequence from a sample of random size, J. Appl. Probab. 36 (1999), no. 4, 1074–1085. MR 1742151, DOI 10.1239/jap/1032374756
Alexander V. Gnedin, A note on sequential selection from permutations, Combin. Probab. Comput. 9 (2000), no. 1, 13–17. MR 1751299, DOI 10.1017/S0963548399004149
Martin L. Puterman, Markov decision processes: discrete stochastic dynamic programming, Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics, John Wiley & Sons, Inc., New York, 1994. A Wiley-Interscience Publication. MR 1270015, DOI 10.1002/9780470316887
D. Romik, The Surprising Mathematics of Longest Increasing Subsequences, Cambridge University Press, Cambridge, 2014., DOI 10.1017/CBO9781139872003
Stephen M. Samuels and J. Michael Steele, Optimal sequential selection of a monotone sequence from a random sample, Ann. Probab. 9 (1981), no. 6, 937–947. MR 632967
A. N. Shiryaev, Optimal stopping rules, Stochastic Modelling and Applied Probability, vol. 8, Springer-Verlag, Berlin, 2008. Translated from the 1976 Russian second edition by A. B. Aries; Reprint of the 1978 translation. MR 2374974
J. M. Steele, The Bruss-Robertson inequality: Elaborations, extensions, and applications, to appear in Mathematica Applicanda (Annales Societatis Mathematicae Polonae Series III) Volume 44, 2016 (eprint arXiv:1510.00843), 2016.