Birthday Paradoxes

Posted by maycontainmaths

If people’s birthday are distributed evenly throughout the year, how many people do you need to put into a room to have a decent chance of a shared birthday? This is the classic birthday problem, and gives rise to an apparent paradox: the number is far, far lower than most people suspect! This is the known as the Birthday Paradox. Let’s work out what the number is.

The Original

Imagine placing $n$ people walking into a room, one by one. We’ll work out the probability $q_n$ that no two people share a birthday at the end of the process.

The first person who walks in will not share a birthday with anybody else, since there is nobody else in the room.
The second person has probability $1-\frac{1}{365}$ of not sharing the first person’s birthday, since only one day is already taken.
Given that the first two did not share a birthday, the third person has probability $1-\frac{2}{365}$ of not sharing a birthday with the first and second, since two days are taken.
Skipping ahead, given that all previous people had no birthday in common, the last person has probability $1-\frac{n-1}{365}$ of not sharing a birthday with any of the previous people.

This gives us $q_n=(1-1/365)\ldots (1-(n-1)/365)$ . For the probability of a shared birthday to be greater than 50%, we need $q_n<\frac{1}{2}$ . With a pocket calculator, you can find out that the smallest number of people for at least a 50% chance of a shared birthday, is 23. But there’s a neater way than brute force.

Since $1-x \leq e^{-x}$ , we have

$q_n \leq e^{-1/365} e^{-2/365} \ldots e^{-(n-1)/365}$

$= e^{-n(n-1)/(2\times 365)}$

If we want $q_n<\frac{1}{2}$ , we can take logs and see that $n^2 - n > 2\times 365 \times \log 2$ . Solving this quadratic inequality shows that $n > \frac{1}{2} + \sqrt{\frac{1}{4} + 2\times 365 \times \log 2 }$ . If you work it out, this number is just less than 23.

There’s no reason we have to stick to 365 days in a year either. If we consider a more general collision problem, with $n$ balls thrown at random into $N$ pots, then the number of balls we require for at least a 50% chance that two share the same pot is

$n > \frac{1}{2} + \sqrt{\frac{1}{4} + 2\times N \times \log 2 } \sim \sqrt{2N \log 2}$

We could have asked a slightly different question: How many people, on average, are required before we get a shared birthday, or collision? Interestingly, the answer to this is different, approximately $\sqrt{\frac{\pi N}{2}}$ .

Another Birthday Paradox

Here’s another interesting paradox related to birthdays that I found here. Let’s say that this time, the people are split into two groups, boys and girls for example. This time, it isn’t enough to have a shared birthday; we want a shared birthday between a boy and a girl. We can push boys and girls into the room and ask how many we require, on average before getting a boy and girl with the same birthday. We can also ask questions about the proportion of boys and girls. You might reasonably expect that equal proportions are best.

But why not make things a little more interesting? What if instead of throughout the year, all of the boys’ birthdays were uniformly randomly distributed in January? How many people then, and what proportion? You might expect that more boys than girls are needed.

It turns out that this doesn’t really change anything! Equal proportions are always best! Check out this paper to find out why.

The Surprise Test Paradox

Posted by maycontainmaths

As promised, today’s blog post is about the Surprise Test Paradox. A quick recap:

On Friday, a teacher says to their class that on some day during the next week, there will be a surprise test. However, the students make the following deductions:

The teacher can’t wait until next Friday, otherwise the test won’t be unexpected, so a Friday test is impossible.
Having eliminated Friday, Thursday is now the last possible day for the test to occur.
Rinse and repeat. We eliminate all possible days of the week, so a surprise test is impossible!

However, the teacher sets a test on Wednesday, to the surprise of all the students.

Why did I put off this blog post, promising to talk about it some time before the New Year? To illustrate the paradox for real. Despite any readers of this blog being able to follow the same logic as the students, you had no idea when I was going to make this post. So is there a problem with the above logic?

What follows is heavily inspired by an excellent article written by Timothy Chow.

Essence of the Paradox

Here are a few observations which try capture some subtleties in the premise of the paradox.

In the story, the teacher sets the test on Wednesday. The choice of Wednesday isn’t important at all. Indeed, as soon as the students had convinced themselves that there would be no test, the teacher would have been able to surprise them on any day of the week. This doesn’t resolve the situation, in that it doesn’t find a flaw in the reasoning process. In fact, it’s wholly unsatisfactory. The correct reasoning of the students convinces them that no surprise is possible, which makes a surprise possible, somehow rendering their correct conclusion incorrect…

What the last paragraph does usefully illustrate is that ‘surprise’ might depend on all kinds of things, like the students’ current states of reasoning, as well as their knowledge of the teacher’s announcement. Surprise and knowledge are very vague and tricky concepts to try and pin down logically.

For example, we can blame the teacher for announcing the test to begin with. The implicit Step 0 in the student’s reasoning is their knowledge that a test will occur (even more than this, their trust in the teacher’s announcement).

