A unified approach to a class of best choice problems with an unknown number of options (Q802201)

This paper generalizes the classical secretary problem in the following two ways: 1) The arrival times \(Z_ 1,Z_ 2,...\), of the applicants are independent random variables which have a common distribution function F defined on [0,t]. 2) The total number of applicants is a random variable N, of unknown distribution. In the classical version of the problem, the strategy which maximizes the probability of selecting the best applicant is of the form: (1) observe and rank all applicants arriving before time x, without making a selection, (2) after time x, select the first applicant who is better than all previously seen applicants. This family of strategies (called x-strategies) also plays an important role in the modified problem. The following results are obtained: 1) There is an optimal value \(x^*\), which maximizes the probability of selecting the best applicant amongst all x - strategies; moreover, as N tends to infinity a.s., \(x^*\) tends to \(F^{-1}(e^{-1)}\). 2) This strategy has success probability \(>e^{-1}\), regardless of the distribution of N. 3) There is no other strategy having property 2. 4) The \(x^*\)- strategy is asymptotically optimal. Note that in the case where the distribution of N is known, the class of ''good'' strategies is not necessarily the class of x-strategies.