Prophet-type inequalities for multi-choice optimal stopping

DOI10.1016/0304-4149(87)90029-9MaRDI QIDQ1089995zbMATH OpenOpenAlexWikidataFDO

Authors D. P. Kennedy

Publication date 1987

Published in Stochastic Processes and their Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-4149(87)90029-9

zbMATH Keywords

multiple optimal stoppingprophet inequality

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Stopping times; optimal stopping problems; gambling theory (60G40) Optimal stopping in statistics (62L15)

Review text

Let \(X_ 1,X_ 2,..\). be independent random variables taking values in [0,1], and let \(v_ r=\sup E(X_{\tau_ 1}+X_{\tau_ 2}+...+X_{\tau_ r})\), where the supremum extends over all stopping times \(\tau_ 1<\tau_ 2<...<\tau_ r\). The author proves inequalities of the form E(sup \(X_ n)\leq F_ r(v_ r).\) He gives an explicit formula for the best possible function \(F_ r\). He also derives best possible constants \(1\leq C_ r\leq 2\) with E(sup \(X_ n)\leq C_ rv_ r\). It is known that \(C_ 1=2\). The constants \(C_ r\) decrease and tend to one rapidly. E.g. \(C_ 2=1.1716\).

Recommendations

• Prophet inequalities for averages of independent non-negative random variables
• scientific article; zbMATH DE number 4062279
• Ratio Prophet Inequalities for the GeneralS_n/nProblem
• scientific article; zbMATH DE number 67296
• Optimal stopping of independent random variables and maximizing prophets

Cites work

• Additive Comparisons of Stop Rule and Supremum Expectations of Uniformly Bounded Independent Random Variables
• Comparison of optimal value and constrained maxima expectations for independent random variables
• Comparisons of stop rule and supremum expectations of i.i.d. random variables
• Note on Shift-Invariant Sets
• Optimal stopping of independent random variables and maximizing prophets
• Prophet Inequalities and Order Selection in Optimal Stopping Problems
• Ratio comparisons of supremum and stop rule expectations
• Semiamarts and finite values

Cited in

(27)

• Prophet inequalities for averages of independent non-negative random variables
• A note on monotonicity in optimal multiple stopping problems
• Matroid prophet inequalities and applications to multi-dimensional mechanism design
• Why is one choice different?
• Prophet inequalities for cost of observation stopping problems
• A prophet inequality for \(L^p\)-bounded dependent random variables
• A prophet inequality for L^2-martingales
• Simple ratio prophet inequalities for a mortal with multiple choices
• Online network design with outliers
• Ratio Prophet Inequalities for the GeneralS_n/nProblem
• Prophet secretary
• Continuity Properties of Optimal Multiple Stopping Value
• Comparison of optimal value and constrained maxima expectations for independent random variables
• Expectation inequalities associated with prophet problems¹
• scientific article; zbMATH DE number 4062279 (Why is no real title available?)
• scientific article; zbMATH DE number 67295 (Why is no real title available?)
• scientific article; zbMATH DE number 3998915 (Why is no real title available?)
• Posted price mechanisms and optimal threshold strategies for random arrivals
• Prophet matching with general arrivals
• Hiring secretaries over time: the benefit of concurrent employment
• Prophet secretary
• Prophet Inequalities for I.I.D. Random Variables with Random Arrival Times
• Optimal stopping problems with generalized objective functions
• The importance of knowing the arrival order in combinatorial Bayesian settings
• Prophet secretary for combinatorial auctions and matroids
• Order-competitive ratio
• Comparison of threshold stop rules and maximum for independent nonnegative random variables

This page was built for publication: Prophet-type inequalities for multi-choice optimal stopping

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