## The Deranged Rockettes

Previously, I noted that if a line of dancers comes out on stage in a random order, then on average one dancer will be in the right spot, regardless of the number of dancers.

A more complete investigation would find the full probability distribution. What is the probability that no dancers are in the right spots, that exactly one is, that exactly two are, etc.?

This mundane question leads to a bit of math I find fascinating. There are also several clever tricks along the route.

To begin, we examine the case of no dancers in the right spot. The probability of every dancer getting it wrong is the number of ways to do that divided by the total number of possible orders. For $n$ dancers there are $n!$ total orders, so we need to know the total number of ways they could all be wrong. Some wonderful person decided to call these “derangements”, and the rest of us have been smart enough to stick with that name since.

These performers are irrelevant to the current problem because they are interchangeable. I just thought you would like this post more if it had some sort of photograph in it.

Before counting the derangements, I want to note a few things about them. The first is that once we know the number of derangements for $n$ dancers (call this $d_n$), we’ll be close to finishing the entire problem. For example, imagine we want the probability that exactly three dancers are in their correct positions. Then the rest of the dancers are in a derangement of $n-3$ dancers. So if we can count derangements, we can count any of the quantities we’re interested in.

(The probability to have exactly $m$ of $n$ dancers correct is

$((n$ choose $m)*d_{n-m})/n!$).

Next, we note that the derangements need to be a pretty significant fraction of the total number of arrangements. If one dancer is going to be in the right spot on average, then we’ll need a lot of times when no dancers are in the right spot to counter-balance times when two, three, four, or more dancers are in the right spot. So the number of derangements should grow roughly comparably to $n!$, although of course they are less than this.

Now investigate a similar but slightly different scenario. We go backstage and interview all the Rockettes, asking them what number they are in the lineup. They don’t know, so they just guess randomly. Then the probability that any given Rockette gets it right is $1/n$, and to get it wrong, $(n-1)/n$. The probability they all guess wrong is

$\left(\frac{n-1}{n}\right)^n = \left(1 - \frac{1}{n}\right)^n$.

which looks an awful lot like the definition of $e$ as $n \to \infty$. In fact it is easily proven to converge to $1/e$.

The number of derangements is a slightly different problem than the one we just solved, because when interviewing the Rockettes, their answers are assumed to be independent. But when picking an order in a lineup, they are not. For example, if Rockette three takes Rockette seven’s spot, then Rockette seven’s chances of getting her spot correct are zero. However, as the number of Rockettes becomes very large, the chance of this happening gets very small, and so the problem feels like it’s almost independent.

Let’s make a conjecture, then. The number of derangements of $n$ dancers, $d_n$, converges to $cn!$ for large $n$, with $1/c$ very close to $e$.

The actual answer to the number of derangements is a little bit clever. I’ll explain in video form:

If you can’t or aren’t inclined to watch, here is the text of the derivation from Wikipedia:

Suppose that there are n persons numbered from 1,2,…,n. Let there be n hats also numbered from 1,2,…,n. We have to find the number of ways in which no one gets the hat: having same number as that of his/her number. Let us assume that first person takes the hat i. There are n − 1 ways for first person to choose the number i. Now there are 2 options –
– Person i takes the hat of 1. So Now the problem reduces to n − 2 persons and n − 2 hats.
– Person i does not take the hat 1. This situation can be simulated as renumbering hat 1 as i. So now case is equivalent to solving problem with n − 1 persons n − 1 hats.
From this, following relation is clear:

Fine, then. Let’s test our conjectured $d_n$ against the recursion relation.

$\begin{array}{rl}d_n & = cn! = (n-1)(d_{n-1} + d_{n-2}) \\ {} & = (n-1)(c(n-1)! + c(n-2)!) \\ {} & = c(n-1)([1+(n-1)](n-2)!) \\ {}& = c(n-1)(n)(n-2)! \\ {} & = cn!\end{array}$

So we’ve at least failed to invalidate our asymptotic estimate. I like it when I fail to invalidate my conjectures. It reminds me that everything might be okay.

We still haven’t found our coefficient $c$, that was supposed to be about $e$. Let’s go through it in a few steps, working with the recursion relation.

A two-step recursion relation with nonlinear coefficients is hard. A one-step relation might be easier. So we work things out like this:

