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)$.

- 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.

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

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

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