Rock, Paper, Scissors: Expected Match Length

Published by Scott Jenkins on

In this post, I derive the general formula for the length of a first to n match of Rock, Paper, Scissors. As a heads up, the maths isn’t light, so I suggest having a pen and paper on hand to work through the examples or finer details yourself to gain a full understanding. Maths is not a spectator sport. 

My thanks to Michael for working with me on this problem, for running Matlab simulations to test the theory, and for the brilliant idea of transforming the question from number of plays to number of points scored: a really fresh perspective. With the restrictions of covid-19, it was good fun working on this problem, and a reminder of the sort of discussions we shared in the Warwick maths department, or on the U1!

Brief:

In this write up, we answer the following question:

  • In a first to n match of rock, paper, scissors, between 2 people, what is the expected number of plays before the match is won?

We assume that each player plays randomly, with equal likelihood of playing rock, paper, or scissors in each play.

Clearing up the definition of a play:

  • A play is a single game of Rock, Paper, Scissors. Each player selects one of Rock, Paper, or Scissors. Each implement has a corresponding winning, losing and drawing implement as per the following image.

Approach:

Possible approaches to solve this:

  • Markov Chains 
  • Joint distributions: Let X, Y be random variables, the scores of the first and second player respectively. Then Max(X,Y) = n is the condition for match termination.
  • Probability Trees
  • Induction?

In our work, we begin with an analysis of the cases where n=1 to understand the expected length of a match in which a single point is scored. The key observation is that this expected length is equal to the expected number of plays between each additional point being won. We will show that this constant is equal to 1.5. The fact that it is constant follows from the fixed probability of any play resulting in a draw. 

With this observation in place, we reframe the problem to one of calculating the expected number of points won before the match is complete, then multiply this by 1.5 to return the solution. 

We determine the number of points scored before a match is won through the use of probability tree diagrams and the manipulation of binomial coefficients. We close with the generalised formula, and a piece of Python code which simulates Rock, Paper, Scissors matches and verifies our result.

N = 1:

Let X be the number of plays until the game is won and recall that the expectation, E(X) is defined as follows:

\mathbf{E(X) = \sum_{k}x_{k}p_{k}}

If n = 1, a match of length m can only occur with a string of m-1 drawn plays followed by a win for either player.There is a 1 in 3 chance of any play resulting in a draw, and a 2 in 3 chance of any play resulting in a win for one of the players. All plays are independent by assumption, and so we have the following table of of match lengths and probabilities:

kx_kp_k
112/3
222/9
332/27
………
nn2 / (3^n)

Therefore, the expectation of X is:

\mathbf{E(X) = \sum_{k=1}^{\infty}\frac{2k}{3^k}}

A throwback to our first year analysis courses, we know that this converges, as a result of the ratio test. Indeed, coding this in Matlab, we see that the limit is 1.5.

Whilst I’m near fully convinced with the correctness of the tech, it’s still desirable to prove this analytically as follows:

We have shown that the expected number of plays before a single point is scored is 1.5. Since each point is independent, the expected number of plays before r points are scored is 1.5r. From here, we focus our attention on the expectation of points scored in a match, knowing that we can multiply this by 1.5 to return the expected number of plays. We proceed with an analysis of the ‘first to 2’ match.

N = 2:

Clearly at least 2 points must be scored for a winner in this case. Also, every match will be won with 3 points scored or less. Either it is won after two points have been scored, else the score at this stage is a 1 all draw, from which the next scoring point results in the winner emerging. This is a straightforward application of the pigeonhole principle, indeed analogous to the example of sock picking.

We consider the probability of winning with exactly 2 points scored and exactly 3 points scored, through the introduction of probability tree diagrams.

In the above, the pairs of numbers at the nodes represent the scores of player 1 and player 2 respectively. Each vertical column of nodes moving to the right accounts for an additional point being scored – the sum of the numbers at the node increments by 1 for every move right along a branch. Each game is equally likely to be won by player 1 or by player 2, and so the probability of moving from each node to the 2 children nodes is 0.5.

We see that there is a 50% chance that the match will terminate after 2 points scored and a 50% chance that the match will terminate after 3 points scored. Thus, the expected number of points scored is:

\mathbf{\frac{2}{2} + \frac{3}{2} = \frac{5}{2}}

Combining this with the knowledge that the expected number of plays for each additional point to be scored is 1.5, we have the expected number of plays:

\mathbf{E(X) = \frac{5}{2} \times \frac{3}{2} = \frac{15}{4}}

Onward to the general case.

N = n, the general case.

Observation 1:

In a ‘first to n’ match, between n and 2n-1 points inclusively must be scored. This follows from the pigeonhole principle explained above.

Observation 2:

After p points are scored, the split of points between the players follows a binomial distribution. The number of ways a score of (player 1 score, player 2 score) can be reached is equal to the following binomial coefficient:

