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 $rr_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\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 $\tau_n(\alpha)$ selects $x_j$ such that $rr_n(x_{ j-1})-rr_n(x_j)\in\{ -1,1\}$. 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{ .}\]
Categories: math.PR math.CO