Duration of a secretary problem

From MaRDI portal





Consider the classical secretary problem (rank-based no-information case, equally probable arrival orders of ranks, one selection, no recall) with \(n\) candidates and let a success of the decision maker be defined by the selection of one of the \(s\) best candidates among the \(n\). This article studies the optimal rule (maximizing the success probability) as well as the expected time \(T\) of selection of a candidate. As the author shows, his stronger results extend and complement some of the results obtained by \textit{M. P. Quine} and \textit{J. S. Law} [ibid. 33, No. 3, 630-639 (1996; Zbl 0871.60037)] who were seemingly unaware of the author's previous work (co-authored) on this subject. The following alternative approach to determine \(E(T)\) seems worth mentioning, and may be new. Define a \(k\)-leader as a candidate which has relative rank \(<k\), and call a \(k\)-leader relevant if it appears at or after cutoff-time \(t_k\). Now note that \(T> t\) if and only if no relevant leader appears up to time \(t\). The probability of this event is just the value of the probability generating function of the counting variable \(N(t)=\#\)\{relevant leaders up to time \(t\)\} at 0. By Rényi's theorem on relative ranks, however, candidate \(j\), \(j> k\), is a \(k\)-leader with probability \(k/j\), independent of preceding ranks, so that the pgf of \(N(t)\) splits into a tractable product.











This page was built for publication: Duration of a secretary problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4358605)