2
$\begingroup$

Alice and Bob play Rock, Paper, Scissors until one or the other is 5 wins ahead. They generate their wins at random, so, in each round, the outcomes are equiprobably win, lose or draw.

After 10 rounds, Alice is 1 ahead.

After 13 rounds, one or the other is 1 ahead.

At round 20, one of them attains the 5 win lead and the game ends.

What is the probability that Alice is the ultimate winner?

This is my attempt at the solution:

After 10 rounds, Alice is 1 ahead. The possibilities are $$\text{Alice wins 1, Bob wins 0, 9 draws}$$ $$\text{Alice wins 2, Bob wins 1, 7 draws}$$ $$\text{Alice wins 3, Bob wins 2, 5 draws}$$ $$\text{Alice wins 4, Bob wins 3, 3 draws}$$ $$\text{Alice wins 5, Bob wins 4, 1 draw}$$

After 13 rounds, one or the other is 1 ahead. The possibilities are $$\text{Alice wins 1, Bob wins 0, 12 draws}$$ $$\text{Alice wins 2, Bob wins 1, 10 draws}$$ $$\text{Alice wins 1, Bob wins 2, 10 draws}$$ $$\text{Alice wins 3, Bob wins 2, 8 draws}$$ $$\text{Alice wins 2, Bob wins 3, 8 draws}$$ $$\text{Alice wins 4, Bob wins 3, 6 draws}$$ $$\text{Alice wins 3, Bob wins 4, 6 draws}$$ $$\text{Alice wins 5, Bob wins 4, 4 draws}$$ $$\text{Alice wins 4, Bob wins 5, 4 draws}$$ $$\text{Alice wins 6, Bob wins 5, 2 draws}$$ $$\text{Alice wins 5, Bob wins 6, 2 draws}$$ At round 20, one of them attains the 5 win lead and the game ends. The possibilities are: $$\text{Alice wins 5, Bob wins 0, 15 draws} - Win$$ $$\text{Alice wins 6, Bob wins 1, 13 draws} - Win$$ $$\text{Alice wins 1, Bob wins 6, 13 draws} - Lose$$ $$\text{Alice wins 7, Bob wins 2, 11 draws} - Win$$ $$\text{Alice wins 2, Bob wins 7, 11 draws} - Lose$$ $$\text{Alice wins 8, Bob wins 3, 9 draws} - Win$$ $$\text{Alice wins 3, Bob wins 8, 9 draws} - Lose$$ $$\text{Alice wins 9, Bob wins 4, 7 draws} - Win$$ $$\text{Alice wins 4, Bob wins 9, 7 draws} - Lose$$ $$\text{Alice wins 10, Bob wins 5, 5 draws} - Win$$ $$\text{Alice wins 5, Bob wins 10, 5 draws} - Lose$$ $$\text{Alice wins 11, Bob wins 6, 3 draws} - Win$$ $$\text{Alice wins 6, Bob wins 11, 3 draws} - Lose$$

As all outcomes occur with equal probability, my answer is

$$\mathbb{P}(\text{Alice wins})=\frac{7}{13}$$

Could someone confirm whether this is correct.

$\endgroup$
  • 2
    $\begingroup$ "After 10 rounds, Alice is 1 ahead. The possibilities are " Stop right there. The possiblities are that Alice is 1 ahead. period. How she got to be 1 ahead is not in the least bit relevent and will not affect any further outcome. Maybe she one one and 9 draws or maybe she won 5 and lost 4. Doesn't matter. $\endgroup$ – fleablood Oct 7 '16 at 17:06
  • 1
    $\begingroup$ Some wrinkles: "Alice wins 1, Bob wins 2, 4 draws" is not equiprobable to "Alice wins 5, Bob wins 1, 1 draw." (You need to consider the number of orderings of these outcomes.) But even disregarding this, the more serious obstacle is that you also need to account for the fact that nobody reaches a 5-win lead before game 20. $\endgroup$ – angryavian Oct 7 '16 at 17:19
1
$\begingroup$

The main issue with your solution occurs when you assert that

all outcomes occur with equal probability

in reference to the number of wins/losses of each of Alice and Bob. While each individual outcome is certainly equiprobable and each event is certainly independent, you have been given very specific conditions to work with that you must adhere to.

Here is a (hopefully intuitive) explanation of the steps you could take to work with those conditions:


Round 10: Alice is up by $1$. As fleablood mentioned, it does not matter how this came to be. After the next $3$ rounds, we know that either Alice or Bob will be $1$ ahead.

For Alice to be $1$ ahead, she can win no more than $1$ game out of the next three, lest Bob be unable to be just $1$ behind. This means that there are two distinct possibilities:

  • Alice wins $1$, loses $1$, and ties $1$.
  • Alice ties all $3$.

There are $6$ ways for the former situation to occur, and $1$ way for the latter to occur.

For Bob to gain a lead of $1$, there is only one possibility:

  • Bob wins $2$ and ties $1$.

There are $3$ ways for this to occur.

