The hiring problem with rank-based strategies (Q2279320)

This paper studies the hiring problem with rank-based strategies. Given a sequence of integers \(r(m)\) with \(m\ge0\) satisfying \(r(0)=1\) and \(r(m)\le r(m+1)\le r(m)+1\) for \(m\ge0\). If so far \(m\ge0\) candidates have been accepted, then (if \(r(m)\le m\)) the next candidates is accepted if its value is above the \(r(m)\)-th best value of the ones already accepted. If \(r(m)=m+1\), we always accept the next candidate. Let \(y_m=\sum_{k=1}^m\frac{1}{r(k)}-\sum_{l=2}^{r(m)}\frac{1}{l}\) and \(\lambda_m=\sum_{k=0}^{m-1}e^{y_k}\) for \(m\ge0\). Define \(M_n\) as the number of accepted candidates among the first \(n\) examined and \(N_m\) the number of candidates examined until \(m\) are accepted. Some limit theorems are provided for these quantities. In particular, if \(\sum_{m=1}^{\infty}r(m)^{-2}<\infty\), then it is shown that \(N_m/\lambda_m\rightarrow e^Z\) almost surely as \(m\rightarrow\infty\), where \(Z=\sum_{k=1}^{\infty}\frac{1+r(k-1)-r(k)}{r(k)}(E_k-1)\) and \(\{E_k\}_{k=1}^{\infty}\) are i.i.d. \(\mathrm{Exp}(1)\) variables.