Optimal online selection of an alternating subsequence: a central limit theorem
From MaRDI portal
Abstract: We analyze the optimal policy for the sequential selection of an alternating subsequence from a sequence of independent observations from a continuous distribution , and we prove a central limit theorem for the number of selections made by that policy. The proof exploits the backward recursion of dynamic programming and assembles a detailed understanding of the associated value functions and selection rules.
Recommendations
- Online Selection of Alternating Subsequences from a Random Sample
- Optimal online selection of a monotone subsequence: a central limit theorem
- On-line selection of \(c\)-alternating subsequences from a random sample
- An adaptive O( n)-optimal policy for the online selection of a monotone subsequence from a random sample
- A central limit theorem for the optimal selection process for monotone subsequences of maximum expected length
Cites work
- A central limit theorem for the optimal selection process for monotone subsequences of maximum expected length
- A Note on Sequential Selection from Permutations
- A probabilistic approach to the asymptotics of the length of the longest alternating subsequence
- A survey of alternating permutations
- Dynamic Programming and Decision Theory
- scientific article; zbMATH DE number 1834589 (Why is no real title available?)
- scientific article; zbMATH DE number 5204618 (Why is no real title available?)
- scientific article; zbMATH DE number 3383344 (Why is no real title available?)
- Local extrema in random permutations and the structure of longest alternating subsequences
- Longest alternating subsequences of permutations
- Markov Chains and Stochastic Stability
- On the limiting distribution for the length of the longest alternating sequence in a random permutation
- On the Markov chain central limit theorem
- Online Selection of Alternating Subsequences from a Random Sample
- 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
- Secretary Problems via Linear Programming
- Sequential selection of an increasing sequence from a multidimensional random sample.
- Sequential selection of an increasing subsequence from a random sample with geometrically distributed sample-size
- Sequential selection of an increasing subsequence from a sample of random size
- Submodular secretary problem and extensions
- The secretary problem of minimizing the expected rank: a simple suboptimal approach with generalizations
- Time series: theory and methods
Cited in
(11)- On-line selection of \(c\)-alternating subsequences from a random sample
- Asymptotics and renewal approximation in the online selection of increasing subsequence
- Reading policies for joins: an asymptotic analysis
- A central limit theorem for temporally nonhomogenous Markov chains with applications to dynamic programming
- Markov decision problems where means bound variances
- Online Selection of Alternating Subsequences from a Random Sample
- An adaptive O( n)-optimal policy for the online selection of a monotone subsequence from a random sample
- Optimal online selection of a monotone subsequence: a central limit theorem
- Longest Increasing Subsequences of Randomly Chosen Multi-Row Arrays
- A central limit theorem for the optimal selection process for monotone subsequences of maximum expected length
- A central limit theorem for repeating patterns
This page was built for publication: Optimal online selection of an alternating subsequence: a central limit theorem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5169506)
