# Why is this coin-flipping probability problem unsolved?

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."

-
There are plenty of problems which are easy to simulate and to guess an answer to where rigorously proving that answer is wide open, e.g. things involving primes, self-avoiding random walks... – Qiaochu Yuan Oct 6 '10 at 13:00
@Joseph O'Rourke: have you tried actually doing that? I think it will end up being hard. – Qiaochu Yuan Oct 6 '10 at 13:18