2017/09/07 by José A. Islas, Islas, José A.
Computer Science · Decision Sciences · #Auction Theory and Applications #Cryptography and Data Security #FOS: Mathematics #Optimization and Search Problems #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.1709.02416
openalex publication_date 2017/09/07 · openalex created_date 2022/08/06 · openalex updated_date 2026/07/28
This note considers a variation of the full-information secretary problem\nwhere the random variables to be observed are independent and identically\ndistributed. Consider X1,\…,Xn to be an independent sequence of random\nvariables, let Mn:=\max X1,\…,Xn , and the objective is to select the\nmaximum of the sequence. What is the maximum probability of "stopping at the\nmaximum"? That is, what is the stopping time \τ adapted to X1,...,Xn\nthat maximizes P(X\τ=Mn)? This problem was examined by Gilbert and\nMosteller citeGilMost when in addition the common distribution is\ncontinuous. The optimal win probability in this case is denoted by\nvn,max^*. What if it is desired to "stop within a proportion of the\nmaximum"? That is, for 0<\α<1, what is the stopping rule \τ that\nmaximizes P(X\τ \≥ \α Mn)? In this note both problems are treated\nas games, it is proven that for any continuous random variable X, if \τ^*\nis the optimal stopping rule then P(X\τ^* \≥ \α Mn)\≥\nvn,max^*, and this lower bound is sharp. Some examples and another\ninteresting result are presented.\n