\mathbf{\binom{\textup{p}}{\textup{player 1 score}} = \binom{\textup{p}}{\textup{p - player 2 score}}}

Convince yourself of this with these tree diagrams.

A mathematical argument if you remain unconvinced. A number of ways of reaching a score of (x,y) is equal to the sum of the number of ways of scoring (x-1,y) and the number of ways of scoring (x,y-1). Then, since 

\mathbf{\binom{n}{r} = \binom{n-1}{r} + \binom{n-1}{r-1}}

the observation follows (exercise!)

For a visual representation of a similar set up, check out the Galton Board, which demonstrates the binomial distribution in a fun way.

With these observations in place, we are ready to calculate the probabilities of the game being won after exactly p points scored, for p between n and 2n -1. 

Without loss of generality, suppose player 1 wins the match.

Case 1: p = n.

The probability of player 1 scoring n consecutive points is (1/2)^n 

Case 2: p is between n + 1 and 2n – 1.

The number of paths which result in exactly p points scored is:

\mathbf{\binom{p}{p-n} - \binom{p-1}{p-n-1}}

Why? We take the number of paths to reach a score of (n, p-n) but need to subtract the paths which pass through (n,p-n-1), since these games are complete before the pth point is scored.

Illustrating these paths on our tree diagrams may be a helpful visual, the top dashed lines contain an example path which will never be followed, and the bottom dashed line contains the corresponding path counts.

Now, the probability of player 1 winning after exactly p points have been scored is:

\mathbf{\frac{\binom{p}{p-n} - \binom{p-1}{p-n-1}}{2^{p}}}

And by symmetry, the probability of either player winning after exactly p points have been scored is:

\mathbf{\frac{\binom{p}{p-n} - \binom{p-1}{p-n-1}}{2^{p-1}}}

 Combining these cases, and applying the definition of expectation, we see that the expected number of points scored in a first to n match is:

\mathbf{\frac{n}{2^{n-1}} + \sum_{p=n+1}^{2n-1} \frac{p \left ( \binom{p}{p-n} - \binom{p-1}{p-n-1}\right )}{2^{p-1}}}

Finally, we multiply the expected number of points scored by 1.5 to return the expected number of plays.

General Formula

Let X_n be the number of plays in a first to n match of rock, paper, scissors. Then:

\mathbf{E(X_{n}) = \frac{3}{2}\left ( \frac{n}{2^{n-1}} + \sum_{p=n+1}^{2n-1}\frac{p\left ( \binom{p}{p-n} - \binom{p-1}{p-1-n}\right )}{2^{p-1}}\right )}

Here are the first 4 results from the formula:

nE(X_n)
13/2
215/4
399/16
4279/32

Python

We can verify these results with the following Python simulation:

This shows that the average number of plays in a set of 1000 first to 3 matches was 98.752/16, pretty close to the 99/16 theoretical result produced by the formula.

A simple tweak, allows us to view how the expected number of games increases as N increases. In the following code, we play 1000 first to 1 matches, 1000 first to 2 matches, and so on up to 1000 first to 100 matches. 100,000 matches in less than a minute, not bad.

We find the following relation between N and the expected number of plays, which suggests there is an underlying linear relationship.

What is this linear relationship, and why is it linear? 

A quick regression line gives us almost perfect positive correlation, with equation:

\textup{Number of Plays} \approx 2.87 N - 4.58

I’m struggling to identify why this is the case right now, something to think about. Can anyone help please? I assume that the coefficients are approximate to some relevant rational numbers.

Further questions for another time:

  • Why does the above linear relation exist?
  • Rock, Paper, Scissors can be defined for N players. How does this impact the expected number of plays? 
  • Rock, Paper, Scissors, Lizard, Spock popularised by the Big Bang Theory. This game is aimed at reducing draws, so we would expect a lower number of plays per match.
  • How does this compare to real game data? I’ve assumed that play is random, which to begin with is a fair assumption. However, humans are not strong random players, and patterns will creep into an individual’s choice of implement. A skilled rps player can use this to their advantage and win x > 50, % of games. In this case, what is the expected number of plays?

Until next time,

Scott

Categories: Learning

Related Posts

Data Science

MSc Operational Research Reflections

A few years after completing my undergraduate mathematics studies at the University of Warwick, and long after I’d last used the definitions of ‘Lipschitz continuity’ or ‘Hausdorff dimensions’, I was working for Dunelm, the British Read more…

thinking which meal to prepare
Learning

Meal Planning with Python and Networkx

I enjoy cooking. It can be a good way to wind down after a day of work, and for recipes I know well switch on auto-pilot. But that’s only once I’ve decided what to cook. Read more…

Learning

Semester 1 Review: MSc Operational Research

That’s a wrap for semester 1 of my MSc Operational Research with Data Science programme. I sat the last of my four exams yesterday afternoon; what better time to reflect on the previous 14 weeks. Read more…