From this (and the knowledge that each individual outcome is equiprobable), we see that the information from Round 10 implies that it is $\frac{7}{3}$ times as likely for Alice to be ahead at the onset of Round 13 than it is for Bob.


Round 13: Let person $X$ be in the lead, with person $Y$ behind by $1$.

For $X$ to win, you may expect that, similarly to above, we would have two distinct probabilities over the next seven rounds:

  • $X$ wins $4$ and ties $3$
  • $X$ wins $5$, loses $1$, and ties $1$

This is nearly correct; however, we must account for the fact, that any win putting $X$ ahead by $5$ must not occur before Round 20.

We know that $X$ will win Round 20 and must be ahead by $4$ after Round 19; we will consider the possibilities for Rounds 14-19

If $X$ wins $4$ and ties $3$, he/she must have won $3$ and tied $3$ over those six rounds; no $3$ wins would put him/her in a winning position, so there are ${6 \choose 3} = 20$ valid ways for this to happen.

If $X$ wins $5$, loses $1$, and ties $1$, then he/she must have won $4$, lost $1$, and tied $1$ over those six rounds. This case is more complicated, because $4$ wins too soon can cause $X$ to win before round $20$. Specifically, the loss cannot occur after $4$ wins; otherwise $X$ would win before Round 20. Thus, ignoring the draw for now, we can have a win/loss ($W/ L$) sequence of $LWWWW$, $WLWWW$, $WWLWW$, or $WWWLW$; now, by inserting the draw into any of the sequences, we see that there are $6$ ways for each ordering of wins and losses to happen, meaning there are a total of $6 \times 4 = 24$ valid ways for $X$ to win $5$, lose $1$, and tie $1$ such that he/she wins exactly at Round 20.

Combining our above results, there are $44$ ways for $X$ to win exactly at Round 20.

For $Y$ to win, he/she must win $6$ and tie $1$. Since the $6^{\text{th}}$ win must occur on Round 20, he/she must win $5$ and tie $1$ over the preceding six rounds.

There are clearly $6$ ways for such a sequence of outcomes to happen.

Thus, we conclude that $P(X \text{ wins } | \, X \text{ leads}) = \frac{44}{6}P(Y \text{ wins } | \, X \text{ leads})$


Putting it all together, we have $7p = P(\text{Alice leads})$ and $2p = P(\text{Bob leads})$, where $p = \frac{1}{10}$. Similarly, we have $44q = P(\text{Alice wins } | \text{ Alice leads}) = P(\text{Bob wins } | \text{ Bob leads})$ and $6q = P(\text{Bob wins } | \text{ Alice leads}) = P(\text{Alice wins } | \text{ Bob leads})$, where $q = \frac{1}{50}$.

$P(\text{Alice wins}) = P(\text{Alice leads})P(\text{Alice wins } | \text{ Alice leads}) + P(\text{Bob leads})P(\text{Alice wins } | \text{ Bob leads})$

$P(\text{Bob wins}) = P(\text{Bob leads})P(\text{Bob wins } | \text{ Bob leads}) + P(\text{Alice leads})P(\text{Bob wins } | \text{ Alice leads})$.

Thus:

$P(\text{Alice wins}) = 7p \cdot 44q + 3p \cdot 6q = \frac{7}{10}\cdot\frac{44}{50} + \frac{3}{10} \cdot {6}{50} = \frac{308}{500} + \frac{18}{500} = \frac{326}{500} = \frac{163}{250}$.

$P(\text{Bob wins}) = 3p \cdot 44q + 7p \cdot 6q = \frac{3}{10}\cdot\frac{44}{50} + \frac{7}{10} \cdot {6}{50} = \frac{132}{500} + \frac{42}{500} = \frac{174}{500} = \frac{87}{250}$

$\endgroup$
2
$\begingroup$

Not every outcome is equaly likely at the end.

We know that after 13 rounds, Alice or Bob has 1 win more than the other. However, we also know that after 10 rounds, Alice has 1 more win than Bob, so the probability that Alice has the lead after 13 rounds is different than the probaliity Bob has the lead after 13 rounds.

Furthermore, the probability for Bob to win after 20 rounds depends on whether Alice has the lead in round 13 or Bob has the lead in round 13, and the same holds for Alice.

So we must first find the probability that Alice wins given that Alice has the lead, and the probability that Alice wins given that Bob has the lead. By symmetry, we have \begin{align} \mathbb{P}(\text{A wins} \mid \text{B leads}) = 1 - \mathbb{P}( \text{B wins} \mid \text{B leads}) = 1 - \mathbb{P}(\text{A wins} \mid \text{A leads}). \end{align} We can interchange Alice and Bob, so we only have to compute one probability. The easiest one is $\mathbb{P}(\text{A wins} \mid \text{B leads})$. As Bob has one more win than Alice, Alice needs 6 wins more than Bob in 7 rounds, so Alice must win 5 games in 6 rounds and a draw, and win the last round. This can happen in 6 ways. However, we must also find out how many ways there are for the game to evolve for Bobs lead to victory for Alice or Bob in 7 rounds, so we must compute the number of ways Bob can win.
Bob must win the last round, and either there will be 3 wins and 3 draws in the 6 previous rounds, or 4 wins, 1 lose and 1 draw. In the first case, we have 20 ways of this happening. In the second case the lose must happen before the fourth win, so either the 19 round is a win for Bob or the 19 round is a draw and the 18 round is win. First case can happen in 20 ways and the second case can happen in 4 ways. As each way to end the game is equally likely, we find \begin{align} \mathbb{P}(\text{A wins} \mid \text{B leads}) = \frac{6}{6+20+20+4} = \frac{3}{25}. \end{align} In a similiar way you can find \begin{align} p = \mathbb{P}(\text{A leads in round 13} \mid \text{A leads in round 10}) \end{align} Than you combine those probabilities to find that the probability Alice wins is $\frac{163}{250}$.

