On-Line Alternating Subsequences of Maximal Expected Length

Abstract

Let X1,X2,…Xn be an i.i.d. uniform random variables over the interval [0, 1].We can observe the sequence sequentially. We want to select a sub-sequence k1,k2,…kM of the sequence 1,2,…,n with the following property that Xki < Xki+1 if i is odd and Xki > Xki+1 if i is even. We want to maximize the expected value of M. In this paper, we derive an algorithm to select the sub-sequence k1,k2,…kM and also prove that the maximal expected value of M is approximately equal to (2-√(2))n as n→∞ . In fact, we also obtain the lower bound and upper bound for E(M). We also study the finite case, i.e, we can only observe n observations sequentially.