Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

Request Permissions   Purchase Content 
 
 

 

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

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 [Enhancements On Off] (What's this?)

  • [Arlotto et al. , 2015] Arlotto, A., 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).
  • [Arlotto et al. , 2015] Arlotto, Alessandro, 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, https://doi.org/10.1016/j.spa.2015.03.009
  • [Baer and Brock, 1968] Baer, R. M. and P. Brock, Natural sorting over permutation spaces, Math. Comp. 22 (1968), 385-410. MR 0228216
  • [Baik et al. , 1999] Baik, Jinho, 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, https://doi.org/10.1090/S0894-0347-99-00307-0
  • [Bertsekas and Shreve, 1978] Bertsekas, Dimitri P. and Steven E. Shreve, Stochastic optimal control: The discrete time case, Mathematics in Science and Engineering, vol. 139, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1978. MR 511544
  • [Bruss and Delbaen, 2001] Bruss, F. Thomas 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, https://doi.org/10.1016/S0304-4149(01)00122-3
  • [Bruss and Delbaen, 2004] Bruss, F. Thomas 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, https://doi.org/10.1016/j.spa.2004.09.002
  • [Bruss and Robertson, 1991] Bruss, F. Thomas 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, https://doi.org/10.2307/1427625
  • [Coffman et al. , 1987] Coffman, E. G., 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, https://doi.org/10.2307/1427427
  • [Feller, 1971] Feller, William, An introduction to probability theory and its applications. Vol. II., Second edition, John Wiley & Sons, Inc., New York-London-Sydney, 1971. MR 0270403
  • [Flat and Woeginger, 1998] Flat, A. and G. J. Woeginger, Online algorithms, 1998. The state of the art; Papers from the Workshop on the Competitive Analysis of On-line Algorithms held in Schloss Dagstuhl, June 1996; Edited by Amos Fiat and Gerhard J. Woeginger. Lecture Notes in Computer Science, vol. 1442, Springer-Verlag, Berlin. MR 1673029
  • [Gnedin, 1999] Gnedin, Alexander V., Sequential selection of an increasing subsequence from a sample of random size, J. Appl. Probab. 36 (1999), no. 4, 1074-1085. MR 1742151
  • [Gnedin, 2000] Gnedin, Alexander V., A note on sequential selection from permutations, Combin. Probab. Comput. 9 (2000), no. 1, 13-17. MR 1751299, https://doi.org/10.1017/S0963548399004149
  • [Puterman, 1994] Puterman, Martin L., 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
  • [Romik, 2014] Romik, D., The Surprising Mathematics of Longest Increasing Subsequences, Cambridge University Press, Cambridge, 2014.
  • [Samuels and Steele, 1981] Samuels, Stephen M. 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
  • [Shiryaev, 2008] Shiryaev, A. N., Optimal stopping rules. Translated from the 1976 Russian second edition by A. B. Aries; Reprint of the 1978 translation. Stochastic Modelling and Applied Probability, Vol. 8, Springer-Verlag, Berlin, 2008. MR 2374974
  • [Steele, 2016] Steele, J. M., 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.

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 60C05, 60G40, 90C40, 60F99, 90C27, 90C39

Retrieve articles in all journals with MSC (2010): 60C05, 60G40, 90C40, 60F99, 90C27, 90C39


Additional Information

Peichao Peng
Affiliation: Department of Statistics, The Wharton School, University of Pennsylvania, 3730 Walnut Street, Philadelphia, Pennsylvania 19104
Email: ppeichao@wharton.upenn.edu

J. Michael Steele
Affiliation: Department of Statistics, The Wharton School, University of Pennsylvania, 3730 Walnut Street, Philadelphia, Pennsylvania 19104
Email: steele@wharton.upenn.edu

DOI: https://doi.org/10.1090/proc/13104
Keywords: Monotone subsequence problem, sequential selection, online selection, Markov decision problem, nonlinear recursion, prophet inequality
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
Article copyright: © Copyright 2016 American Mathematical Society

American Mathematical Society