×

Sequential selection of a monotone subsequence from a random permutation. (English) Zbl 1386.60038

Summary: 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)\).

MSC:

60C05 Combinatorial probability
60G40 Stopping times; optimal stopping problems; gambling theory
90C40 Markov and semi-Markov decision processes
90C39 Dynamic programming
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Arlotto, A.; Mossel, E.; Steele, J. M., Quickest online selection of an increasing subsequence of specified size, to appear in Random Structures and Algorithms (eprint arXiv:1412.7985) (2015) · Zbl 1347.60042
[2] Arlotto, Alessandro; Nguyen, Vinh V.; Steele, J. Michael, Optimal online selection of a monotone subsequence: a central limit theorem, Stochastic Process. Appl., 125, 9, 3596-3622 (2015) · Zbl 1327.60053 · doi:10.1016/j.spa.2015.03.009
[3] Baer, R. M.; Brock, P., Natural sorting over permutation spaces, Math. Comp., 22, 385-410 (1968)
[4] Baik, Jinho; Deift, Percy; Johansson, Kurt, On the distribution of the length of the longest increasing subsequence of random permutations, J. Amer. Math. Soc., 12, 4, 1119-1178 (1999) · Zbl 0932.05001 · doi:10.1090/S0894-0347-99-00307-0
[5] Bertsekas, Dimitri P.; Shreve, Steven E., Stochastic optimal control, Mathematics in Science and Engineering 139, xiii+323 pp. (1978), Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London · Zbl 0471.93002
[6] Bruss, F. Thomas; Delbaen, Freddy, Optimal rules for the sequential selection of monotone subsequences of maximum expected length, Stochastic Process. Appl., 96, 2, 313-342 (2001) · Zbl 1005.60056 · doi:10.1016/S0304-4149(01)00122-3
[7] Bruss, F. Thomas; Delbaen, Freddy, A central limit theorem for the optimal selection process for monotone subsequences of maximum expected length, Stochastic Process. Appl., 114, 2, 287-311 (2004) · Zbl 1071.60021 · doi:10.1016/j.spa.2004.09.002
[8] Bruss, F. Thomas; Robertson, James B., “Wald”s lemma” for sums of order statistics of i.i.d.random variables, Adv. in Appl. Probab., 23, 3, 612-623 (1991) · Zbl 0752.62057 · doi:10.2307/1427625
[9] Coffman, E. G., Jr.; Flatto, L.; Weber, R. R., Optimal selection of stochastic intervals under a sum constraint, Adv. in Appl. Probab., 19, 2, 454-473 (1987) · Zbl 0616.90035 · doi:10.2307/1427427
[10] Feller, William, An introduction to probability theory and its applications. Vol. II., Second edition, xxiv+669 pp. (1971), John Wiley & Sons, Inc., New York-London-Sydney · Zbl 0219.60003
[11] Flat, A.; Woeginger, G. J., Online algorithms, xviii+436 pp. (1998) · Zbl 1177.68009 · doi:10.1007/BFb0029561
[12] Gnedin, Alexander V., Sequential selection of an increasing subsequence from a sample of random size, J. Appl. Probab., 36, 4, 1074-1085 (1999) · Zbl 0960.62084
[13] Gnedin, Alexander V., A note on sequential selection from permutations, Combin. Probab. Comput., 9, 1, 13-17 (2000) · Zbl 0943.05002 · doi:10.1017/S0963548399004149
[14] Puterman, Martin L., Markov decision processes: discrete stochastic dynamic programming, Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics, xx+649 pp. (1994), John Wiley & Sons, Inc., New York · Zbl 0829.90134
[15] Romik, D., The Surprising Mathematics of Longest Increasing Subsequences (2014), Cambridge University Press: Cambridge:Cambridge University Press · Zbl 1345.05003
[16] Samuels, Stephen M.; Steele, J. Michael, Optimal sequential selection of a monotone sequence from a random sample, Ann. Probab., 9, 6, 937-947 (1981) · Zbl 0473.62073
[17] Shiryaev, A. N., Optimal stopping rules. {\rm Translated from the 1976 Russian second edition by A. B. Aries; Reprint of the 1978 translation. Stochastic Modelling and Applied Probability}, 8, xii+217 pp. (2008), Springer-Verlag, Berlin
[18] 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) · Zbl 1370.60012
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.