2016/12/31 by Lin, Yi-Shen, Hsiau, Shoou-Ren, Yao, Yi-Ching · 1 citation
#60G40 #62L15 #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.1701.00052
In the subject of optimal stopping, the classical secretary problem is concerned with optimally selecting the best of n candidates when their relative ranks are observed sequentially. This problem has been extended to optimally selecting the k-th best candidate for k≥ 2. While the optimal stopping rule for k=1,2 (and all n≥ 2) is known to be of threshold type (involving one threshold), we solve the case k=3 (and all n≥ 3) by deriving an explicit optimal stopping rule that involves two thresholds. We also prove several inequalities for p(k,n), the maximum probability of selecting the k-th best of n candidates. It is shown that (i) p(1,n)=p(n,n)>p(k,n) for 1