Refined Asymptotics in the Online Selection of an Increasing Subsequence

2018/08/20 by Amirlan Seksenbayev, Seksenbayev, Amirlan
Computer Science · Mathematics · #Algorithms and Data Compression #Bayesian Methods and Mixture Models #FOS: Mathematics #Optimization and Control (math.OC) #Random Matrices and Applications

paper · pdf · doi:10.48550/arxiv.1808.06300

openalex publication_date 2018/08/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let v_n be the maximum expected length of an increasing subsequence, which can be selected by an online nonanticipating policy from a random sample of size n. Refining known estimates, we obtain an asymptotic expansion of v_n up to a O(1) term. The method we use is based on detailed analysis of the dynamic programming equation, and is also applicable to the online selection problem with observations occurring at times of a Poisson process.

Related

• Asymptotics and Renewal Approximation in the Online Selection of Increasing Subsequence
• Diffusion Approximations in the Online Increasing Subsequence Problem
• On sequential selection and a first passage problem for the Poisson process
• Sequential Selection of a Monotone Subsequence from a Random Permutation
• Threshold rules for online sample selection