46
$\begingroup$

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):
alt text
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."

  • 0
    Would you go on with a game when winning in 70% of the cases a little money and loosing a lot in the remaining 30% of the cases?2010-10-06
  • 7
    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...2010-10-06
  • 0
    @jug: Yes, that does have to be factored into any decision. But it certainly can be quantified precisely.2010-10-06
  • 0
    @Qiaochu: Point well taken! But this one feels different to me, in that one presumably can write out (although I haven't) explicit expressions.2010-10-06
  • 6
    @Joseph O'Rourke: have you tried actually doing that? I think it will end up being hard.2010-10-06
  • 0
    @Qiaochu: Perhaps that is the only way to answer my question: Write out the expectation explicitly. When time permits I'll give it a try. Or if anyone else is facile in this domain, you are welcome to lend a hand...2010-10-06
  • 1
    @Joseph: Thanks to the law of the iterated logarithm you are guaranteed \$50. But what will your strategy be for continuing or stopping after having drawn $k$ after $n$ throws? The expectation depends on your strategy, which has to be a function of $k$ and $n$. Your graph hides the fact that you have to stop without knowing the future.2010-10-06
  • 0
    @jug: One possible strategy would be: Stop when the current ratio exceeds the expected future maximum ratio. You are right that there is more than one strategy!2010-10-06
  • 1
    @Joseph: What do you mean with the expected future maximum ration?2010-10-06
  • 0
    From my point you want to predict the peak for the next X coin flips given your current score and stop when you hit it. Finding the optimum balance between value of the peak and probablity of exceeding or hitting it seems challenging.2010-10-06
  • 1
    What if you know in advance the coin will come up heads p% of the time, even for p!=50? That's sort of the question I asked at: http://quant.stackexchange.com/questions/2172/probability-distribution-of-maximum-value-of-binary-option (and no answers there yet either)2014-02-01

4 Answers 4