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)

 
 

 

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?)


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