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

DOI10.1016/J.SPA.2015.03.009MaRDI QIDQ491928zbMATH OpenOpenAlexWikidataFDO

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)

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

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)

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.

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

Cites work

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

Cited in

(19)

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