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.
Let’s start off with defining the problem. You and your family members or friends are with a group of persons where every person is denoted by a capital letter and their lot by a small lot. So, we have the set of persons and the set of lots. What we want to know is the probability is that nobody draws its own lot. This is given by:
The denominator part is easy, we can distribute the lots in different ways. This follows by the fact that we can distribute the first lot over people, the second one over etc..
To make our life a bit easier we use some more mathematical notation: let be the number of ways to distribute lots over persons without anyone getting his own lot.
Now we start with lot , this lot can of course be distributed in ways. Let’s say that person draws lot . Then, in how many ways can lot be distributed? There are two options in this case.
- The first option is that lot goes to person . Then the remaining lots can be distributed over in ways.
- The second option is that lot goes to an other person that . This means that we have lots which have to be distributed over , where lot b cannot go to person by assumption. But when look better at this problem we see that this is exactly the same as before but then with persons. We can just rename person as person since we know it can not receive lot . Hence, the total number of ways to distribute the lot here is in ways.
This gives in total . But we also assumed that person drew lot which does not have to be the case, there are ways to distribute lot . Using this, we finally get an equation where we can work with:
Writing out this equation gives us that: Looking better at this equation, we see a kind of symmetric relation:
These two forms are identical and to show this relation we define which shows us that:
So we know that . But we also know , it is given by 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 . So, returning to the notation, we have:
At this point we are really getting somewhere. What we now want to do, is writing as a direct formula without other terms. We first apply a trick which will help us when when we write out all the equations. We divide the above equation by , so:
The real magic comes into play when we write this equation as a series and add them up:
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 . Furthermore we can make the equation look better by adding 1 and subtracting . The direct formula for is given by:
We can now finally write down the probability that nobody gets his own lot. We get that:
Another way to write down this probability is by using a summation:
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 ! 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.
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