4
$\begingroup$

Let the number of players for a game of rock, paper, scissors be $n$. In each round of the game, each player chooses one of rock, paper, or scissors. Then, if exactly two of the three options have been chosen, the players who chose the losing option among those two are eliminated. (For example, if everybody chooses either rock or paper, those choosing rock are eliminated.) Otherwise, everyone stays in the game. The game continues until all but one player has been eliminated.

How would you work out the probability that a winner is determined after $k$ rounds?

(Assuming each choice is equally as likely)

$\endgroup$
6
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Thanks for the intuitive understanding. Well done I must say. $\endgroup$ – Desmoz Oct 2 '16 at 19:55

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.