You play a game flipping a fair coin. You may stop after any trial, at which point you are paid in dollars the percentage of heads flipped. So if on the first trial you flip a head, you should stop and earn \$100 because you have 100% heads. If you flip a tail then a head, you could either stop and earn \$50, or continue on, hoping the ratio will exceed 1/2. This second strategy is superior.
A paper by Medina and Zeilberger (arXiv:0907.0032v2 [math.PR]) says that it is an unsolved
problem to determine if it is better to continue or stop after you have flipped 5 heads in 8 trials: accept \$62.50 or hope for more. It is easy to simulate this problem and it is clear
from even limited experimental data that it is better to continue (perhaps more than 70% chance you'll improve over \$62.50):
My question is basically: Why is this difficult to prove? Presumably it is not that difficult to write out an expression for the expectation of exceeding 5/8 in terms of the cumulative binomial distribution.
(5 Dec 2013). A paper on this topic was just published:
Olle Häggström, Johan Wästlund. "Rigorous computer analysis of the Chow-Robbins game." (pre-journal arXiv link). The American Mathematical Monthly, Vol. 120, No. 10, December 2013. (Jstor link). From the Abstract:
"In particular, we confirm that with 5 heads and 3 tails, stopping is optimal."