Toss a fair coin a number of times.

Question

Toss a fair coin, number of times. You always bet on heads and gain one dollar if it is a head and lose one dollar if it is a tail. You stop whenever you gain 3 dollars or you lose 2 dollars. Then which of the following is the correct one?

1. you end up winning with $2\over 3$ probability
2. you end up winning with $1\over 3$ probability
3. you end up winning with $3\over 4$ probability
4. you end up winning with $3\over 5$ probability
5. None of the above is correct.

If we don't know the number of trials, how can we do it?

Answer 1

For elegance, note that we can start from $2$ dollars instead of nothing, and win if you get to $5$ dollars and lose if you get to $0$ dollars.

Let $p_n$ be the probability that you will win if you start with $n$ dollars.

Then $p_0 = 0$ and $p_5 = 1$.

Also $p_n = \frac{1}{2} p_{n-1} + \frac{1}{2} p_{n+1}$ for any integer $n$ (strictly) between $0$ and $5$.

Thus $p_{n+1}-p_n = p_n-p_{n-1}$ for any integer $n$ (strictly) between $0$ and $5$.

Thus $p_5-p_0 = 5 ( p_1-p_0 )$ and hence $p_1-p_0 = \frac{1}{5}$.

Thus $p_n = \frac{n}{5}$ for any integer $n$ from $0$ to $5$.

Answer 2

I assume that you stop when your net gain becomes +3 or -2.

On average, you don't win or lose money in one toss. So your average gain in the whole game must be $0$ as well. (I don't really know how to prove it strictly, but if you just need to give the answer in a test, this consideration is enough.)

If you win with probability $p$ and lose with probability $1-p$, then your average gain is $3p-2(1-p)$. So you have $3p-2(1-p) = 0$, which means that $p = \frac25$.

Answer 3

