Choosing either the best or the second best when the number of applicants is random (Q597360): Difference between revisions

The paper investigates a generalized variant of the secretary problem [\textit{S. M. Gusein-Zade}, Theory Probab. Appl. 11, 472--476 (1966); translation fromTeor. Veroyatn. Primen. 11, 534--537 (1966; Zbl 0203.20405)], which is announced as follows: A set of \(N\) applicants (1 being the best and \(N\) being the worst) appear before use one at a time in random order, with all \(N!\) permutations equally likely. The rank of each applicant relative to the preceding ones is noticed, and (based on the observed rank) decided to choose the best (or the second best) or to pass over to the next (if any). No recall of the previous applicants is allowed, and the choice is considered to be successful if the chosen applicant is either the best or the second best among all. While in the secretary problem \(N\) is a known natural number, the present paper considers \(N\) to be a random variable whose distribution is known. The optimality equations are derived for any given distribution on \(N\), but the authors concentrate on the case when \(N\) is uniformly distributed on the interval of integers \([1, m]\). For this situation, the authors prove that the optimal policy has the form similar to the solution of the more particular secretary problem. Namely, to pass the (\(s_1-1)\) applicants, then to choose the relatively best applicant thereafter (if any), but beginning with the \(s_2\)th stage \((s_2 \geq s_1)\) to choose also the relatively second best applicant (if any). A certain asymptotic result concerning the critical numbers \(s_1\) and \(s_2\), and the success probability when \(m\) tends to infinity is also provided.