Online Selection of Alternating Subsequences from a Random Sample


Journal Article

We consider sequential selection of an alternating subsequence from a sequence of independent, identically distributed, continuous random variables, and we determine the exact asymptotic behavior of an optimal sequentially selected subsequence. Moreover, we find (in a sense we make precise) that a person who is constrained to make sequential selections does only about 12 percent worse than a person who can make selections with full knowledge of the random sequence.

Full Text

Duke Authors

Cited Authors

  • Arlotto, A; Chen, RW; Shepp, LA; Steele, JM

Published Date

  • December 2011

Published In

Volume / Issue

  • 48 / 4

Start / End Page

  • 1114 - 1132

Published By

Electronic International Standard Serial Number (EISSN)

  • 1475-6072

International Standard Serial Number (ISSN)

  • 0021-9002

Digital Object Identifier (DOI)

  • 10.1239/jap/1324046022


  • en