Asymptotics and renewal approximation in the online selection of increasing subsequence

DOI10.3150/20-BEJ1294zbMath1469.60155arXiv1904.11213OpenAlexW3163876545MaRDI QIDQ2040096

Amirlan Seksenbayev, Alexander V. Gnedin

Publication date: 9 July 2021

Published in: Bernoulli (Search for Journal in Brave)

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

zbMATH Keywords

dynamic programmingmonotone subsequenceonline selectionrenewal approximation

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Continuous-time Markov processes on general state spaces (60J25) Point processes (e.g., Poisson, Cox, Hawkes processes) (60G55) Renewal theory (60K05)

Related Items (3)

Asymptotic expansions and strategies in the online increasing subsequence problem ⋮ Diffusion approximations in the online increasing subsequence problem ⋮ On sequential selection and a first passage problem for the Poisson process

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal online selection of a monotone subsequence: a central limit theorem
• A central limit theorem for the optimal selection process for monotone subsequences of maximum expected length
• Optimal sequential selection of a monotone sequence from a random sample
• Sequential selection of an increasing sequence from a multidimensional random sample.
• Optimal rules for the sequential selection of monotone subsequences of maximum expected length
• The key renewal theorem for a transient Markov chain
• Quickest online selection of an increasing subsequence of specified size
• Sequential selection of a monotone subsequence from a random permutation
• Renewal approximation for the absorption time of a decreasing Markov chain
• The Surprising Mathematics of Longest Increasing Subsequences
• ‘Wald's Lemma' for sums of order statistics of i.i.d. random variables
• A note on the selection of random variables under a sum constraint
• On the distribution of the length of the longest increasing subsequence of random permutations
• Renewal-type behavior of absorption times in Markov chains
• An adaptive O(log n)‐optimal policy for the online selection of a monotone subsequence from a random sample
• Optimal selection of stochastic intervals under a sum constraint
• A Note on Sequential Selection from Permutations
• Sequential selection of an increasing subsequence from a sample of random size
• Theory of Random Sets

This page was built for publication: Asymptotics and renewal approximation in the online selection of increasing subsequence