Choosing either the best or the second best when the number of applicants is random
Gusein-Zade considered a version of the secretary problem in which we are allowed to make one choice and regard the choice as successful when the chosen applicant is either the best or the second best among all N applicants, where N is a given constant. Here we attempt to generalize his problem to the one in which N is a random variable whose distribution is known. The optimality equations are derived for any given distribution of N, but our main concerns are to investigate, in detail, the case where N is uniformly distributed on [1, m]. It can be shown that, in this case, the optimal policy has the form similar to that of the Gusein-Zade problem: pass s(1) - 1 applicants, then choose the relatively best applicant thereafter (if any), but beginning with the s(2) (greater than or equal to s(1))(th) stage, choose also the relatively second best applicant (if any). Some asymptotics concerning the critical numbers s(1) and s(2), and the success probability, are also obtained. (C) 2003 Elsevier Ltd. All rights reserved.
secretary problem optimal stopping unknown number of applicants relative ranks dynamic programming