Skip to main content
Journal cover image

Optimal online selection of a monotone subsequence: A central limit theorem

Publication ,  Journal Article
Arlotto, A; Nguyen, VV; Steele, JM
Published in: Stochastic Processes and their Applications
July 28, 2015

Consider a sequence of n independent random variables with a common continuous distribution F, and consider the task of choosing an increasing subsequence where the observations are revealed sequentially and where an observation must be accepted or rejected when it is first revealed. There is a unique selection policy πn∗ that is optimal in the sense that it maximizes the expected value of Ln(πn∗), the number of selected observations. We investigate the distribution of Ln(πn∗); in particular, we obtain a central limit theorem for Ln(πn∗) and a detailed understanding of its mean and variance for large n. Our results and methods are complementary to the work of Bruss and Delbaen (2004) where an analogous central limit theorem is found for monotone increasing selections from a finite sequence with cardinality N where N is a Poisson random variable that is independent of the sequence.

Duke Scholars

Altmetric Attention Stats
Dimensions Citation Stats

Published In

Stochastic Processes and their Applications

DOI

ISSN

0304-4149

Publication Date

July 28, 2015

Volume

125

Issue

9

Start / End Page

3596 / 3622

Related Subject Headings

  • Statistics & Probability
  • 4905 Statistics
  • 4901 Applied mathematics
  • 1502 Banking, Finance and Investment
  • 0104 Statistics
  • 0102 Applied Mathematics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Arlotto, A., Nguyen, V. V., & Steele, J. M. (2015). Optimal online selection of a monotone subsequence: A central limit theorem. Stochastic Processes and Their Applications, 125(9), 3596–3622. https://doi.org/10.1016/j.spa.2015.03.009
Arlotto, A., V. V. Nguyen, and J. M. Steele. “Optimal online selection of a monotone subsequence: A central limit theorem.” Stochastic Processes and Their Applications 125, no. 9 (July 28, 2015): 3596–3622. https://doi.org/10.1016/j.spa.2015.03.009.
Arlotto A, Nguyen VV, Steele JM. Optimal online selection of a monotone subsequence: A central limit theorem. Stochastic Processes and their Applications. 2015 Jul 28;125(9):3596–622.
Arlotto, A., et al. “Optimal online selection of a monotone subsequence: A central limit theorem.” Stochastic Processes and Their Applications, vol. 125, no. 9, July 2015, pp. 3596–622. Scopus, doi:10.1016/j.spa.2015.03.009.
Arlotto A, Nguyen VV, Steele JM. Optimal online selection of a monotone subsequence: A central limit theorem. Stochastic Processes and their Applications. 2015 Jul 28;125(9):3596–3622.
Journal cover image

Published In

Stochastic Processes and their Applications

DOI

ISSN

0304-4149

Publication Date

July 28, 2015

Volume

125

Issue

9

Start / End Page

3596 / 3622

Related Subject Headings

  • Statistics & Probability
  • 4905 Statistics
  • 4901 Applied mathematics
  • 1502 Banking, Finance and Investment
  • 0104 Statistics
  • 0102 Applied Mathematics