Choosing either the best or the second best when the number of applicants is random (Q597360): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/s0898-1221(03)90120-9 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2008619552 / rank | |||
Normal rank |
Latest revision as of 12:03, 30 July 2024
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
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