The secretary problem for a random walk (Q1104634)

The problem of picking the maximum of a sequence of n numbers was first considered by \textit{J. P. Gilbert} and \textit{F. Mosteller} [J. Am. Stat. Assoc. 61, 35-73 (1966)]. Since then, other work has appeared to extend their results, but all extensions to date have retained the assumption that the n numbers are observations on a sequence of independent random variables. This paper considers the problem of finding the maximum on a generalized one-dimensional random walk. The process considered is \(\{Y_ i\}_{i\geq 0}\), such that \(Y_ i=Y_{i-1}+X_ i\), where the \(X_ i's\) are i.i.d. continuous or discrete random variables, symmetric with respect to 0. Like in the usual secretary problem, the process must stop after n observations, and there is no recall. The objective is to maximize the probability of selecting the best (highest) of the n observations. The authors consider a class of stopping rules \(S_ 0,S_ 1,..\). such that \(S_ 0\equiv 0\), and \(S_ k\) is of the form ``let the first k-1 observations go by, and afterwards stop at the first observation which is better than all previous observations''. The main result of the paper states that the \(S_ k's\) are all optimal. Also, in the case of the ordinary random walk, where \(P(X_ i=1)=P(X_ i=-1)=0.5\), the probability of making the best selection if \(n=2m\) is large is approximately equal to 1/\(\sqrt{\pi m}\).