# When to stop in this coin toss game?

Suppose you play the following game: You toss a fair coin. If you get heads, a hundred dollars are added to your reward. If you get tails, however, the game is stopped and you do not get anything at all. After each throw you can decide, whether you want to take the money or keep playing. When should you stop to play the game in order to get the maximum expected reward and why? What happens if the coin is biased and has an 80% chance of showing heads?

-
Of course you mean maximum expected reward. The actual reward is unbounded although the probability of very long strings of heads gets small quickly, less quickly for a biased coin favoring heads. – Michael Chernick Sep 13 '12 at 19:24
Thanks, I changed that. – Ignavia Sep 13 '12 at 19:26
See what you think of the answer I have just given. – Michael Chernick Sep 13 '12 at 19:55

Let $p$ be the probability that the coin comes up heads. Suppose that you’ve tossed a head $n$ times. If you play one more time, your expected payoff is $100(n+1)p$; if this is less than the $100n$ that you’ve won so far, you shouldn’t play again. The inequality $100(n+1)p<100n$ boils down to $n(1-p)>p$, or $n>\frac{p}{1-p}$; if $n=\frac{p}{1-p}$, your expected payoff is equal to your current winnings. Thus, if $n\ge\left\lfloor\frac{p}{1-p}\right\rfloor+1$, you should not play again. If $n=\frac{p}{1-p}$, you can play again or not. And if $n<\frac{p}{1-p}$, you should play again. We can get a slightly nicer expression for the cutoff: you should stop when $n$ reaches

$$\left\lfloor\frac{p}{1-p}\right\rfloor+1=\left\lfloor\frac1{1-p}-1\right\rfloor+1=\left\lfloor\frac1{1-p}\right\rfloor\;.$$

For a fair coin, with $p=\frac12$, this says that if $n>1$, you shouldn’t play again: if you toss heads once, you can go ahead and try again or not, as you please, but if you toss heads twice, you should quit. If $p=4/5$, the cutoff is $n>4$: if you’ve managed to toss four heads in a row, you can try again or not, but if you’ve managed five, quit.

To see how this relates to Sam’s calculus-based answer, start with the Maclaurin series for $\ln(1-x)$:

$$\ln p=-\sum_{n\ge 1}\frac{(1-p)^n}n\;,$$

so

$$\frac1{-\ln p}=\frac1{\sum_{n\ge 1}\frac{(1-p)^n}n}=\frac1{1-p}\cdot\frac1{1+\frac12(1-p)+\frac13(1-p)^2+\ldots}\;.$$

Clearly $1<1+\frac12(1-p)+\frac13(1-p)^2+\ldots<\sum_{k\ge 0}(1-p)^k=\frac1p$, so

$$\frac{p}{1-p}<\frac1{-\ln p}<\frac1{1-p}=\frac{p}{1-p}+1\;.$$

-
+1 for agreeing with me and adding more mathematics – Michael Chernick Sep 13 '12 at 20:50
Can someone please explain the factorisation in the first (and other) answers? I can't see how 100(n+1)p<100n boils down to n>p/(1−p). – timboj May 24 '13 at 14:45
@timboj: First divide through by $100$ to bet $(n+1)p<n$. Multiply out the lefthand side to get $np+p<n$. Subtract $np$ from both sides: $p<n-np=n(1-p)$. Now divide through by $1-p$. – Brian M. Scott May 24 '13 at 15:30

If the coin lands on heads with probability $p$, then your expected reward at time $n$ is $E(n)=p^n\cdot n\cdot 100$, so the question amounts to asking when this function is maximized. Taking derivatives in $n$ gives:

$0=E'(n)=100(np^n\ln(p)+p^n)$

So $p^n(n\ln(p)+1)=0$ giving $n=-(\ln(p))^{-1}$ (notice that $0<p<1$ so $n>0$). It's not too hard to check this is a local maximum, for example by second derivative test. Since $n$ must be an integer, the critical value of $n$ we found needs to be either rounded up or down (you can test which gives you a better answer).

-
I gave +1 for the answer because it is nice but it doesn't really answer the question. This is your expected reward based on a game where you continue playing. You could use a stopping straegy that quits prior to this optimal n. Als this expectation is unconditional. Given that you have survived until time N should you continue. It is the reward conditional on these outcomes that I think should be considered to decide whether or not to continue. Given you survive N stages your rewared is 100 N. The expected reward at stage N+1 given that you survived stage N is p(N+1)100 + (1-p) 0 . – Michael Chernick Sep 13 '12 at 19:34
What is not clear from your question is whether or not the stopping strategy should be unconditional on how much you have won so far which is what Sam's answer provides, whereas Brian and I look at sequentially decisions based on the current string of successes (head tosses). To my way of thinking the sequential stopping rule makes more sense than ignore the conditional information and continuing to play until a maximum unconditional expectation is achieved. – Michael Chernick Sep 13 '12 at 21:46
Sam's rule is to decide in advance when to stop whereas the sequential rule looks at the current reward and whether or not there is an expected gain or loss from another flip that another flip. It looks one step ahead based on current information. But by giving Sam the check mark you either prefer Sam's answer or did not appreciate the value (advantage)of the conditional information in our decision rule. – Michael Chernick Sep 13 '12 at 21:48

Following up on my comment: So a rational decision on quiting would be to stop if the expected gain by continuing for 1 more flip is less than or equal to the current gain. That would be to stop when 100 N >=100(N+1)p or 100 N (1-p)>= 100p or N>=p/(1-p).

For p=1/2 you would stop after 1 flip if you win $100. For the case p=0.8 N=4. this sort of rational play say to stop early. For a fair game quit if you are lucky to win on the first flip. If you know that probability of heads is 0.8 try to win 4 straight games and if you are lucky enough to get there then quit. Now this is a kind of risk neutral strategy. Since you didn't mention an inital bet that gets lost it is always worth playing once. But if you are highly risk averse and value the$100 gain you may want to quit after 1 flip even if you know that heads has a 0.8 chance of occurring each time. On the other hand if you are willing to take high risks and think (hey I am playing eith the houses money) and are a little greedy you might go beyond 4 flips given 4 straight heads starting out. Level of risk aversion could be quantified mathematically and an optimal solution could be found using a risk adverse or a greedy criterion fro stopping.

-

In the moment strategy

Assume the coin comes up heads with probability $p$ and tails with probability $1-p$. If you have $D$ dollars, your expected gain after the next flip would be $100p-D(1-p)$. I would quit when I am not expecting to increase my winnings. That is, when I have $D\ge\frac{100p}{1-p}$ dollars.

The expected winnings after $n$ flips is $100np^n$. I would stop when $100np^n\ge100(n+1)p^{n+1}$. That is, when $\frac{n}{n+1}\ge p$ which is when $n\ge\frac{p}{1-p}$.

Conclusion

Since both of these strategies yield the same answer, I would stop after $\left\lfloor{\raise{1pt}\large\frac{p}{1-p}}\right\rfloor$ flips.

If the coin is fair, that is $p=\frac12$, then I would quit after the first flip.

If the coin has $p=.8$, I would quit after $4$ flips, assuming I get there.

-
+1 for agreeing with me and Brian – Michael Chernick Sep 13 '12 at 20:51
@MichaelChernick: Thanks! I was trying to show both an immediate win-loss strategy, which is what it seems that you and Brian employed, and a strategy that looks at the game as a whole, which is more what Sam did. However, since this is a discrete game, I wanted to do a discrete analysis (taking differences) rather than taking derivatives as Sam did. Of course, upon closer examination, both look almost the same anyway. – robjohn Sep 13 '12 at 21:32