On-Line Selection of c-Alternating Subsequences from a Random Sample

A sequence is a -alternating sequence if any odd term is less than or equal to the next even term and the any even term is greater than or equal to the next odd term , where is a nonnegative constant. In this paper, we present an optimal on-line procedure to select a -alternating subsequence from a symmetric distributed random sample. We also give the optimal selection rate when the sample size goes to infinity. 1. Introduction Given a finite (or infinite) sequence of real numbers, we say that a subsequence with is -alternating if we have , where is a nonnegative real number. When , is alternating. We are mainly concerned with the length of the longest -alternating subsequence of . Here, we study the problem of making on-line selection of a -alternating subsequence. That is now we regard the sequence as being available to us sequentially, and, at time when is available, we must choose to include as a term of our subsequence or reject as a member of our subsequence. We will consider the sequence to be given by independent, identically distributed, symmetric random variables over the interval . In [1], Arlotto et al. studied the case that the sequence to be given by independent, identically distributed, uniform random variables over the interval and . So this paper can be considered as an extension of their paper. Now we need to be more explicit about the set of feasible strategies for on-line selection. At time , when is presented to us, we must decide to select based on its value, the value of earlier members of the sequence, and the actions we have taken in the past. All of this information can be captured by saying that , the index of the th selection, must be a stopping time with respect to the increasing sequence of -fields, , . Given any feasible policy in the random variable of most interest here is , the number of selections made by the policy up to and including time . In other words, is equal to the largest for which there are stopping times such that is a -alternating subsequence of the sequence . In this paper, we are interested in the optimal selection and the asymptotic rate of the optimal selection. That is, we have a selection policy in such that 2. Main Results For each and each , we define a threshold function as follows: for all . We now recursively define random variables by setting and taking if , if . Introduce a value function , where is a constant and is the indicator function of the event . Let be the distribution function and the probability density function of . If is not a uniform random variable over the interval , then we