Sequential selection of a monotone subsequence from a random permutation
HTML articles powered by AMS MathViewer
- by Peichao Peng and J. Michael Steele
- Proc. Amer. Math. Soc. 144 (2016), 4973-4982
- DOI: https://doi.org/10.1090/proc/13104
- Published electronically: April 20, 2016
- PDF | Request permission
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.
Bibliographic Information
- Peichao Peng
- Affiliation: Department of Statistics, The Wharton School, University of Pennsylvania, 3730 Walnut Street, Philadelphia, Pennsylvania 19104
- MR Author ID: 1082870
- Email: ppeichao@wharton.upenn.edu
- J. Michael Steele
- Affiliation: Department of Statistics, The Wharton School, University of Pennsylvania, 3730 Walnut Street, Philadelphia, Pennsylvania 19104
- MR Author ID: 166615
- Email: steele@wharton.upenn.edu
- Received by editor(s): September 15, 2015
- Received by editor(s) in revised form: January 2, 2016, and January 14, 2016
- Published electronically: April 20, 2016
- Communicated by: David Levin
- © Copyright 2016 American Mathematical Society
- 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
- MathSciNet review: 3544544