Hostname: page-component-745bb68f8f-kw2vx Total loading time: 0 Render date: 2025-02-07T04:40:47.007Z Has data issue: false hasContentIssue false
  • English
  • Français

Optimal Sequential Selection of a Unimodal Subsequence of a Random Sequence

Published online by Cambridge University Press:  05 October 2011

ALESSANDRO ARLOTTO  and
J. MICHAEL STEELE
ALESSANDRO ARLOTTO
Affiliation:
Department of Operations and Information Management, Wharton School, Huntsman Hall 527.2, University of Pennsylvania, Philadelphia, PA 19104, USA (e-mail: alear@wharton.upenn.edu)
J. MICHAEL STEELE
Affiliation:
Department of Statistics, Wharton School, Huntsman Hall 447, University of Pennsylvania, Philadelphia, PA 19104, USA (e-mail: steele@wharton.upenn.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We consider the problem of selecting sequentially a unimodal subsequence from a sequence of independent identically distributed random variables, and we find that a person doing optimal sequential selection does so within a factor of the square root of two as well as a prophet who knows all of the random observations in advance of any selections. Our analysis applies in fact to selections of subsequences that have d+1 monotone blocks, and, by including the case d=0, our analysis also covers monotone subsequences.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 20 , Issue 6 , November 2011 , pp. 799 - 814
Copyright
Copyright © Cambridge University Press 2011

References

[1]Baik, J., Deift, P. and Johansson, K. (1999) On the distribution of the length of the longest increasing subsequence of random permutations. J. Amer. Math. Soc. 12 1119–1178.CrossRefGoogle Scholar
[2]Bertsekas, D. P. and Shreve, S. E. (1978) Stochastic Optimal Control: The Discrete Time Case, Vol. 139 of Mathematics in Science and Engineering, Academic Press.Google Scholar
[3]Bollobás, B. and Brightwell, G. (1992) The height of a random partial order: Concentration of measure. Ann. Appl. Probab. 2 1009–1018.CrossRefGoogle Scholar
[4]Bollobás, B. and Janson, S. (1997) On the length of the longest increasing subsequence in a random permutation. In Combinatorics, Geometry and Probability: Cambridge 1993, Cambridge University Press, pp. 121–128.CrossRefGoogle Scholar
[5]Bruss, F. T. and Delbaen, F. (2001) Optimal rules for the sequential selection of monotone subsequences of maximum expected length. Stochastic Process. Appl. 96 313–342.CrossRefGoogle Scholar
[6]Bruss, F. T. and Delbaen, F. (2004) A central limit theorem for the optimal selection process for monotone subsequences of maximum expected length. Stochastic Process. Appl. 114 287–311.CrossRefGoogle Scholar
[7]Bruss, F. T. and Robertson, J. B. (1991) ‘Wald's lemma’ for sums of order statistics of i.i.d. random variables. Adv. Appl. Probab. 23 612–623.CrossRefGoogle Scholar
[8]Chung, F. R. K. (1980) On unimodal subsequences. J. Combin. Theory Ser. A 29 267–279.CrossRefGoogle Scholar
[9]Erdős, P. and Szekeres, G. (1935) A combinatorial problem in geometry. Compositio Math. 2 463–470.Google Scholar
[10]Gnedin, A. V. (1999) Sequential selection of an increasing subsequence from a sample of random size. J. Appl. Probab. 36 1074–1085.CrossRefGoogle Scholar
[11]Lugosi, G. (2009) Concentration-of-measure inequalities. www.econ.upf.edu/~lugosi/anu.pdf.Google Scholar
[12]Rhee, W. and Talagrand, M. (1991) A note on the selection of random variables under a sum constraint. J. Appl. Probab. 28 919–923.CrossRefGoogle Scholar
[13]Samuels, S. M. and Steele, J. M. (1981) Optimal sequential selection of a monotone sequence from a random sample. Ann. Probab. 9 937–947.CrossRefGoogle Scholar
[14]Steele, J. M. (1981) Long unimodal subsequences: A problem of F. R. K. Chung. Discrete Math. 33 223–225.CrossRefGoogle Scholar