Optimal Online Selection of an Alternating Subsequence: A Central Limit Theorem


Journal Article

We analyze the optimal policy for the sequential selection of an alternating subsequence from a sequence of n independent observations from a continuous distribution F, and we prove a central limit theorem for the number of selections made by that policy. The proof exploits the backward recursion of dynamic programming and assembles a detailed understanding of the associated value functions and selection rules.

Full Text

Duke Authors

Cited Authors

  • Arlotto, A; Steele, JM

Published Date

  • June 2014

Published In

Volume / Issue

  • 46 / 2

Start / End Page

  • 536 - 559

Published By

Electronic International Standard Serial Number (EISSN)

  • 1475-6064

International Standard Serial Number (ISSN)

  • 0001-8678

Digital Object Identifier (DOI)

  • 10.1239/aap/1401369706


  • en