Choosing either the best or the second best when the number of applicants is random (Q597360)

From MaRDI portal
Revision as of 00:43, 5 March 2024 by Import240304020342 (talk | contribs) (Set profile property.)
scientific article
Language Label Description Also known as
English
Choosing either the best or the second best when the number of applicants is random
scientific article

    Statements

    Choosing either the best or the second best when the number of applicants is random (English)
    0 references
    0 references
    6 August 2004
    0 references
    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.
    0 references
    optimal stopping
    0 references
    best-choice secretary problem
    0 references
    unknown number of applicants
    0 references
    relative ranks
    0 references
    dynamic programming
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references