Optimal stopping problems such as the Secretary Problem are generally solved dynamically with a Bellman equation. However, a simpler solution exists. Consider the roll of a fair die, where there are n total rolls and you win a prize if you stop the final time a 6 is rolled. The probability of exactly one 6 existing in the final k rolls is k(1/6)^1(5/6)^(k-1) by the binomial theorem. This is maximized when k=6. Intuitively, then, one should reject every roll until only 6 remain, and then stop when a 6 is rolled (if such an event occurs). It turns out that this intuition leads to a simple algorithm for optimal stopping with independent events: begin with the final event, and sum the odds (NOT the probability, but p/(1-p)) of a “success” occurring until that sum equals one. Every event for which the sum is one or higher is should be rejected automatically. After that, select the first event where a success occurs. A simple solution for the probability of this strategy winning is also proven. This paper proves that even intuitively obvious mathematical ideas have not all been proven: it was published in Annals of Probability in 2000!
“Sum the Odds to One and Stop,” Bruss (2000)