An experimental mathematics perspective on the old, and still open, question of when to stop?
Luis A. Medina, Doron Zeilberger · Contemporary mathematics - American Mathematical Society · 2010
In a delightful and insightful recent “general ” article [4], the great probabilist and master expositor Theodore Hill described, amongst numerous other intriguing things, a more than forty-year-old open problem, due to Y.H. Chow and Herbert Robbins [2] that goes as follows: Toss a fair coin repeatedly and stop whenever you want, receiving as a reward the average number of heads accrued at the time you stop. If your first toss is a head, and you stop, your reward is 1 Kruegerrand. Since you can never have more than 100 percent heads, it is clearly optimal to stop in that case. If the first toss is a tail, on the other hand, it is clearly best not to stop, since your reward would be zero... Then Ted Hill goes on to comment that if the first toss is a tail and the second is a head, then it is good to go, since by the law of large numbers, you would eventually do (at least slightly) better than one half. [It turns out that in this case of one head and one tail, the expected gain of continuing the game is larger than 0.6181]. Hill further claims that it is optimal to stop if the initial sequence is tail-headhead.