De Econometrist

De Econometrist neemt een statistische kijk op de wereld.

Sinterklaas drawing lots
Overig Wiskunde

Sinterklaas special: The math of drawing lots

 

It is almost that time of the year again: 5 December. In the Netherlands we also call it ‘pakjesavond’. Especially the children look forward to it throughout the whole year. A well known tradition around this time of the year is drawing lots: everybody gets a lot with the name of somebody else and you should buy a gift and write a poem for that person. An often encountered problem is that you do not draw another person but that you draw yourself. But how likely is it that this will happen?
When I first thought about this problem I thought that it would be easy to solve for an econometrician. It seemed to me as a basic probability theory problem. But when I started to think about it deeper I realized that it is not that easy. In this article I will show the mathematics behind drawing lots which actually has a really elegant solution from a mathematical viewpoint.

The problem

Let’s start off with defining the problem. You and your family members or friends are with a group of n persons where every person is denoted by a capital letter and their lot by a small lot. So, we have the set \{A, B, ... N \} of persons and the set \{a, b, ... n \} of lots. What we want to know is the probability is that nobody draws its own lot. This is given by:

    \[\mathbb{P}(\text{Nobody own lot}) = \frac{\text{Number of correct distributions}}{\text{Number of possible distributions}}.\]

The denominator part is easy, we can distribute the lots in n! different ways. This follows by the fact that we can distribute the first lot over n people, the second one over n-1 etc..
To make our life a bit easier we use some more mathematical notation: let D_n be the number of ways to distribute n lots over n persons without anyone getting his own lot.
Now we start with lot a, this lot can of course be distributed in n-1 ways. Let’s say that person B draws lot a. Then, in how many ways can lot b be distributed? There are two options in this case.

  1.  The first option is that lot b goes to person A. Then the remaining lots \{c,d, ..., n\} can be distributed over \{C,D,...,N \} in D_{n-2} ways.
  2.  The second option is that lot b goes to an other person that A. This means that we have lots \{b,c, ..., n\} which have to be distributed over \{A,C,...,N \}, where lot b cannot go to person A by assumption. But when look better at this problem we see that this is exactly the same as before but then with n-1 persons. We can just rename person A as person B since we know it can not receive lot b. Hence, the total number of ways to distribute the lot here is in D_{n-1} ways.

 

This gives in total D_{n-2} + D_{n-1}. But we also assumed that person B drew lot a which does not have to be the case, there are n-1 ways to distribute lot a. Using this, we finally get an equation where we can work with:

    \[D_n = (n-1)(D_{n-2} + D_{n-1}).\]

Writing out this equation gives us that: D_n = nD_{n-2} + n D_{n-1} - D_{n-2} - D_{n-1}. Looking better at this equation, we see a kind of symmetric relation:

    \[D_n - nD_{n-1} = (n-1)D_{n-2} - D_{n-1} = -(D_{n-1} - (n-1)D_{n-2}).\]

These two forms are identical and to show this relation we define P_n = D_n - nD_{n-1} which shows us that:

    \[P_n = -P_{n-1}.\]

So we know that P_n = - P_{n-1} = (-1)^2 P_{n-2} = ... = (-1)^{n-2}P_2. But we also know P_2, it is given by P_2 = D_2 - 2D_1 = 1 since the number of ways to distribute lots over people without anyone getting his own lot is 1 for 2 persons and 0 for 1 person. This makes our formula even easier. We get that P_n = (-1)^{n-2} = (-1)^n. So, returning to the D notation, we have:

    \[D_n - n D_{n-1} = (-1)^n.\]

At this point we are really getting somewhere. What we now want to do, is writing D_n as a direct formula without other D terms. We first apply a trick which will help us when when we write out all the equations. We divide the above equation by n!, so:

    \[\frac{D_n}{n!} - \frac{D_{n-1}}{(n-1)!} = \frac{(-1)^n}{n!}.\]

The real magic comes into play when we write this equation as a series and add them up:

    \begin{align*} \frac{D_n}{n!} - \frac{D_{n-1}}{(n-1)!} &= \frac{(-1)^n}{n!} \\ \frac{D_{n-1}}{(n-1)!} - \frac{D_{n-2}}{(n-2)!} &= \frac{(-1)^{n-1}}{(n-1)!} \\ \frac{D_{n-2}}{(n-2)!} - \frac{D_{n-3}}{(n-3)!} &= \frac{(-1)^{n-2}}{(n-2)!} \\ \vdots \\ \frac{D_2}{2!} - \frac{D_1}{1!} &= \frac{(-1)^2}{2!}\\ \mathclap{\rule{5cm}{0.4pt}} \\ \frac{D_n}{n!} - \frac{D_1}{1!} &= \frac{(-1)^n}{n!} + \frac{(-1)^{n-1}}{(n-1)!} + \ldots + \frac{(-1)^2}{2!}. \end{align*}

Note that the first term of the left hand size is always equal to the the second term of the line above and that is why they all drop. Next to that, we can simplify this by using that D_1 = 0. Furthermore we can make the equation look better by adding 1 and subtracting \frac{1}{1!}. The direct formula for D_n is given by:

    \[D_n = n! \left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \ldots + \frac{(-1)^n}{n!}\right).\]

We can now finally write down the probability that nobody gets his own lot. We get that:

    \[\mathbb{P}(\text{Nobody own lot}) = \frac{\text{Number of correct distributions}}{\text{Number of possible distributions}} = \frac{D_n}{n!} = 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \ldots + \frac{(-1)^n}{n!}.\]

Another way to write down this probability is by using a summation:

    \[\mathbb{P}(\text{Nobody own lot}) = \sum^n_{i = 0} \frac{(-1)^i}{i!}.\]

Plot

This is of course a nice formula but we do not see at first glance what would be the probability if we draw lots with 6 persons. This can easily be seen in the graph below which is generated by the software program R.

As we can see, the probability converges to a value of approximately 0.37. But this value is not some arbitrary value, it follows from some famous mathematical constant. It is equal to \frac{1}{e} = 0.3678779...! This shows the beauty of mathematics, even with a simple problem which every family encounters every year, there is a simple and elegant mathematical solution.

Conclusion

So, the next time when you are drawing lots and your friends start complaining that it takes so long to draw lots because every time someone gets his/her own lot, surprise them with this funny mathematical fact! If you even want to avoid this problem, you can also use a website to the drawing for you. Aside of the math, enjoy your ‘pakjesavond’ and make sure not to get sick from all the ‘pepernoten’!


Dit artikel is geschreven door Stan Koobs

Deel dit artikel:

By Daniele Zedda • 18 February

← PREV POST

By Daniele Zedda • 18 February

NEXT POST → 34
Share on