The students’ argument also uses the fact that there is a ‘final day’ on which the surprise test can happen. If the teacher had merely promised them a surprise test in the future, there would be no paradox. Their reasoning would not make it past Step 1.

Resolution?

Two essential features of the paradox are the announcement of the test, and the fact that there is a “final day”. So let’s consider the simplest possible case (in fact, this is the case that the students arrive at):

On Friday, the teacher announces “There will be a surprise test on Monday!”

Of course, this statement is badly written. Most humans would probably now interpret the “surprise” as pertaining to the content or length of the test, rather than the day on which it was to be held, since the teacher has stated this. Slightly better:

On Friday, the teacher announces “There will be test on Monday. On Monday, the timing of the test will come as a surprise to you!”

Taken in the context of the original paradox, this statement is clearly absurd. It seems as though the teacher is at fault for giving the students a contradictory statement. We could say the same for the original. A precise way of reformulating the teacher’s announcement is:

On Friday, the teacher announces “There will be a test next week. It is not possible to deduce the day of the test from this announcement”

Self-reference. The teacher might as well have said “This is not an announcement”. Actually, you can go through the formal steps as Chow does, and phrase even this self-referential statement mathematically using Godel numbering and such things. The conclusion is still that the announcement is contradictary.

Conclusion

The self-reference argument is just about good enough for me. Reformulating the announcement seemed to clear things up quite a lot. But unfortunately, the teacher’s statement is justified undeniably after the fact, logically ridiculous until it comes true. Isn’t this as bad as our observation before, with the correct reasoning of the students becoming incorrect only later?

There is no universally accepted resolution to the surprise test paradox. But that’s the one that I like the best.

The Waiter Paradox

Posted by maycontainmaths

Today, I’ll discuss one of my favourite paradoxes, and unravel it. It’s called the Waiter Paradox.

What is a Paradox?

The dictionary definition says that a paradox is “A seemingly absurd or contradictory statement or proposition which when investigated may prove to be well founded or true”.

The Waiter Paradox

The following is taken from the Paradox section of www.curiouser.co.uk (it’s called the Missing Pound Paradox here, but I always thought that the Waiter Paradox sounded more catchy).

“Three ladies go to a restaurant for a meal. They receive a bill for £30. They each put £10 on the table, which the waiter collects and takes to the till. The cashier informs the waiter that the bill should only have been for £25 and returns £5 to the waiter in £1 coins. On the way back to the table the waiter realises that he cannot divide the coins equally between the ladies.

As they didn’t know the total of the revised bill, he decides to put £2 in his own pocket and give each of the ladies £1.

Now, each of the ladies paid £9. Three times 9 is 27. The waiter has £2 in his pocket. Two plus 27 is £29. The ladies originally handed over £30.

Where is the missing pound?”

Where indeed?

Resolution

The “Paradox” here stems from a misrepresentation of the facts, leading to some bad counting. Let’s do some simple book-keeping.

We’ll call the ladies $L$ , $M$ and $N$ . The waiter will be $W$ and the cashier will be $C$ . The amounts of money held by all parties at any time will be stored like this: $(L,M,N,W,C)$

Ignore all the rest of the money involved, like other money that the ladies and waiter are carrying, and the rest of the money in the cashier’s till. It’s not important because we only want to keep track of £30. At the start, each lady has £10.

$(10,10,10,0,0)$

The waiter collects the money.

$(0,0,0,30,0)$

The cashier takes £25 for the meal and returns £5 to the waiter.

$(0,0,0,5,25)$

The waiter returns £1 to each lady.

$(1,1,1,2,25)$

We started with £30 in circulation and we end this way too. Clearly there’s no missing pound here. So where does the paradox come from? It’s true that each lady paid £9. It’s true that 3 times £9 is £27, and it’s true that the waiter has £2 at the end.

It’s also true that £2 plus £27 is £29, but why are we adding these numbers together? The ladies have paid £27 in total, of which £25 is with the cashier and £2 is with the waiter. So the £2 held by the waiter is already included in the £27. Why would we add it on again? What we should be adding is the money that the ladies have not paid; the £3 that they got back in change. This makes £30. There’s no paradox, just bad book-keeping.

More Paradoxes: The Suprise Test Paradox

On Friday, a teacher says to their class that at some point during the next week, there will be a surprise test. However, the students start thinking about this:

The teacher can’t wait until next Friday for the exam, because then the test won’t be unexpected. So it can’t be Friday.
Since we’ve removed Friday from the possible test days, the same logic applies to Thursday.
By repeating this logic, we removed all the possible test days.
So, it turns out that the teacher can’t give a surprise test at all.

However, the teacher sets a test on Wednesday and all the students are surprised! Teachers can certainly give surprise tests, as anybody who has experienced one will tell you. So where did the students go wrong? The Surprise Test Paradox is subtle and much harder to pin down than it first appears. Have a think about it.

I’d like to take this opportunity to announce that I’ll be writing a surprise blog article on this paradox, at some point before the end of 2014. See you next week!

More paradoxes may be found at http://www.curiouser.co.uk/ and http://www.paradoxes.co.uk/.