Optimal Sequential Selection of a Monotone Sequence From a Random Sample
Loading...
Embargo Date
Related Collections
Degree type
Discipline
Subject
monotone subsequence
optimal stopping
subadditive process
Physical Sciences and Mathematics
optimal stopping
subadditive process
Physical Sciences and Mathematics
Funder
Grant number
License
Copyright date
Distributor
Related resources
Contributor
Abstract
The length of the longest monotone increasing subsequence of a random sample of size n is known to have expected value asymptotic to 2n1/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.
Advisor
Date Range for Data Collection (Start Date)
Date Range for Data Collection (End Date)
Digital Object Identifier
Series name and number
Publication date
1981-04-01
Journal title
The Annals of Probability
Volume number
Issue number
Publisher
Publisher DOI
Comments
At the time of publication, author J. Michael Steele was affiliated with Stanford University. Currently, he is a faculty member at the Statistics Department at the University of Pennsylvania.