(Edit: There were a number of bugs (I attribute to sleep deprivation). @imj is correct that I was not computing conditional probabilities. I have fixed that (probably with only one or two errors). These errors led to @Newb's difficulty in getting the results (incorrectly) claimed.)

Note that we can track our progress through the tosses via powers of $x + x^{-1}$. For instance, after one toss, we are equally likely to have gained or lost a dollar. The coefficients keep track of how many paths (from the initial state) have the various winnings/losings so far. Don't forget t oremove terms corresponding to terminated processes.

• two tosses: $(x + x^{-1})^2 = x^2 + 2 + x^{-2}$: 1 loser in 4 starts:
  • $1/4$ of the time, end here, losing \$2.
  • $3/4$ of the time we continue.
• three tosses: $(x^2 + 2)(x+x^{-1}) = x^3 + 3x + 2x^{-1}$: 1 winner in 6 continuations
  • $1/6 \cdot 3/4 = 1/8$ of the time, end here, winning \$3.
  • $5/6 \cdot 3/4 = 5/8$ of the time we continue.
• four tosses: $\dots = 3x^2 + 5 + 2/x^2$: 2 losers in 10 continuations
  • $2/10 \cdot 5/8 = 1/8$ of the time, end here, losing \$2.
  • $8/10 \cdot 5/8 = 1/2$ of the time we continue.
• five tosses: $\dots = 3 x^3 + 8x + 5/x$: 3 winners in 16 continuations
  • $3/16 \cdot 1/2 = 3/32$ of the time, end here, winning \$3.
  • $13/16 \cdot 1/2 = 13/32$ of the time we continue.
• ...

At this point, we already know our probability of winning is $\geq 1/8 + 3/32 = 7/32 > 1/5$ and of losing $\geq 1/4 + 1/8 = 3/8 > 1/5$

Notice the Fibonacci numbers in the coefficients. Set up two sums, one for winning, one for losing. Done.

Answer 4

Option 5: none of the above. We can of course exclude 1, 3, and 4 out of hand because otherwise gambling would work more often than it failed, but to exclude 2 we must get the actual value.

Starting from $0$, your odds of ending up (after any number of rolls) at $+2$ or $-2$ are even.

If it's $-2$, then you lose $= 0.5$ chance of losing so far, and the game ends so we can ignore this branch from now on.

If you are at $+2$ then your odds of ending up at $+3/+1$ (after any number of rolls) are even.

If it's $+3$, you win $= 0.5*0.5 = 0.25$ chance of winning so far.

If $+1$, then odds of $+3/-1$ are even. If $+3$, you win $= 0.25 + (0.5*0.5*0.5) = 0.375$ chance of winning so far.

If $-1$, odds of $-2/0$ are even. If $-2$, you lose $= 0.5 + (0.5*0.5*0.5*0.5) = 0.5625$ chance of losing so far.

If $0$, then we're back at zero dollars.

So we have a:

• $0.5625$ chance of losing;
• $0.375$ chance of winning;
• $0.625$ chance of having to "roll again", which will always be split into the same proportions.

So the proportion of wins:losses is hence $0.5625:0.375$.

Lose: $0.5625/(0.5625+0.375) = 0.6$

Win: $0.375/(0.5625+0.375) = 0.4$

I am a math noob (which likely shows), but the odds of winning being $2/5$ and of losing being $3/5$ just feels intuitively right, too.

Answer 5

The probability of winning appears to be $\dfrac25$, as this computation shows

There are 6 states (from $-2$ to $+3$). The square matrix shows the probability of moving from one state to another with one coin flip.

The vector $\left(\begin{array}{c} 0\\0\\1\\0\\0\\0\end{array}\right)$ is the starting state (we start with $0$ gain)

the limit as $n\to +\infty$ of the result is $\left(\begin{array}{c} \frac35\\0\\0\\0\\0\\\frac25\end{array}\right)$, therefore with infinite coin toss we are in the winning state $40\%$ of the time.

There has to be a better way tough.

Answer 6

This solution is based on the same simple idea as Litho's very nice answer, but also addresses the theoretical objections to it.

Assume the probability of winning the game is $p$. Then in one game, the expected amount won is $3p - 2(1-p) = 5p - 2$.

On the other hand, it is intuitively obvious that the expected amount won must be zero, and it follows from this that $p = 2/5$.

To prove this fact, we view the same game differently. We flip the coin an infinite number of times, except that once you have already reached $+3$ or $-2$, instead of being $\pm 1$, the value of heads or tails becomes $0$.

If $X$ is the total gain in the game, and $X_i$ is the gain on the $i$th flip, then $X = \sum X_i$, so $E(X) = \sum E(X_i)$.

But if $q_i$ is the probability that the threshold has not yet been reached before step $i$, then $X_i$ is $+1$ with probability $q_i/2$, $-1$ with probability $q_i/2$ and $0$ with probability $1-q_i$. Therefore $E(X_i) = 0$.

The foregoing argument that $E(X) = \sum E(X_i)$ actually depends on the Lebesgue dominated convergence theorem, with bounding function $\sum |X_i|$ (the number of flips needed to finish the game). The theorem is applicable here because the expected number of flips needed to finish the game is finite. For example, at any point in the game there is always at least a $1/8$ chance that the game will end within the next three flips, so $E(|X_{i+4}|) \leq \frac{7}{8} E(|X_i|)$, hence the series $\sum E(|X_i|)$ is convergent.

Answer 7

No need to get complicated, just use symmetry.

You can immediately drop options $1$, $3$ and $4$, because the probability of winning (i.e. stopping with $+3$ dollars) is less than $1/2$. You know this because the winning scenario ($+3$ dollars) is much harder to reach than the losing scenario ($-2$ dollars): it is as hard to reach $+2$ dollars as it is to reach $-2$ dollars, and then you have to get heads once more.

Now we wonder about option $2$: is the probability of winning $1/3$? I actually don't have an immediate answer to this, and I think another user will probably fill in this part. (If option $2$ also doesn't work, then the answer must be option $5$.)

Note that the question is a little unclear: do you stop after any two wins/three losses, or do you stop when your net value has changed by +3 or -2?