Monthly Archives: November 2021

Squid Game expectation

Posted on by
Reply

Warning: This post is motivated by the Netflix series Squid Game, and contains significant spoilers. I just recently watched the show, and really enjoyed it, so if you haven’t yet seen it, you may want to skip this article.

Suppose that you are one of n=16 competitors who must cross a bridge of s=18 steps. The steps are far enough apart that you must jump from one to the next… and at each step you must choose which of two side-by-side glass squares to jump onto: one square is tempered glass that is strong enough for you to safely jump onto, while the other square is normal glass that will break if you step on it, causing you to fall to your death and out of the competition. The glass squares are otherwise indistinguishable, so that players must guess which square to jump onto at each new step.

Each player in turn attempts to cross the bridge. The first player has a tough road ahead, safely crossing with a probability of only 1/2^{18}. But each subsequent player observes the progress of all previous players, noting which squares at each “explored” step are safe and which are deadly.

Last week’s FiveThirtyEight Riddler column asked for the expected number Y of surviving players. Let’s turn this around, and instead consider the expected number X=n-Y of eliminated players, since the analysis and resulting formulas turn out a bit nicer that way.

I think this is a nice problem for several reasons. It can be an engaging problem for students as a, uh, “real-world application” of probability and expected value. It’s easy to simulate as a programming exercise; and there are several analytical approaches to solving the problem as well. The Riddler solutions describe a recurrence relation, as well as a relatively nice summation:

E[X] = n - \frac{1}{2^{s}}\sum\limits_{k=0}^n (n-k){s \choose k}

yielding 589819/65536, or 8.9999237060546875 players eliminated on average.

But the fact that the expected value is so close to 9– so close to half the number of steps– is not a coincidence. This seems like a great example application of linearity of expectation, that in this case allows us to solve the problem with just paper and pencil.

Let X_1, X_2, \ldots, X_s be indicator random variables, each equal to 1 if and only if some player is eliminated at the corresponding step, so that X=\sum X_j, and thus

E[X] = \sum\limits_{j=1}^s E[X_j] = \sum\limits_{j=1}^s P(X_j=1) .

The key observation is that “most” of these probabilities are exactly 1/2. More precisely, as long as j \leq n, someone must encounter step j, and whoever does encounter that step for the first time will be eliminated with probability P(X_j=1)=1/2.

So if there are at least as many players as steps, i.e. n \geq s, then the expected number of players eliminated is exactly E[X]=s/2.

In the actual game, however, there are two “extra” steps. As described above, the first 16 steps contribute exactly half a player each to the total expected number eliminated. But the 17th and 18th steps require more careful analysis, because it is possible that one or both of these steps may not be encountered at all.

For example, consider the worst possible outcome, where the first player is eliminated on the first step, the second player on the second step, and so on, with the 16th and final player being eliminated on the 16th step, so that the 17th (and 18th) step is never reached. This happens with probability 1/2^{16}, and so

P(X_{17}=1) = (1-\frac{1}{2^{16}})(\frac{1}{2})

We handle the 18th step similarly. In addition to the above situation where neither the 17th nor 18th step is reached, there are 16 equally likely ways for the last player to be eliminated on the 17th step (according to which one of the first 16 steps is guessed correctly by some player), so that

P(X_{18}=1) = (1-\frac{1}{2^{16}}-\frac{16}{2^{17}})(\frac{1}{2})

Adding to the 16/2=8 expected eliminations from the first 16 steps yields the desired E[X]=589819/65536.

Granted, it is fortunate that there are only two more steps than players, because the resulting general formula for the expected number of players eliminated:

E[X] = \frac{1}{2}\sum\limits_{j=1}^s (1-\frac{1}{2^{j-1}}\sum\limits_{k=n}^{j-1}{j-1 \choose k})

looks more complicated than the summation presented earlier.