Weber’s optimal stopping problem and generalizations

One way to interpret the classical secretary problem (CSP) is to consider it as a special case of the following problem. We observe n independent indicator variables I1,I2,…,In sequentially and we try to stop on the last variable being equal to 1. If Ik=1 it means that the kth observed secretary has smaller rank than all previous ones (and therefore is a better secretary). In the CSP, pk=E(Ik)=1/k and the last k with Ik=1 stands for the best candidate. The more general problem of stopping on a last “1” was studied by Bruss (2000). In what we will call Weber’s problem the indicators are replaced by random variables which can take more than 2 values. The goal is now to maximize the probability of stopping on a value appearing for the last time in the sequence. Notice that we do not fix in advance the value taken by the variable on which we stop.