The odds algorithm based on sequential updating and its performance

Let I_1, I_2, ..., I_n be independent indicator functions on some probability space (Ω, A, P). We suppose that these indicators can be observed sequentially. Furthermore, let T be the set of stopping times on (I_k), k = 1,..., n, adapted to the increasing filtration (F_k), where F_k = σ (I_1,..., I_k). The odds algorithm solves the problem of finding a stopping time t ϵ T which maximises the probability of stopping on the last I_k = 1, if any. To apply the algorithm, we only need the odds for the events {I_k = 1), that is, r_k = P_k/ (1 – P_k), where p_k = E(I_k), k = 1,2,..., n. The goal of this paper is to offer tractable solutions for the case where the p_k are unknown and must be sequentially estimated. The motivation is that this case is important for many real-world applications of optimal stopping. We study several approaches to incorporate sequential information. Our main result is a new version of the odds algorithm based on online observation and sequential updating. Questions of speed and performance of the different approaches are studied in detail, and the conclusiveness of the comparisons allows us to propose always using this algorithm to tackle selection problems of this kind.