Optimal sequential selection of a unimodal subsequence of a random sequence

DOI10.1017/S0963548311000411MaRDI QIDQ3103629zbMATH OpenOpenAlexFDO

Authors Alessandro Arlotto, J. Michael Steele

Publication date 8 December 2011

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

optimal sequential selection

Mathematics Subject Classification ID

Combinatorial probability (60C05) Stopping times; optimal stopping problems; gambling theory (60G40) Optimal stopping in statistics (62L15)

Abstract: We consider the problem of selecting sequentially a unimodal subsequence from a sequence of independent identically distributed random variables, and we find that a person doing optimal sequential selection does within a factor of the square root of two as well as a prophet who knows all of the random observations in advance of any selections. Our analysis applies in fact to selections of subsequences that have d+1 monotone blocks, and, by including the case d=0, our analysis also covers monotone subsequences.

Recommendations

• Sequential selection of a monotone subsequence from a random permutation
• Online Selection of Alternating Subsequences from a Random Sample
• Optimal rules for the sequential selection of monotone subsequences of maximum expected length
• A central limit theorem for the optimal selection process for monotone subsequences of maximum expected length
• Optimal online selection of a monotone subsequence: a central limit theorem

Cites work

• 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
• Long unimodal subsequences: a problem of F. R. K. Chung
• On the distribution of the length of the longest increasing subsequence of random permutations
• On unimodal subsequences
• Optimal rules for the sequential selection of monotone subsequences of maximum expected length
• Optimal sequential selection of a monotone sequence from a random sample
• Sequential selection of an increasing subsequence from a sample of random size
• Stochastic optimal control. The discrete time case
• The height of a random partial order: Concentration of measure
• ‘Wald's Lemma' for sums of order statistics of i.i.d. random variables

Cited in

(11)

• Optimal selection of the \(k\) best of a sequence with \(k\) stops
• The BRS-inequality and its applications
• Quickest online selection of an increasing subsequence of specified size
• Sequential selection of a monotone subsequence from a random permutation
• Markov decision problems where means bound variances
• Optimal Sequential selection of n random variables under a constraint
• Optimal online selection of a monotone subsequence: a central limit theorem
• Sequential search beats best-of-N search
• Optimal online selection of an alternating subsequence: a central limit theorem
• Longest Increasing Subsequences of Randomly Chosen Multi-Row Arrays
• The sequence selection properties of C_p(X)

This page was built for publication: Optimal sequential selection of a unimodal subsequence of a random sequence

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