Let random points $X_1,\dots, X_n$ be sampled in strict sequence
from a continuous product distribution on Euclidean $d$-space. At the time
$X_j$ is observed it must be accepted or rejected. The subsequence of accepted
points must increase in each coordinate. We show that the maximum expected
length of a subsequence selected is asymptotic to $\gamma n^{1/(d+1)}$ and give
the exact value of $\gamma$. This extends the $\sqrt{2n}$ result by Samuels and
Steele for $d = 1$.
@article{1019737672,
author = {Baryshnikov, Yuliy M. and Gnedin, Alexander V.},
title = {Sequential selection of an increasing sequence from a
multidimensional random sample},
journal = {Ann. Appl. Probab.},
volume = {10},
number = {2},
year = {2000},
pages = { 258-267},
language = {en},
url = {http://dml.mathdoc.fr/item/1019737672}
}
Baryshnikov, Yuliy M.; Gnedin, Alexander V. Sequential selection of an increasing sequence from a
multidimensional random sample. Ann. Appl. Probab., Tome 10 (2000) no. 2, pp. 258-267. http://gdmltest.u-ga.fr/item/1019737672/