Sequential selection of a monotone subsequence from a random permutation

DOI10.1090/PROC/13104MaRDI QIDQ2821757zbMATH OpenOpenAlexFDO

Authors Peichao Peng, J. Michael Steele

Publication date 23 September 2016

Published in Proceedings of the American Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

Markov decision problemmonotone subsequence problemnonlinear recursiononline selectionprophet inequalitysequential selection

Mathematics Subject Classification ID

Combinatorial probability (60C05) Stopping times; optimal stopping problems; gambling theory (60G40) Dynamic programming (90C39) Markov and semi-Markov decision processes (90C40)

Abstract: We find a two term asymptotic expansion for the optimal expected value of a sequentially selected monotone subsequence from a random permutation of length n. A striking feature of this expansion is that tells us that the expected value of optimal selection from a random permutation is quantifiably larger than optimal sequential selection from an independent sequences of uniformly distributed random variables; specifically, it is larger by at least (1/6)log n +O(1).

Recommendations

• A Note on Sequential Selection from Permutations
• Optimal sequential selection of a unimodal subsequence of a random sequence
• 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 Sequential Selection from Permutations
• scientific article; zbMATH DE number 700091 (Why is no real title available?)
• scientific article; zbMATH DE number 3349081 (Why is no real title available?)
• On the distribution of the length of the longest increasing subsequence of random permutations
• Online algorithms. The state of the art
• Optimal online selection of a monotone subsequence: a central limit theorem
• Optimal rules for the sequential selection of monotone subsequences of maximum expected length
• Optimal selection of stochastic intervals under a sum constraint
• Optimal sequential selection of a monotone sequence from a random sample
• Quickest online selection of an increasing subsequence of specified size
• Sequential selection of an increasing subsequence from a sample of random size
• Stochastic optimal control. The discrete time case
• The Bruss-Robertson inequality: elaborations, extensions, and applications
• The surprising mathematics of longest increasing subsequences
• ‘Wald's Lemma' for sums of order statistics of i.i.d. random variables

Cited in

(8)

• 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 BRS-inequality and its applications
• Asymptotics and renewal approximation in the online selection of increasing subsequence
• Asymptotic expansions and strategies in the online increasing subsequence problem
• Sequential selection of an increasing subsequence from a random sample with geometrically distributed sample-size
• Optimal sequential selection of a unimodal subsequence of a random sequence
• A Note on Sequential Selection from Permutations

This page was built for publication: Sequential selection of a monotone subsequence from a random permutation

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