[Math] Odds of drawing multiple rounds of rock paper scissors.

probability

OK, so the back story for this is me and my friend often decide things on a quick game of rock paper scissors. I think on this occasion it was for who would get up and answer the door when the pizza came. The point is, on this occasion, we drew 17 times in a row before we broke the dead lock.

How do I find the odds of drawing n games of rock, paper, scissors?

We were playing the normal rules of rock, paper, scissors and, for arguments sake, there were no tactics or mind games going on – just random choices by both my friend and I (though I think some kind of subconscious thing must have been at play because my gut tells me the odds of this are astronomical).

Best Answer

The chances of a draw when both parties chosing uniformly are exactly $\frac13$ (it's a fair game because of this). Now for that to happen $17$ times in a row, the chances are $$\frac1{3^{17}} \approx 7.74\cdot 10^{-9}$$ but keep in mind that these are a-priori. That means for example after two draws, the chances of another draw stay at $\frac13$ and the chances for the $15$ remaining draws consecutively are $\frac1{3^{15}}$.

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

[Math] Rock, Paper, Scissors Problem

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

Best Answer

Related Solutions

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

Transition probabilities

Stopping probabilities

[Math] Rock, Paper, Scissors Problem

Related Question