Continuing on our theme of head-breaking maths, I’d like to present another example of probability gone wrong.
For this experiment, we’re going to need to gather twenty two of your friends at random. Hold a party in your kitchen (or any way you can snugly fit twenty three people).
Well done Mr Popular, but did you know that there is half a chance that one of you shares a birthday?
This is the Birthday Paradox; that in a set of twenty three people selected randomly, there is a 50% chance that two will share a birthday. Seem unlikely? Let us explain.
To demonstrate how this works, we’re going to need to scale things up for a second.
Instead of imagining your kitchen or classroom, think about a ballroom (those from The Shining or Titanic will do nicely) and instead of twenty three of your friends, I want you to invite three hundred and sixty six.
(That’s got to fit 367 people, surely?)
Once you’ve crammed all of these people into one room, you can be certain that two of them will share a birthday. How do we know this?
There are only 366 possible birthdays (including February 29th on a leap year), even if somehow you managed to find one person whose birthday was on a different day of the year for the first 366, if you were in the room, one of them would have to share a birthday with you (of course, in real life, some birthdays are more common than others).
In discrete mathematics, this is called the Pigeonhole principle. If you have x pigeons and y pigeonholes, where x > y, then at least two pigeons are going to have to buddy up.
This sounds pretty simple, but gets fairly odd when we introduce the idea of infinity and upwards, but that’s for another article.
Half A Chance
Going back to our party in the ballroom, there are either one of two probabilities; that someone in that room shares a birthday with another or nobody does. These are mutually exclusive; they cannot both be true.
If we calculate this probability, we see that it is in fact comprised of several more, one for each person. The probability that nobody in the room shares a birthday can be split down into the probability that Person A doesn’t share a birthday and then Person B and so on.
In probability, we can express mutually exclusive outcomes as:
Probability something happens + probability something doesn’t happen = 1
P + not P = 1 or P + ‘P = 1
In our paradox, either at least two people in that room share a birthday (B) or no-one does (‘B)
The probability that nobody shares a birthday then can be displayed as:
‘B = 366/366 x 365/366 x 364/365 …
And so on, for each of people in the room we are comparing to. Each comparison leads to a smaller and smaller value of ‘B (that nobody shares a birthday).
We know that the first person can have any birthday in the year without invalidating the probability that none of them do. The second may only have a birthday on all of those days minus the one which the first person has the birthday.
The next person has one less day and so on and so on. A simpler way of writing this is:
‘B = 366!/((366-n)!x366^n)
Where n is the number of people in the room. If the value is 367, then we may be certain that two people share a birthday (though at 70, the odds are 99.9%).
If the value is set at 23, the probability works out roughly as 0.5, which is half a chance.
You can work it out with different sizes here.
(Here’s a graphic representation from Cornell University)
The Birth of the Paradox
This paradox was featured as part of a maths puzzle in Scientific American in 1957. It had been separately been proposed by mathematicians Harold Davenport and Richard von Mises prior to this.
But why should we care about all of this? Why do we celebrate birthdays? As well as being a strange piece of probability, there is a real world application in hacking called the birthday attack.
It involves attacking the way data can be encrypted via a hash function – stealing data or passwords. If two people are sending data to each other, it will be encrypted with each at both ends able to translate the code via a hash function.
The birthday attack examines the way that two pieces of information may be encoded in the same way, much like two people sharing the same birthday.
The attack means all the hacker needs to do is find any matching pair before and after encryption rather than any single pair. This reduces the time taken to break into a system and is so much more important than it may seem at first!
- More maths to bend your mind.
- Follow Ben on Twitter so you never miss an article from drbenjanaway.com
- Give this a share if you found it interesting.
- Let me know what you think in the comments below or on social media.
- Donate. For just the price of a coffee you can help us Change The World.
The opinions expressed in this article are those of George Aitch and Dr Janaway alone and may not represent those of their affiliates. Images courtesy of flickr.
- Su, Francis E., et al. “Pigeonhole Principle.” Math Fun Facts. <http://www.math.hmc.edu/funfacts>