“Sum the Odds to One and Stop,” Bruss (2000)

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!

http://projecteuclid.org/DPubS/Repository…

Advertisements

3 thoughts on ““Sum the Odds to One and Stop,” Bruss (2000)

  1. mermel says:

    i dont think that intuition is obviously correct. consider observing a 6 on the 7th to last roll, you dont stop if P(exactly one 6)>P(no sixes). its not obvious to me that this always happens right before the roll that maximizes the P(exactly one success). maybe it is the case in binomial but not other distributions?

  2. mermel says:

    i think if you roll 6 on 6th to last roll, you are indifferent between continuing

    • Bruss says:

      Answer to Mermel conerning Bruss’ odds algorithm:

      That’s right, indifferent to 6 or 5. The probability is the same, because the sum
      of the odds (each (1/6/(1-1/6))=1/5 is an integer. There are always two
      optimal thresholds (here 5 and 6) if the odds add up exactly to 1.
      ThB

Comments are closed.

%d bloggers like this: