A sharp bound for winning within a proportion of the maximum of a sequence

DOI10.1007/S40590-018-0209-7zbMATH Open1439.60040arXiv1709.02416OpenAlexW2964035830WikidataQ129505944 ScholiaQ129505944MaRDI QIDQ2010856FDOQ2010856

Authors: José A. Islas Edit this on Wikidata

Publication date: 28 November 2019

Published in: Boletín de la Sociedad Matemática Mexicana. Third Series (Search for Journal in Brave)

Abstract: This note considers a variation of the full-information secretary problem where the random variables to be observed are independent and identically distributed. Consider $X_1,dots,X_n$ to be an independent sequence of random variables, let $M_n:=max{X}_1,dots,X_n$, and the objective is to select the maximum of the sequence. What is the maximum probability of "stopping at the maximum"? That is, what is the stopping time $au$ adapted to $X_1,\mathrm{...},X_n$ that maximizes $P(X_{au}=M_n)$? This problem was examined by Gilbert and Mosteller cite{GilMost} when in addition the common distribution is continuous. The optimal win probability in this case is denoted by $v_{n,max}^{\ast }$. What if it is desired to "stop within a proportion of the maximum"? That is, for $0<alpha<1$, what is the stopping rule $au$ that maximizes $P(X_{au}geqalpha{M}_n)$? In this note both problems are treated as games, it is proven that for any continuous random variable $X$, if $a{u}^{*}$ is the optimal stopping rule then $P(X_{a{u}^{\ast }}geqalpha{M}_n)geq{v}_{n,max}^{\ast }$, and this lower bound is sharp. Some examples and another interesting result are presented.

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

Recommendations

• A sharp lower bound for choosing the maximum of an independent sequence
• The secretary problem for a random walk
• Optimal sequential selection of a gambler assessed by the prophet
• scientific article; zbMATH DE number 3894189
• scientific article; zbMATH DE number 67296

zbMATH Keywords

choosing the maximum stopping timesharp inequalities for stochastic processes

Mathematics Subject Classification ID

Stopping times; optimal stopping problems; gambling theory (60G40)

Cites Work

• Who solved the secretary problem

Cited In (3)

• Title not available (Why is that?)
• A sharp lower bound for choosing the maximum of an independent sequence
• Title not available (Why is that?)

This page was built for publication: A sharp bound for winning within a proportion of the maximum of a sequence

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