$\endgroup$
  • $\begingroup$ I think you overlooked the fact that the five game lead can not happen before game 20. You allow for Alice to win with the last game being a draw, or alice to be up by 6 at game 19 but B wins the last, etc. all of those are not possible. $\endgroup$ – fleablood Oct 7 '16 at 17:50
  • $\begingroup$ @fleablood, I take that in account by making sure the 19 round is won by Bob if Alice wins once in the last rounds, or round 19 is draw and round 18 is won by Bob, so that Alice wins before Bob has a 5 game lead. $\endgroup$ – Hetebrij Oct 7 '16 at 17:54
  • $\begingroup$ Hmm, okay. I came up with different numbers than yours. I could have done a counting error. .. oh, scrod. I think I see my second counting error. If 19 is a draw then Bob must win 18.... grumble.... $\endgroup$ – fleablood Oct 7 '16 at 18:11
  • $\begingroup$ Wait, no! If 19 is a draw than alice, not bob, wins 18. Otherwise alice won 14,15,16,17 and won at 17. $\endgroup$ – fleablood Oct 7 '16 at 18:15
  • $\begingroup$ @fleablood We have the roles of Alice and Bob switched. I assume Bob is winnie-pants, so Bob should win 18 if 19 is draw, so that Alice wins once before to prevent Bob from getting 5 ahead. $\endgroup$ – Hetebrij Oct 7 '16 at 21:10
1
$\begingroup$

Wow, that's a lot of unnecessary extra work.

After 10 rounds Alice is a ahead by 1. How she got that way doesn't matter so the following 5 lines are utterly wasted.

After 13 rounds One or the other is ahead. So either:

1) Bob was ahead: Bob won 2 rounds, and third was a draw.

2) Alice was ahead: All three were draws.

3) Alice was ahead: 1 was a draw, and alice and bob each won 1.

4) Impossible options: everything else.

Possible ways for 1 to happen: $3$. game 11,12,or 13 is a draw; others are won by Bob.

Possible ways for 2 to happen: $1$. All games are draws.

Possible ways for 3 to happen: $6$. there are three possible games that could be a draw and two possible ways Alice and bob can each win one or the other.

Probability Bob is ahead after 13 games: $3/10$.

Probability Alice is ahead after 13 games: $7/10$.

Call the person who is ahead Winnie-pants and the guy who is behind Losie-pants.

After 20 games, somone wins.

Possibility it is Losie-pants: $6$. Losie-pants had to win 6 out 7 games to come out 5 ahead. So 1 was a draw. The last game was not a draw as that would mean Losie-pants won on the 19th game. So there are 6 games Losie-pants could have drawn on.

Possibility it is Winnie-pants: Winnie-pants won game 20 otherwise the match would have ended earlier. Winnie pants won 3 other games in order to end up 5 ahead. And of the three remaining games:

-- all were draws, so 3 of 6 where draws rest were winnie-pants wins: ${6 \choose 3} = 6*5*4/1*2*3 = 20$ ways.

-- one was a draw, one was a winnie pants win, and one was a losie-pants win. However the losie pant's win most occur before the last winnie-pants win or else winnie-pants would have been up by 5. So

-- game 19 is draw, game 18, is winnie pants and of 14-17 one is a losie-pants win: $4$ ways.

--game 19 is winnie-pants win: 1 of the remaining 5 is a losie-pants win and 1 or the remaining 4 is a draw. 20 ways.

Probability of losie-pants being the winner: $6/50=3/25$.

Probability of winnie-pants bing the winner: $44/50=22/25$

Probability of Alice winning = Probability of Alice being winnie-pants x probability of winnie-pants winning + probability of alice being losie-pants x probability of losie-pants winning =

$7/10 * 22/25 + 3/10*3/25 = 163/250$

Probability of Bob winning = Probability of Bob being winnie-pants x probability of winnie-pants winning + probability of bob being losie-pants x probability of losie-pants winning=

$3/10*22/53 + 7/10*3/25 = 87/250$

$\endgroup$
  • $\begingroup$ If winnie.-pants must be the winner, losie-pants cannot lose after the fourth win of winnie-pants, otherwise the game would have ended in round 18 or 19. $\endgroup$ – Hetebrij Oct 7 '16 at 17:50
  • $\begingroup$ Hmm, good point. $\endgroup$ – fleablood Oct 7 '16 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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