[Math] Probability in Rock Paper Scissors competitions

combinatoricsprobability

My professor gave the following question as a bonus, if two brothers Pat and Steve enter a rock paper scissors competition with $2^n$ players. In this competition players are randomly paired and then the winners move on to the next round. What is the probability that at one point in the competition the brothers face each other? My professor said my answer was wrong, and provided no explanation. I was wondering where my logic went wrong?

This is the solution I gave.

We can look at a smaller part of this problem to help solve the larger problem, the smaller part being what is the probability that two people will face each other in an individual round of of the tournament with $2^n$ players. This problem can also be expressed as the following, given a random pairing of $2^n$ people which includes two brothers Pat and Steve, what is the probability that the brothers will be in the same pair. This is given by the number of pairings where Pat and Steve are together divided by the total number of pairings. Notice that the number possible pairings where Pat and Steve are held constant is the number of pairings for $2n-2$ people. Thus if we can find some function $f(2n)$ that is defined as the number of ways of pairing $2n$ people, then the ratio $\frac{f(2^n-2)}{f(2^n)}$ will give us the desired probability. To find this ratio, lets consider how many pairings we add by increasing the number of people we are pairing by two. When this pair is held together there are $f(2n-2)$ pairings, and if we switch one of the people with a new person there are another $f(2n-2)$ pairings. If we hold one person constant we can pair him with any of the other $2n-1$ people. Since by summing these all together we get all of the possible pairings, this is $(2n-1)*f(2n-2)$. Thus the ratio we were looking for is $\frac{f(2^n-2)}{(2^n-1)*f(2^n-2)} = \frac{1}{2^n-1}$. The probability that both brothers reach the nth round is $\frac{1}{4^n}$, and since these cases are distinct from when the brothers face each other the probability that the brothers face each other in any of the $n$ rounds is the sum $\sum_{i=0}^n \frac{1}{2^{n-i}-1}*\frac{1}{4^n}$.

Best Answer

Your result $f(n)=(2^n-1)f(2^n-2)$ is correct (though it could have been more easily derived by noting that a player is equally likely to be paired with any of the $2^n-1$ other players). Note that you wrote $2n$ instead of $2^n$ in several places.

Your final result is wrong on several counts: It should say $4^i$ instead of $4^n$; the sum should only run up to $n-1$; and you didn't take into account that the later stages are only reached if the two aren't paired before, e.g. the second term isn't

$$\frac1{2^{n-1}-1}\frac1{4^1}$$

but

$$\frac{2^n-2}{2^n-1}\frac1{2^{n-1}-1}\frac1{4^1}\;.$$

The first numerator and second denominator cancel up to a factor $2$, and the same for subsequent terms, so the correct sum is

$$ \sum_{i=0}^{n-1}\frac1{2^n-1}\frac1{2^i}=\frac1{2^n-1}\frac{1-(1/2)^n}{1-(1/2)}=2^{1-n}\;, $$

consistent with the result that Hagen derived by a more elegant argument in a comment.

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

The probability of meeting in a tournament

Imagine all $2^n$ players with names Alice, Bob, Charlie and so on stay in line. Then they are given a blue card with a number from $1$ to $2^n$ which means their skill in game and a red card with a number from $1$ to $2^n$ which means their position in a tournament bracket.

Given a permutation of blue cards $p_b$ and a permutation of red cards $p_r$ we can calculate how the tournament will go. Or in other words, predict all $2^n-1$ pairing that will happen in the tournament.

Imagine this huge table with $N=(2^n!)^2$ rows (each row corresponds to a particular permutation $p_b$ and $p_r$) and $M=2^n-1$ columns (all predicted pairings for a given row). Is pair Alice-Bob is more frequent in this table than Alice-Charlie? Of course, no. Because for every row with particular cards of Bob and Charlie, there is a row with cards of Bob and Charlie swapped. Thus we conclude that every $k={2^n\choose 2}=2^{n-1}(2^n-1)$ pair of names has the same number of entries in the table.

Then what is the number $x$ of rows with a particular pair in it? Since pair cannot happen in the same row twice: $$ x\times k=N\times M, \qquad x=\frac{NM}k $$

What is the probability to pick one of those $x$ rows? $$ p=\frac xN = \frac Mk = \frac{2^n-1}{2^{n-1}(2^n-1)}=2^{-(n-1)}. $$

Best Answer

Related Solutions

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

Transition probabilities

Stopping probabilities

The probability of meeting in a tournament

Related Question