11
$\begingroup$

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?

$\endgroup$
11
  • $\begingroup$ Wining pobability: $$WWW$$ OR $$LWWWW$$ $\endgroup$ Feb 17 '16 at 8:14
  • $\begingroup$ Then, how about LLWWWWW, LLLWWWWWW.... can have infinite trial... when should be stop? $\endgroup$
    – user109403
    Feb 17 '16 at 8:18
  • $\begingroup$ $$LL\implies$$ "you lose $2$ dollar, you are stopped" $\endgroup$ Feb 17 '16 at 8:19
  • 1
    $\begingroup$ How about LWLWLWLWLWLWWWW? $\endgroup$ Feb 17 '16 at 8:20
  • 4
    $\begingroup$ Doe you stop when (a) you have won $3$ times in total or lost $2$ times in total (maximum trials would be $4$) or (b) when your net position is $+3$ or $-2$ or (c) you have won $3$ times consecutively or lost $2$ times consecutively? $\endgroup$
    – Henry
    Feb 17 '16 at 8:37
18
$\begingroup$

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

$\endgroup$
4
  • 3
    $\begingroup$ Some people call this method first-step analysis. Note that in this case we don't have to worry about infinite game plays since the probabilities are well-defined. However, in similar other questions that ask for the expected number of steps, one must always first prove that an infinite game play occurs with probability $0$, if not the expectation is infinite and the equations obtained from first-step analysis will all be useless. $\endgroup$
    – user21820
    Feb 17 '16 at 11:49
  • $\begingroup$ @imj: Edited. I'm surprised that some people take "between" to mean "including", when these two English words are on their own mutually contradictory. (See english.stackexchange.com/a/118403/75136) Also, instances of "between" for inclusive discrete ranges seems to be a very recent development. Historical usage of "between" seems to not include discrete ranges. $\endgroup$
    – user21820
    Feb 17 '16 at 13:26
  • $\begingroup$ I'm french. Inéqualities default to large in the french langage. e.g. 'positif' means non-negative, 'croissant' <-> non-decreasing, etc. Therefore I read between 0 to 5 as from 0 to 5. My bad. $\endgroup$
    – imj
    Feb 17 '16 at 13:38
  • $\begingroup$ @imj: Ah I see. Interesting! $\endgroup$
    – user21820
    Feb 17 '16 at 14:07
4
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ That is (very) pretty, but as you noted incomplete.If we remove the stopping at +3 for instance, the average gain becomes -2. We need to prove that the final expectancy is 0 :( $\endgroup$
    – imj
    Feb 17 '16 at 11:17
  • 2
    $\begingroup$ In my answer, I have addressed the theoretical issues raised here. $\endgroup$
    – David
    Feb 17 '16 at 15:52
3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ How do we know he wins more than 1/3 of the time? Sorry, it's not immediately obvious to me $\endgroup$
    – Newb
    Feb 17 '16 at 9:14
  • $\begingroup$ The probability of winning after 3 tosses should be 1/8 and not 1/6.the total number of possibilities is wrong every time after that. (removing the $x^{-2}$ makes it a conditional probability) $\endgroup$
    – imj
    Feb 17 '16 at 9:55
  • $\begingroup$ No need for any generating functionology. See my answer. =) $\endgroup$
    – user21820
    Feb 17 '16 at 11:44
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I knew there were non-trivial arguments at play. Thank you. $\endgroup$
    – imj
    Feb 17 '16 at 20:44
0
$\begingroup$

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?

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.