$d_n = (n-1)(d_{n-1} + d_{n-2})$

$d_n - nd_{n-1} = -d_{n-1} + (n-1)d_{n-2}$

This makes it so the right hand side is pretty much the same as the left, but with $n$ reduced by one. Specifically, if we define

$u_n \equiv d_n - nd_{n-1}$

then the recurrence relation above is

$u_n = -u_{n-1}$.

Because $d_2 = 1$ and $d_1 = 0$, we know $u_2 = 1$ and therefore

$u_n = 1, \qquad n$ is even

$u_n = -1, \qquad n$ is odd.

This can be abbreviated by

$u_n = -1^n$

which we replace by

$d_n - nd_{n-1} = -1^n$.

These chickens used to be free, but they have now been de-ranged.

We gone from a recurrence relation with two terms down to just one. Next clever step is to divide by the asymptotic behavior, $n!$.

$\frac{d_n}{n!} - \frac{d_{n-1}}{n-1}! = \frac{-1^n}{n!}$.

To clean things up, let’s define

$a_n \equiv \frac{d_n}{n!}$

whence

$a_n - a_{n-1} = \frac{-1^n}{n!}$.

Now we’re going to do a long column adding-thingy, which hopefully you’ve seen before so my sucky explanation doesn’t detract much

$\begin{array}{ccc} a_n - a_{n-1} & = & \frac{-1^n}{n!} \\ a_{n-1} - a_{n-2} & = & \frac{-1^{n-1}}{(n-1)!} \\ \vdots \\ a_2 - a_1 & = & 1 \end{array}$

Add all those equations to each other, and everything on the left cancels except the very beginning and very end of the chain, leaving us with

$a_n - a_1 = \sum_{k=1}^n \frac{-1^{n-1}}{n!}$

I re-arranged the terms on the right to look more familiar. The summation on the right is just the power series of $e^x$ with $x = -1$. Also $a_1 = 0$ so

$\lim_{n \to \infty} a_n = \frac{1}{e}$.

We defined $a_n = d_n/n!$, so the asymptotic form of the number of derangements is $d_n = n!/e$, exactly the same answer as to the separate problem about independently interviewing the Rockettes backstage.

There’s an explanation begging to be found here. It’s obvious the two questions should have similar answers, but not immediately obvious to me they should be the same.

Two events $A$ and $B$ are independent when $P(A \cap B) = P(A)P(B)$. Let the two events be that Anne and Bubbatunde (who are first and second in the Rockette’s lineup) are in the wrong spot, respectively. Then $P(A) = P(B) = (n-1)/n$, so

$P(A)P(B) = \left(\frac{n-1}{n}\right)^2$

To find $P(A \cap B)$, count the ways they can both be wrong. If Anne takes Bubbatunde’s spot, then Bubbatunde can pick any of the remaining places, because her spot is already occupied so all the remaining ones are safe. That’s $(n-1)$. Then if Anne chooses a different spot (of which there are $(n-2)$), then Bubbatunde has two forbidden spots: the one Anne is already in, and her own. That makes $(n-2)^2$ ways for this to happen. So the total number of ways for Anne and Bubbatunde both to get it wrong is $(n-1) + (n-2)^2$.

The total number of ways Anne and Bubbatunde could pick their spots is $(n)(n-1)$, so $P(A \cap B)$ is given by

$P(A \cap B) = \frac{(n-1) + (n-2)^2}{n(n-1)}$.

To get an idea of how nearly independent events $A$ and $B$ are, let’s look at

$P(A \cap B) - P(A)P(B) = \frac{1}{n^2(n-1)}$,

where I have simplified the algebra. This goes to zero fairly quickly as $n \to \infty$, so the condition for independence holds in the limit of large $n$, showing why the two different problems have the same answer in this limit.

Finally, we can answer the original question about the full probability distribution. Plugging in the asymptotic form for $d_n$ into the expression we derived earlier and simplifying, we get

$P(m) = \frac{1}{e * m!}$

where $P(m)$ is the probability to have exactly $m$ Rockettes in the right spot. All the $n's$ have canceled out, showing that for large numbers of Rockettes, the probability distribution settles down to a fixed distribution independent of $n$. Surely this distribution has a special name. Does anyone out there on the internet want to drop me a comment?

Now if we could only find an infinite supply of Rockette fuel to feed them…