Combinatorics, Probability and Computing

Paper

Optimal Sequential Selection of a Unimodal Subsequence of a Random Sequence

ALESSANDRO ARLOTTOa1 and J. MICHAEL STEELEa2

a1 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)

a2 Department of Statistics, Wharton School, Huntsman Hall 447, University of Pennsylvania, Philadelphia, PA 19104, USA (e-mail: steele@wharton.upenn.edu)

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.

(Received October 19 2010)

(Revised August 25 2011)

(Online publication October 05 2011)