[Math] Rock, Paper, Scissors Problem

probability

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.

Best Answer

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

Transition probabilities

Let's start with an easier question. Suppose you play a round with $n$ players. We want to compute the probability that, after that round, there will be exactly $m$ players remaining, for some $m$ with $1 \leq m \leq n$. We'll call this probability $T_{n,m}$.

If $m < n$, this means that one of three things happened:

$m$ players picked rock, $n-m$ picked scissors, none picked paper,
$m$ players picked scissors, $n-m$ picked paper, none picked rock, or
$m$ players picked paper, $n-m$ picked rock, and none picked scissors.

These are mutually exclusive options (for $0 < m < n$). Each of these options can occur in $\binom{n}{k}$ of the $3^n$ equally likely round configurations, so the total probability that one of them occurs is $$ T_{n,m}=3\frac{\binom{n}{m}}{3^n}=\frac{\binom{n}{m}}{3^{n-1}} $$

If $m=n$, then the number of different options picked was not exactly two (it was either three or one). So we'll compute $T_{n,n}$ by finding the probability that the number of options picked was exactly two, and then subtracting that from $1$.

We can compute the probability that exactly two options were picked by summing all the $T_{n,m}$ we already know and using the binomial theorem, but there's an easier approach. We can uniquely specify a configuration in which exactly two options were picked by choosing:

An option to skip (in one of $3$ ways)
A way for the $n$ players to choose between the other two options (in one of $2^n-2$ ways — here we're leaving out the $2$ ways in which all $n$ players choose the same other option).

So there are $3(2^n-2)$ configurations in which exactly two options are chosen, meaning the probability of landing in one of them is $\frac{3(2^n-2)}{3^n}$, or $\frac{2^n-2}{3^{n-1}}$. So $$ T_{n,n}=1-\frac{2^n-2}{3^{n-1}}=\frac{3^{n-1}-2^n+2}{3^{n-1}} $$ and we've now computed all the values of $T_{n,m}$ that we need.

Stopping probabilities

Now that we have that under our belt, let's compute the probability that, starting with $n$ players, it takes exactly $k$ rounds to finish. Let $p_{n,k}$ be that probability.

We'll start with some trivial cases. If $n=1$, we're already done! So we should take $p_{1,0}=1$, and $p_{1,k}=0$ for all $k>0$. Also, if $n>1$, we have to play at least one more round, so $p_{n,0}=0$ for all $n>1$.

For larger $n$ and $k$, we can use the transition probabilities we've already computed. For example, say we want to know $p_{4,3}$. After playing the first round, we'll be left with some number of players (between $1$ and $4$). The number of players we're left with is given by $p_{m,2}$ for some $m$; the probability we're left with that many players is $T_{n,m}$. So overall, we have $$ p_{4,3}=T_{4,4}p_{4,2}+T_{4,3}p_{3,2}+T_{4,2}p_{2,2}+T_{4,1}p_{1,2}=\sum_{m=1}^4 T_{4,m}p_{m,2} $$

In general, this kind of reasoning leads to a recursive formula for $p_{n,k}$: $$ p_{n,k}=\sum_{m=1}^n T_{n,m}p_{m,k-1} $$

I haven't been able to use this recursive formula to find a closed form for $p_{n,k}$, but it's certainly good enough to compute it for any fixed $n,k$. This Sage/Python code does that (though note that it's not at all optimized and will probably take a while to run):

#!/usr/bin/env sage -python

from sage.all import *

def transition_prob(n, m):
    if n < m:
        return 0
    elif n == m:
        return ZZ(3 ** (n - 1) - 2 ** n + 2) / ZZ(3 ** (n - 1))
    else:
        return binomial(n, m) / ZZ(3 ** (n - 1))

def p(n, k):
    if n == 1 and k == 0:
        return 1
    elif n == 1 or k == 0:
        return 0
    else:
        return sum(transition_prob(n, m) * p(m, k - 1) for m in range(1, n + 1))

Using this, here are some $p_{n,k}$ for specific small values of $n$ and $k$:

\begin{array}{c|ccccc} & 2 & 3 & 4 & 5 & 6\\ \hline1 & 2/3 & 1/3 & 4/27 & 5/81 & 2/81 \\ 2 & 2/9 & 1/3 & 196/729 & 125/729 & 1922/19683 \\ 3 & 2/27 & 5/27 & 4492/19683 & 11405/59049 & 644342/4782969 \\ 4 & 2/81 & 7/81 & 81724/531441 & 89125/531441 & 161571182/1162261467 \\ 5 & 2/243 & 1/27 & 1324852/14348907 & 5544485/43046721 & 35534152202/282429536481 \\ 6 & 2/729 & 11/729 & 20057428/387420489 & 3976885/43046721 & 7285176581882/68630377364883 \\ 7 & 2/2187 & 13/2187 & 290507260/10460353203 & 1994764685/31381059609 & 1433492089339262/16677181699666569 \\ 8 & 2/6561 & 5/2187 & 4082704396/282429536481 & 12026993765/282429536481 & 274981525969093862/4052555153018976267 \\ 9 & 2/19683 & 17/19683 & 56174521060/7625597484987 & 641108146565/22876792454961 & 51889668896621508242/984770902183611232881 \end{array}

I see no obvious pattern for $k>1$ and $n>3$, but you are invited to look for one!

To three significant figures, these numbers are: \begin{array}{c|ccccc} &2&3&4&5&6 \\ \hline 1 & 0.667 & 0.333 & 0.148 & 0.0617 & 0.0247 \\ 2 & 0.222 & 0.333 & 0.269 & 0.171 & 0.0976 \\ 3 & 0.0741 & 0.185 & 0.228 & 0.193 & 0.135 \\ 4 & 0.0247 & 0.0864 & 0.154 & 0.168 & 0.139 \\ 5 & 0.00823 & 0.0370 & 0.0923 & 0.129 & 0.126 \\ 6 & 0.00274 & 0.0151 & 0.0518 & 0.0924 & 0.106 \\ 7 & 0.000915 & 0.00594 & 0.0278 & 0.0636 & 0.0860 \\ 8 & 0.000305 & 0.00229 & 0.0145 & 0.0426 & 0.0679 \\ 9 & 0.000102 & 0.000864 & 0.00737 & 0.0280 & 0.0527 \end{array}

So, roughly speaking, the $2$-player game most likely takes $1$ round; the $3$-player game $1$ or $2$; the $4$-player game $2$; the $5$-player game $3$; and the $6$-player game $3$ or $4$.

Best Answer

Related Solutions

[Math] A seeming paradox in a coin-flipping game

[Math] Rock, Paper, Scissors Probability For Multiple Players

Transition probabilities

Stopping probabilities

Related Question