Sequential selection of an increasing sequence from a multidimensional random sample

Yuliy M. Baryshnikov, Alexander V. Gnedin

Research output: Contribution to journalArticlepeer-review

Abstract

Let random points X1,..., Xn be sampled in strict sequence from a continuous product distribution on Euclidean d-space. At the time Xj 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 γn1/(d+1) and give the exact value of γ. This extends the √2n result by Samuels and Steele for d = 1.

Original languageEnglish (US)
Pages (from-to)258-267
Number of pages10
JournalAnnals of Applied Probability
Volume10
Issue number1
DOIs
StatePublished - Feb 2000
Externally publishedYes

Keywords

  • Increasing sequence
  • Stopping rule
  • Ulam's problem

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Fingerprint Dive into the research topics of 'Sequential selection of an increasing sequence from a multidimensional random sample'. Together they form a unique fingerprint.

Cite this