Let there initially be $m$ players in a game of rock-paper-scissors. Everyone uniformly outputs one of rock, paper, and scissors. Rock wins against scissors, scissors win against paper, and paper wins against rock.
There are three cases for each game:
Case 1, only two of the possible outputs are played:
There is a group of people with the winning output over the group with the losing output. This group will stay in play while the losing group leaves.
Case 2, there is at least one of each output:
Everyone stays and another game is played with the players still in the game.
Case 3, everyone outputs the same thing:
Everyone stays and another game is played with the players still in the game.
What is the expected number of games until only one person is still in play?
I tried a few small cases and figured that using a function $f(x)$ where $x$ is the number of people left and $f(x)$ is the expected number of games until only one person is still in play is a possible way of figuring out the solution, but I'm not sure how to generalize this to a case of $m$ players. Does anyone have any ideas?
Best Answer
There are $3^m$ possible (ordered) choices by the contestants. Of these, $2^m$ consist only of papers and rocks; more specifically, for each $0\le k\le m$, there are $\binom mk$ sets of choices that consist of exactly $k$ papers and $m-k$ rocks. Let's discard the $2$ choices with only rocks and only papers; that means that for $1\le k\le m-1$ there are $\binom mk$ sets of choices that result in $k$ players remaining after the round. The same is true of rock-scissors choices and scissors-paper choices, so we multiply by $3$. The other $3^m-3(2^m-2)$ choices result in the $m$ contestants all remaining after the round.
We conclude that the expected stopping time, $S_m$, of this game with $m$ contestants satisfies $S_1=0$ and $$ S_m = 1 + \frac1{3^m} \bigg( \big( 3^m-3(2^m-2) \big) S_m + \sum_{k=1}^{m-1} 3\binom mk S_k \bigg), $$ or $$ S_m = \frac1{3(2^m-2)} \bigg( 3^m + \sum_{k=1}^{m-1} 3\binom mk S_k \bigg). $$ The first eight values are $$ \{S_1,\dots,S_8\} = \left\{0,\frac{3}{2},\frac{9}{4},\frac{45}{14},\frac{157}{35},\frac{13497}{2170},\frac{22 5161}{26040},\frac{10007591}{826770}\right\}; $$ a closed form seems difficult, but emperically the asymptotic formula $S_m \sim \frac13\big(\frac32\big)^m$ holds (with a square-root error roughly).