Secretary problem and two consecutive applicants with almost the same relative rank
Josef Rukavicka · arXiv (Cornell University) · 2021
We present a new variant of the secretary problem: Let $A_n$ be a totally ordered set of $n$ applicants. Given $P\subseteq A_n$ and $x\in A_n$, let $rr(P,x)=\vert\{z\in P \mid z\leq x\}\vert\mbox{ }$ be the \emph{relative rank of} $x$ \emph{with regard to} $P$, and let $rr_n(x)=rr(A_n,x)$. Let $x_1,x_2,\dots,x_n\in A_n$ be a random sequence of distinct applicants. The aim is to select $1<j\leq n$ such that $rr_n(x_{j-1})-rr_n(x_j)\in\{-1,1\}$. Let $\alpha$ be a real constant with $0<\alpha<1$. Suppose the following stopping rule $\tau_n(\alpha)$: reject first $\alpha n$ applicants and then select the first $x_j$ such that $rr(P_j,x_{j-1})-rr(P_j,x_j)\in\{-1,1\}$, where $P_j=\{x_i\mid 1\leq i\leq j\}$. Let $p_{n,\tau}(\alpha)$ be the probability that $rr_n(x_{j-1})-rr_n(x_j)\in\{-1,1\}$ under the condition that $x_j$ was selected with the rule $\tau_n(\alpha)$. We show that \[\lim_{n\rightarrow\infty}p_{n,\tau}(\alpha)\leq \lim_{n\rightarrow\infty}p_{n,\tau}\left(\frac{1}{2}\right)=\frac{1}{2}\mbox{.}\]