Sequential selection of an increasing sequence from a multidimensional random sample

Yuliy M. Baryshnikov; Alexander V. Gnedin

doi:10.1214/aoap/1019737672

Sequential selection of an increasing sequence from a multidimensional random sample

Yuliy M. Baryshnikov, Alexander V. Gnedin

Research output: Contribution to journal › Article › peer-review

Abstract

Let random points X₁,..., 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 γn^1/(d+1) and give the exact value of γ. This extends the √2n result by Samuels and Steele for d = 1.

Original language	English (US)
Pages (from-to)	258-267
Number of pages	10
Journal	Annals of Applied Probability
Volume	10
Issue number	1
DOIs	https://doi.org/10.1214/aoap/1019737672
State	Published - Feb 2000
Externally published	Yes

Keywords

Increasing sequence
Stopping rule
Ulam's problem

ASJC Scopus subject areas

Statistics and Probability
Statistics, Probability and Uncertainty

Online availability

10.1214/aoap/1019737672

Library availability

Discover UIUC Full Text

Cite this

@article{fa9d226ecd894824bc56c4015dec1020,

title = "Sequential selection of an increasing sequence from a multidimensional random sample",

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.",

keywords = "Increasing sequence, Stopping rule, Ulam's problem",

author = "Baryshnikov, {Yuliy M.} and Gnedin, {Alexander V.}",

year = "2000",

month = feb,

doi = "10.1214/aoap/1019737672",

language = "English (US)",

volume = "10",

pages = "258--267",

journal = "Annals of Applied Probability",

issn = "1050-5164",

publisher = "Institute of Mathematical Statistics",

number = "1",

}

TY - JOUR

T1 - Sequential selection of an increasing sequence from a multidimensional random sample

AU - Baryshnikov, Yuliy M.

AU - Gnedin, Alexander V.

PY - 2000/2

Y1 - 2000/2

N2 - 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.

AB - 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.

KW - Increasing sequence

KW - Stopping rule

KW - Ulam's problem

UR - http://www.scopus.com/inward/record.url?scp=0034344295&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0034344295&partnerID=8YFLogxK

U2 - 10.1214/aoap/1019737672

DO - 10.1214/aoap/1019737672

M3 - Article

AN - SCOPUS:0034344295

SN - 1050-5164

VL - 10

SP - 258

EP - 267

JO - Annals of Applied Probability

JF - Annals of Applied Probability

IS - 1

ER -

Sequential selection of an increasing sequence from a multidimensional random sample

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this