Tag Archives: mathematics

Happy Birthday! Another Maths Paradox To Test Your Mind

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.

Counting backwards

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.

 

16

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

Probability isn’t as simple as just heads or tails, especially when we think about big numbers. Image courtesy of Flickr.

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.

image11

(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!

What’s Next?

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

Sources

  1. Su, Francis E., et al. “Pigeonhole Principle.” Math Fun Facts. <http://www.math.hmc.edu/funfacts>
  2. http://mathforum.org/dr.math/faq/faq.birthdayprob.html
  3. https://www.geeksforgeeks.org/birthday-paradox/
  4. http://www.math.cornell.edu/~mec/2008-2009/TianyiZheng/Birthday.html
  5. http://mste.illinois.edu/activity/birthday/
Advertisements

How Good Are You At Simple Maths? Maybe Not As Good As You Think.

Mathematics is not always as simple as two and two making four. Some particular problems are so counter-intuitive that they’ll make your head spin. And we aren’t talking about quantum physics or binomial equations, we are talking about simple fractions. Something you would have learned in Primary School. The most famous of these is the Monty Hall Problem, though there are plenty more. The mind does funny things when faced with problems of ‘chance’. and these brief thought experiments demonstrates how bizarre probability can be. So we will place a bet, if you get this wrong, give it a share.

A Good Problem

The Monty Hall problem refers to a US 1960’s game show called ‘Let’s Make A Deal‘ whose host was Monty Hall. The show involved three doors. In this case, a goat, another goat, and a roadster. When we talk about the statistics problem, we can imagine that we are contestants on ‘Let’s Make A Deal‘. There are three doors with three prizes, and we want to guess the best door for the best prize. We could win one of two goats or a roadster. We want the roadster, so we wish to maximise our chances of making the ‘right guess’.

Your chance here of picking the roadster, based on the knowledge you have, is 1/3. One door in three. Pretty simple. But let’s make it a little harder. The host, Monty Hall, shows us the prizes and shuffles them behind doors number 1, 2 and 3. After some thought, we decide to pick the second door. We’re about to open the door, when the host (who knows where everything is), opens the third door to reveal one of the goats. He then asks us “Do you want to change your mind?” (i.e do you want to stay with door number 2, or switch to door number 1.)

So what do you do? Do you stay or switch? It seems like a 50/50 chance of winning the roadster. But actually, it isn’t. There is a hidden factor. But, you can make a decision here which increases your chances of winning. Figured it out yet? This is the Monty Hall problem. Is it to our advantage to switch our selection? If you haven’t heard of the problem before, think about it while I explain the history to you. The puzzle was first posed in an American mathematical magazine, with the answer appearing later down the line. The answer, being not what you’d expect, caused a media furore against Marilyn Vos Savant, the woman who’d explained the solution.

Are you ready for the answer?

A Simple Paradox

Believe it or not, the best move is to switch doors. You know door 3 has a goat behind it, so door 1 and 2 are left. So you switch to door one, and it is opened to reveal the luxury red roadster. But why was it beneficial to change your mind here?

In the beginning, the roadster has a 1/3 chance of being behind each door.

1      2      3

1/3    1/3    1/3

You pick 2, which has equal probability of being any of the prizes that point, a third chance. The host, then reveals to you a goat.

1        2         3

1/2    1/3    Goat

At this point, your original choice remains one in three whereas the other door has half of chance of being the roadster. The answer lies with the assumptions of the problem. As the host is aware of where each prize is hidden, he cannot open a door to reveal a roadster (he would lose the show money! He has all of the information and by revealing the goat to you, he imparts some information which alters the balance of probability. As one mathematician points out: “Probabilities are expressions of our ignorance about the world, and new information can change the extent of our ignorance.” This is the simpler version of the proof, but requires a little more heavy work to explain it fully.

goat monty hall maths paradox

Do you want a Goat, or a Roadster? You can cuddle either, and ride both. But one bites. Image courtesy of Tamsin Cooper

So bear with us.

The Best Solution

They key to solving the problem is the following assumptions:

  1. At the start you have a 1/3 chance of getting the roadster and a 2/3 chance of getting a goat. So you picked a door (door 2 in this case.)
  2. The host opened a door (door 3 in this case,) which had a goat behind it.
  3. The host will not help you win, so his behaviour would directly effect your chances of winning the roadster.
  4. So at this point instead of the remaining doors having a 50:50 chance, you must now account for another factor, the probability that the host may force you to lose.
  5. By multiplying together the probabilities, you can get a clear answer of the ‘best’ door to pick.
  6. Remember,  you don’t know what is behind your door (2), or the other one (3.)

Take a moment to read that again. You aren’t dealing with just a 1/3 chance anymore, you are dealing with a multiplicity of uncertainty where you must account for a combination of the hosts effect on outcome (1/2) and your original choice of winning (1/3.) So let’s see what happens when you apply the math in each case. Each fraction is here is your chance of winning if you switch in each case;

1: You picked a goat (2/3 chance of doing so). The host reveals the remaining goat behind door (1/2 of doing so), he cannot reveal the car. (2/3 x 1/2 = 1/3) Your chance of winning is 1/3.

2: You picked a car (1/3 chance of doing so). The host reveals a goat behind door 3 (1/2 chance of doing so). (1/3 x 1/2 = 1/6) Your chance of winning is 1/6.

3: You picked a car (1/3 chance of doing so). The host reveals a goat behind door 2 (1/2 chance of doing so). (1/3 x 1/2 = 1/6) Your chance of winning is 1/6.

4: You picked a the other goat (2/3). The host reveals the remaining goat behind door 2 or 3 (1/2) again, he cannot reveal the car. (2/3 x 1/2 = 1/3.) Your chance of winning is 1/3.

So now we can add the probabilities together. If we talk options 1 and 4 (i.e you picked either goat,) your chance of winning by switching = 1/3 + 1/3 = 2/3.  If you picked a car, (options 2 and 3) then your chances of winning by switching are 1/6 +1/6 = 2/6 = 1/3.  So comparing the probabilities, if you pick a goat door, and the host doesn’t want you to win, then you best switch (2/3 chance of winning. If you picked the car door, and the host doesn’t want you to win, you best not switch (1 – 1/3 = 2/3.) Admittedly, and some of you may have spotted this already, if the host was not biased, or wanted you to win, the answer may be different. Let us know what you find in the comments below.

goat roadster monty hall problem paradox

Einstein may even have had trouble with this one.
Image courtesy of Tom Haex

If this still sounds strange to you, don’t worry; you’re not alone. After Vos Savant published her proof, many attacked her and claimed that she was wrong despite many simulations and proofs. Even the (arguably) greatest mathematician alive at that point Paul Erdős wasn’t convinced at first. This is an example of veredical paradox; that is, a situation or result which at first appears to be wrong but can be demonstrated to be true. How many of your friends do you feel would get it right first time?

What’s Next?

  • Getting your mind blown was just the beginning when you consider that we probably live in a simulation
  • Follow Ben on Twitter so you never miss an article from drbenjanaway.com. Or join our mailing list.
  • Give this a share if you found it interesting.

The opinions expressed in this article are those of Dr George Aitch and Dr Janaway alone and may not represent those of their affiliates. Images courtesy of flickr. Note from the Editor:  I had to write this out and work out the fractions myself before I was convinced (lights cigarette, stares blankly into the sea listening to soft circus music.)