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.

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.
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

← Previous: Libra: Facebook's valuta Next: Are you smart enough to work at Google? →

Regression analysis: A beginner’s guide

by | Dec 19, 2023 |

Econometrics, the intersection of economics and statistics, employs sophisticated methods to analyse and quantify relationships within economic systems. One of its fundamental tools is regression analysis, a statistical technique that allows economists tot model...

Are you tying your shoelaces wrong?

by Tommiebeerm | Dec 12, 2023 |

We tie our shoelaces to ensure that our shoes stay on tight, and we do these by tying a knot. There are different ways to tie your shoelaces, you may have learnt the “around the tree” technique, but somehow, they still always come undone, why? This all has to do with...

The Dutch Childcare Benefits Scandal – How Big Data and AI Can Have Disastrous Consequences

by Bart Koopmans | Dec 5, 2023 |

Last week, the elections for the Dutch parliament took place. This election came earlier than usual since the cabinet Rutte IV had fallen due to failed negotiations about policy toward asylum seekers. The same political parties formed the previous coalition, Rutte...

« Older Entries

December 3, 2019

Share this article:

Written by secretaris

The problem

Plot

Conclusion

Read more

Regression analysis: A beginner’s guide

Are you tying your shoelaces wrong?

The Dutch Childcare Benefits Scandal – How Big Data and AI Can Have Disastrous Consequences

Menu

Office