The length of the longest monotone increasing subsequence of a random sample of size $n$ is known to have expected value asymptotic to $2n^{1/2}$. We prove that it is possible to make sequential choices which give an increasing subsequence of expected length asymptotic to $(2n)^{1/2}$. Moreover, this rate of increase is proved to be asymptotically best possible.
@article{1176994265,
author = {Samuels, Stephen M. and Steele, J. Michael},
title = {Optimal Sequential Selection of a Monotone Sequence From a Random Sample},
journal = {Ann. Probab.},
volume = {9},
number = {6},
year = {1981},
pages = { 937-947},
language = {en},
url = {http://dml.mathdoc.fr/item/1176994265}
}
Samuels, Stephen M.; Steele, J. Michael. Optimal Sequential Selection of a Monotone Sequence From a Random Sample. Ann. Probab., Tome 9 (1981) no. 6, pp. 937-947. http://gdmltest.u-ga.fr/item/1176994265/