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

DOI10.1016/J.SPA.2015.03.009zbMATH Open1327.60053arXiv1408.6750OpenAlexW2004912523WikidataQ29301140 ScholiaQ29301140MaRDI QIDQ491928FDOQ491928

Authors: Alessandro Arlotto, Vinh V. Nguyen, J. Michael Steele 

Publication date: 19 August 2015

Published in: Stochastic Processes and their Applications (Search for Journal in Brave)

Abstract: 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 $p{i}_n^{\ast }$ that is optimal in the sense that it maximizes the expected value of $L_n(p{i}_n^{\ast })$, the number of selected observations. We investigate the distribution of $L_n(p{i}_n^{\ast })$; in particular, we obtain a central limit theorem for $L_n(p{i}_n^{\ast })$ 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.

Full work available at URL: https://arxiv.org/abs/1408.6750

Recommendations

• A central limit theorem for the optimal selection process for monotone subsequences of maximum expected length
• Sequential selection of an increasing subsequence from a sample of random size
• Optimal online selection of an alternating subsequence: a central limit theorem
• An adaptive \(O(\log n)\)-optimal policy for the online selection of a monotone subsequence from a random sample
• Optimal rules for the sequential selection of monotone subsequences of maximum expected length

zbMATH Keywords

central limit theoremdynamic programmingmartingaleBellman equationMarkov decision problemmonotone subsequencenon-homogeneous Markov chainoptimal online selection

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Martingales with discrete parameter (60G42) Combinatorial optimization (90C27) Dynamic programming (90C39) Functional limit theorems; invariance principles (60F17) Combinatorial probability (60C05) Stopping times; optimal stopping problems; gambling theory (60G40) Markov and semi-Markov decision processes (90C40)

Cites Work

• Analytic combinatorics
• Dependent central limit theorems and invariance principles
• Title not available (Why is that?)
• On the distribution of the length of the longest increasing subsequence of random permutations
• Tauberian Theory
• Title not available (Why is that?)
• Optimal sequential selection of a monotone sequence from a random sample
• Title not available (Why is that?)
• Martingale Central Limit Theorems
• A variational problem for random Young tableaux
• Subadditive ergodic theory
• The height of a random partial order: Concentration of measure
• Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
• Title not available (Why is that?)
• The surprising mathematics of longest increasing subsequences
• ‘Wald's Lemma' for sums of order statistics of i.i.d. random variables
• Analytical depoissonization and its applications
• Optimal rules for the sequential selection of monotone subsequences of maximum expected length
• On increasing subsequences of random permutations
• Title not available (Why is that?)
• Markov decision problems where means bound variances
• Optimal sequential selection of a unimodal subsequence of a random sequence
• A note on the selection of random variables under a sum constraint
• Sequential selection of an increasing subsequence from a sample of random size
• A central limit theorem for the optimal selection process for monotone subsequences of maximum expected length
• Descending subsequences of random permutations

Cited In (19)

• Optimal sequential selection of a unimodal subsequence of a random sequence
• Online Selection of Alternating Subsequences from a Random Sample
• Logarithmic regret in the dynamic and stochastic knapsack problem with equal rewards
• A unified approach for solving sequential selection problems
• On-line scheduling with monotone subsequence constraints
• Online Scheduling with Increasing Subsequence Serving Constraint
• Optimal online selection of an alternating subsequence: a central limit theorem
• An adaptive \(O(\log n)\)-optimal policy for the online selection of a monotone subsequence from a random sample
• Asymptotics and renewal approximation in the online selection of increasing subsequence
• The BRS-inequality and its applications
• Diffusion approximations in the online increasing subsequence problem
• Asymptotic expansions and strategies in the online increasing subsequence problem
• Optimal rules for the sequential selection of monotone subsequences of maximum expected length
• Sequential selection of an increasing subsequence from a random sample with geometrically distributed sample-size
• Quickest online selection of an increasing subsequence of specified size
• Sequential selection of a monotone subsequence from a random permutation
• On-line Scheduling with a Monotonous Subsequence Constraint
• A central limit theorem for the optimal selection process for monotone subsequences of maximum expected length
• On-line selection of \(c\)-alternating subsequences from a random sample

This page was built for publication: Optimal online selection of a monotone subsequence: a central limit theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q491928)