Oscillation criteria for stopping near the top of a random walk

Abstract

Consider the problem of maximizing the probability of stopping with one of the two highest values in a Bernoulli random walk with arbitrary parameter $p$ and finite time horizon $n$. Allaart \cite{Allaart} proved that the optimal strategy is determined by an interesting sequence of constants $\{p_n\}$. He conjectured the asymptotic behavior to be $1/2$. In this work the best lower bound for this sequence is found and more of its properties are proven towards solving the conjecture.