Publications [#319307] of Alessandro Arlotto
Papers Published
- Arlotto, A; Steele, JM. "Optimal sequential selection of a unimodal subsequence of a random sequence." Combinatorics, Probability and Computing 20.06 (November, 2011): 799-814. [doi]
(last updated on 2023/06/01)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. © 2011 Cambridge University Press.