Optimal Sequential Selection of a Monotone Sequence From a Random Sample

1981/12/01 by Stephen M. Samuels, John Steele · 3 citations
Computer Science · Mathematics · #Algorithms and Data Compression #Optimization and Search Problems #Stochastic processes and statistical mechanics #Mathematics #Subsequence #Monotone polygon #Sequence (biology) #Longest increasing subsequence #Combinatorics #Selection (genetic algorithm) #Sample (material) #Sample size determination #Discrete mathematics #Applied mathematics #Statistics #Mathematical analysis

paper · pdf · doi:10.1214/aop/1176994265

openalex publication_date 1981/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11

Abstract

The length of the longest monotone increasing subsequence of a random sample of size n is known to have expected value asymptotic to 2n^1/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.

Cited by

• Optimal rules for the sequential selection of monotone subsequences of maximum expected length
• A central limit theorem for the optimal selection process for monotone subsequences of maximum expected length
• Longest increasing subsequence [wikipedia]