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.

It is demonstrated that for each n ≧ 2 there exists a minimal universal constant, cn, such that, for any sequence of independent random variables {Xr, r ≧ 1} with finite variances, , where the supremum is over all stopping times Τ, 1 ≦ Τ ≦ n. Furthermore, cn ≦ 1/2 and lim infn→ ∞cn ≧ 0.439485 · ··.

Let X1, X2, · ··, Xn be positive i.i.d. random variables with known distribution function having a finite mean. For a given s ≥0 we define Nn = N(n, s) to be the largest number k such that the sum of the smallest k Xs does not exceed s, and Mn = M(n, s) to be the largest number k such that the sum of the largest k X's does not exceed s. This paper studies the precise and asymptotic behaviour of E(Nn), E(Mn), Nn, Mn, and the corresponding ‘stopped' order statistics and as n →∞, both for fixed s, and where s =sn is an increasing function of n.

Optimal stopping of a sequence of random variables is studied, with emphasis on generalized objectives which may be non-monotone functions of EXt, where t is a stopping time, or may even depend on the entire vector (E[X1I{t=l}], · ··, E[XnI{t=n}]), such as the minimax objective to maximize minj{E[XjI{t=j}]}. Convexity is used to establish a prophet inequality and universal bounds for the optimal return, and a method for constructing optimal stopping times for such objectives is given.