# Expected number of turns for SPROUT

As a mathematical father (and with apparently plenty of time on my hands) I long ago computed the expected number of turns for a number of children's games that are effectively Markov maps. (Chutes and Ladders, Hi Ho! Cherry-O, Candy Land, etc.) And I've seen this and similar posts. (The TLDR version for this technique is that you have to diagonalize a matrix.)

My, now older, son has introduced me to a new game and I was wondering about its expected number of turns. The game is SPROUT and it's rules are as follows:

1. $n$ players play a game similar to every-man-for-himself dodge ball.
2. Initally a ball is put into play and all players are free to run around the playing field.
3. Free players can pick up the ball, take up to three steps with the ball, and throw it at another free player--if they hit the target that player is frozen and must sit down. If the target instead catches the ball then the Thrower is frozen and must sit.
4. A frozen player is freed if the player that froze them becomes frozen. The freed player "sprouts" back up.
5. The game ends when all players but one are frozen, this can only happen if that single free player has managed to freeze every every player.

Apparently with 30 kids or so this game almost never ends. It's a great game to play I guess because the kids get exercise, but even if you get "out" or frozen, it's usually not long until you are back in the game. And you have a sweet sense of retribution at the moment of your freedom.

Assuming that a turn of this game consists of one random free player freezing another random free player (and simultaneously freeing all the players that the newly frozen player had previously frozen), how many turns do we expect a game of $n$ players to take?

This is harder to analyze because the state of the game is not just the number of free players and the number of frozen players, we must remember who froze whom so we can free the captives if their opressor ever becomes frozen. I can run numerical simulations for this but I'd be much more satisfied with an analytical understanding.

Here's what I've done so far:

We can keep track of the state of the game by an $n$ long vector that tracks the state of each player. Let a zero in position $i$ denote that player $i$ is free and a number from $1$ to $n$ represents the freezor of the frozen player $i$. Initialize the state to be all zeros. $$\{0,0,0,0,0,0,0,\ldots,0\}$$ At any later turn the state will be a combination of zeros and integers from $1$ to $n$ (e.g. $\{0,1,5,5,0\}$ ) but we also have the property that any non-zero integers appearing in the state vector imply that there are zeros in those positions of the state vector as well (due to property 4 above).

This means that there are $$\sum_{k=0}^{n-1}{n \choose k}(n-k)^k$$ total states, including the initial state (which is never returned to) and the $n$ final states (one for each possible winning player).

This number is crazy big but I imagine that these states are sparsely connected since I have seen a game of ten boys completed. (Maybe one boy was just really superior at the game??)

I'd appreciate any feedback on my analysis. Am I thinking about this correctly? Is this just gonna be a hard problem? Is it really an easy problem??

Thanks

Update:

Upon further inspection I realize that there are actually far fewer states. If I do not care about player identity, only the total number of turns, I can relable my players as needed so that they are ordered with the free player indices lower than the the frozen players and each group further ordered as follows. For the free players let player 1 be the player in the "lead" i.e. the one who has frozen the most, let player 2 be the next according to this order and so on for $k$ free players. For the frozen players (beginning at index $k+1$) let them be ordered by the index of their Freezor. e.g. $$\{0,0,0,0,1,1,1,2,2,3\}$$ Then the states are just ordered lists of non-negative integers with the only properties that

• The last element is not greater in value than the number (count) of zeros.
• The non-zero integers are monotonically non-decreasing in count. (Never fewer ones than twos, etc.)

This drastically reduces the number of states but I do not yet have a good count of this.

• It looks like a hard problem to me. I think you correctly evaluated the number of states, and even though the matrix connecting them is sparse, it will be very hard to analyze even for relatively small values of $n$... – 5xum Apr 22 '15 at 13:35
• Thanks @5xum, I realized that I didn't need to keep track of players' identities specifically for my question so the number of states is much smaller. I updated the post in light of this. – amcalde Apr 22 '15 at 14:06

Note that unless you're distinguishing between the players in some way (e.g., modeling their different skill levels), then their identities don't matter, and you can work with a much smaller number of states.

To see how this works, imagine that each live player is "stuck" to all the players that he has frozen. So if a live player has frozen $n$ other players, he looks like a blob of $n+1$ players running around. A blob of size $m$ represents one unfrozen player and the $m-1$ players that he has frozen. As a state of the game is just a partition of the players into blobs, the number of states with $n$ players is exactly the number of integer partitions of $n$. When a live player is hit, he becomes frozen, and all the players that he previously froze become live players that never froze anyone. In the blob language, this means that when (the single unfrozen member of) a blob of size $m$ freezes (the single unfrozen member of) a blob of size $n$, we get one blob of size $m+1$ and $n-1$ blobs of size one.

In short, the rule is the following:

Start with a partition of $n$ into $n$ $1$'s. Each turn, choose two different components of the partition at random. Add one to the first component; subtract one from the second and then, if its size is still greater than $1$, break it into $1$'s. The game is over when the partition has a single component.

Because the number of states is reasonably small (when $n=10$ there are $p(10)=42$ states; when $n=30$ there are $p(30)=5604$), this game should be amenable to a Chutes-and-Ladders-style analysis.

Update:

The expected length of the game turns out to have a surprisingly simple form; presumably there is an elegant proof of this, but I haven't found it. For $n=2$, the game is over in one turn. For $n=3$, the game state is $(2,1)$ after one turn; it then stays $(2,1)$ with probability $1/2$ and ends with probability $1/2$ each subsequent turn, so the expected duration is $1+2=3$. This pattern continues: the expected duration with $n$ players is exactly $2^{n-1}-1$. Moreover, the expected time remaining from any state appears always to be an integer.

• Thank you! This is a great new way for me to think about this. Give me a moment to digest. – amcalde Apr 22 '15 at 14:10
• My kids, in Oregon, play this game too :). They call it "Sproutball". – mjqxxxx Apr 22 '15 at 17:12
• There is another question on this site with an equivalent game, and the answer includes an elegant proof: math.stackexchange.com/q/2455288/19328 – A. Rex Oct 17 '18 at 16:49