Convergence of the critical probabilities for stopping near the top of a random walk

Let $(S_n{)}_{n\ge 0}$ be a Bernoulli random walk with $P(X_i=1)=p$ and $P(X_i=-1)=q=1-p$, and let $M_n=\max \{S_0,\dots ,S_n\}$. We consider the semi-best selection problem of maximizing $P(M_N-S_{\tau }\le 1)$ over stopping times $\tau \le N$. Allaart showed that the optimal decision in the critical state $(n,1)$ is determined by a sequence of critical probabilities $\{p_n\}$, and conjectured that $p_n\to 1\mathrm{/}2$. We prove this conjecture. For every fixed $p<1\mathrm{/}2$, the stopping value converges to $\nu =1-(p\mathrm{/}q{)}^2$, while the continuation value converges to $2p\nu$. Since $2p\nu <\nu$, stopping is optimal in state $(n,1)$ for all sufficiently large $n$. Together with the known bound $p_n<1\mathrm{/}2$ for $n\ge 4$, this yields ${\lim }_{n\to \mathrm{\infty }}{p}_n=1\mathrm{/}2$.