Optimal Sequential Selection of a Unimodal Subsequence of a Random Sequence
- 1 January 2011
- journal article
- research article
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 20 (6) , 799-814
Abstract
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.Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- A Combinatorial Problem in Geometry2009
- A central limit theorem for the optimal selection process for monotone subsequences of maximum expected lengthStochastic Processes and their Applications, 2004
- Optimal rules for the sequential selection of monotone subsequences of maximum expected lengthStochastic Processes and their Applications, 2001
- Sequential selection of an increasing subsequence from a sample of random sizeJournal of Applied Probability, 1999
- The Height of a Random Partial Order: Concentration of MeasureThe Annals of Applied Probability, 1992
- A note on the selection of random variables under a sum constraintJournal of Applied Probability, 1991
- A note on the selection of random variables under a sum constraintJournal of Applied Probability, 1991
- Long unimodal subsequences: a problem of F.R.K. ChungDiscrete Mathematics, 1981
- Optimal Sequential Selection of a Monotone Sequence From a Random SampleThe Annals of Probability, 1981
- On unimodal subsequencesJournal of Combinatorial Theory, Series A, 1980