Optimal Sequential Selection of a Monotone Sequence from a Random Sample.

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)(to the 1/2 power). We prove that it is possible to make sequential choices which give an increasing subsequence of expected length asymptotic to (2n)(to the 1/2 power). Moreover, this rate of increase is proved to be asymptotically best possible. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 10, 1981
Accession Number
ADA109661

Entities

People

  • J. Michael Steele
  • Stephen M. Samuels

Organizations

  • Stanford University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Computer Simulations
  • Dynamic Programming
  • Equations
  • Inequalities
  • Integral Equations
  • Integrals
  • Military Research
  • New York
  • Observation
  • Probability
  • Random Variables
  • Sequences
  • Statistical Samples
  • Statistics
  • Theorems
  • United States

Fields of Study

  • Mathematics

Readers

  • Neural Network Machine Learning.
  • Regression Analysis.