6
$\begingroup$

There is a simple icebreaker game where a group of people compete in a rock-paper-scissors (RPS) tournament. When person A beats person B, they become a team where person A is the leader. And in general, when team A beats team B, they all become one team, and A's leader becomes the leader of the new team. This game always ends quickly with everyone on the same team. As Ross Millikan pointed out in the comments, it always takes exactly $n-1$ games.

But I'm wondering what would happen if we changed the rules slightly. Suppose team A beats team B. Then team A acquires B's leader, and the rest of team B dissolves into a bunch of teams of 1. For example, if a team of 4 beats a team of 6, then it will result in a team of 5 and 5 teams of 1. It makes sense that this game would last longer because teams can be dissolved.

I am specifically interested in finding out the average number of RPS games played in a tournament of $n$ people (they all start out as teams of 1) before there is only 1 team. To make this number well defined, I assume the following:

  1. Only one RPS game is played at a time.
  2. Each RPS game is played between a random pair of teams, with equal probabilities.
  3. The result of each RPS game is completely random (50/50). (Perhaps rock paper scissors was a bad analogy because it has ties. Just imagine that ties are played out until there is a winner, and that we're not counting ties in our running total of RPS games.)

I have constructed Markov Chains for a few values of $n$ where the nodes are the different partitions of teams. Using them, I have found that the average number of RPS games played seems to be $$2^{n-1}-1$$ I have no idea why this would be, or how to prove it, but maybe it is just a coincidence that it works for $1\le n\le6$ (or maybe I calculated them wrong). Can anyone prove a formula for the average number of RPS games? I would also appreciate it if anyone can programmatically verify my formula for larger values of $n$.

$\endgroup$
  • $\begingroup$ In your original version the tournament always ends after $n-1$ matches. After each match the number of leaders always decreases by $1$. You start with $n$ leaders and need to get to $1$, which takes $n-1$ matches. $\endgroup$ – Ross Millikan Oct 3 '17 at 4:13
  • $\begingroup$ @RossMillikan Yes, but I am considering the original rules trivial. I'm asking about the average number of matches with the new rules. $\endgroup$ – Riley Oct 3 '17 at 4:15
  • $\begingroup$ I understand, but you didn't say how many matches the original rules take. I agree with your formula for the new rules for $n=2,3$. $\endgroup$ – Ross Millikan Oct 3 '17 at 4:17
  • 2
    $\begingroup$ You may find it interesting to note that this game previously appeared in an equivalent, but different, formulation on this site: math.stackexchange.com/q/1246567/19328 $\endgroup$ – A. Rex Oct 17 '18 at 16:50
9
+50
$\begingroup$

Your calculations and conjecture are correct: for $n$ people, it takes an average of $2^{n-1}-1$ games for them to all end up on one team. Here's a Markov chain argument that avoids calculations and uses trickery instead, but it's a bit long, so bear with me.

First, let's consider a deterministic variant of the RPS game played by your rules. In the deterministic version, teams are sorted from best to worst. Every round consists of the two worst teams playing against each other. The second-worst team always wins, taking one person from the worst team; the worst team always loses, getting broken up into teams of $1$ which become the new worst teams (in arbitrary order, but all at the bottom of the ranking). Finally, we'll add a rule for what happens when there's only one team: in that case, the team plays against itself, loses, and gets broken up into $n$ teams (so we start over).

In the deterministic variant, we cycle between $2^{n-1}$ states in a form of binary counting. Let's represent the $n$ players as a row of $n$ $\star$'s, with $|$ dividers separating the teams in up to $n-1$ places. So the initial state (for $n=8$) looks like this: $$\star\mid\star\mid\star\mid\star\mid\star\mid\star\mid\star\mid\star$$ and after one game, we get: $$\star\mid\star\mid\star\mid\star\mid\star\mid\star\mid\star\;\star$$ and after another game, we get: $$\star\mid\star\mid\star\mid\star\mid\star\mid\star\;\star\mid\star$$ and after another game, we get: $$\star\mid\star\mid\star\mid\star\mid\star\mid\star\;\star\;\star$$ and so on. If we convert each state to a binary number by treating $\mid$ as $0$ and the lack of a $\mid$ as $1$, then these states become $0000000$, $0000001$, $0000010$, $0000011$, and so on, counting up by $1$ each time. The rule that the leader of the losing team joins the winning team and everyone gets split up is exactly the rule for adding $1$ to a number in binary.

We can think of the state of the deterministic game as a Markov chain, too. It's a really stupid Markov chain where all the transition probabilities are $0$ or $1$, but that's okay. In particular, the distribution in which we assign probability $\frac1{2^{n-1}}$ to each of the $2^{n-1}$ states is a stationary distribution.


Now let's convert the deterministic game into the actual game with probabilities of winning. We can do that with the following modification: right before each game is played, we shuffle the teams: we randomly permute the order of the teams sorted from best to worst.

After shuffling, we still say that the two worst teams play and the worst always loses. However, with shuffling, any two teams are equally likely to become the two temporarily-worst teams (and therefore be the ones playing) and for those two teams, either is equally likely to be the second-worst team and win. In other words, the deterministic rule with shuffling is equivalent to having two random teams play and with with equal probability.

But adding shuffling to the rules doesn't change the fact that the uniform distribution on states is stationary. If, on step $k$, we are equally likely to be in any state, but then we shuffle the teams (exchanging a bunch of equally-likely states) and advance to the next state in the cycle (replacing a state with an equally-likely state), on step $k+1$ we are still equally likely to be in any state.

And since the game with shuffling added is aperiodic (we can shuffle a state ending in $\star\mid\star\;\star$ to a state ending in $\star\;\star\mid\star$ and then increment to return to the original state), it has a unique limiting distribution, so the uniform distribution (which is stationary) must be it.


Okay, so we did a lot of work to figure out the limiting distribution. We wanted something completely different: a hitting time. What gives?

The reason we did this is to use the following fact about (finite, ergodic) Markov chains: given a state $i$ with limiting probability $\pi_i$, the expected time to return to state $i$ is $\frac1{\pi_i}$. In this Markov chain, the starting state $\star\mid\star\mid\cdots\mid\star$ has limiting probability $\frac1{2^{n-1}}$, so it takes $2^{n-1}$ steps to return to this state.

But how can we return to this state? The only other state that can get to this one is the state $\star\;\star\;\cdots\;\star$ in which everyone is on one team. So if it takes $2^{n-1}$ games, in expectation, to return to the $n$-teams state, and we must have gotten there from the $1$-team state, then it takes $2^{n-1}-1$ games, in expectation, to get from the $n$-teams state to the $1$-team state, proving the result we wanted.

$\endgroup$
  • 1
    $\begingroup$ This answer is brilliant. Is there a name for the property that the expected return time is $\frac1{\pi_i}$? Or do you have a reference so I can read about why that is? $\endgroup$ – Riley Oct 13 '17 at 15:12
  • $\begingroup$ None of the sources I've seen give a name for this property, but these course notes give a proof (Theorem 24.3). $\endgroup$ – Misha Lavrov Oct 13 '17 at 16:21
  • $\begingroup$ (Every resource on Markov chains I know gives essentially the same proof - that defining $\pi_i = 1/\mathbb E[\mathbf{T}_{ii}]$ satisfies the stationary equations. This involves messy algebra. We can also prove it using Wald's identity, which is much cleaner, but I don't have a reference for this argument.) $\endgroup$ – Misha Lavrov Oct 13 '17 at 16:31
  • $\begingroup$ Thanks, those course notes are very helpful. I really like your answer's approach, and how well you explain it! $\endgroup$ – Riley Oct 13 '17 at 16:49

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.