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!
-
Follow
Following
Already have a WordPress.com account? Log in now.
A Fine Theorem 
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?
i think if you roll 6 on 6th to last roll, you are indifferent between continuing
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