Secretary problem and two almost the same consecutive applicants

Abstract

We present a new variant of the secretary problem. Let $A$ be a totally ordered set of $n$ \emph{applicants}. Given $P\subseteq A$ and $x\in A$, 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 $r{r}_n(x)=rr(A,x)$. Let $x_1,x_2,\dots ,x_n\in A$ be a random sequence of distinct applicants. The aim is to select $1<j\le n$ such that $r{r}_n(x_{j-1})-r{r}_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\le i\le j\}$. Let $p_{n,\tau }(\alpha )$ be the probability that ${\tau }_n(\alpha )$ selects $x_j$ such that $r{r}_n(x_{j-1})-r{r}_n(x_j)\in \{-1,1\}$. We show that \[\lim_{n\rightarrow\infty}p_{n,τ}(α)\leq \lim_{n\rightarrow\infty}p_{n,τ}\left(\frac{1}{2}\right)=\frac{1}{2}\mbox{.}\]