probability

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.

So, you’re wandering through the Old West, accidentally stumble into an unfriendly saloon, and find yourself at the wrong end of the barrel of a gun. As your life flashes before your eyes, you find yourself wishing that you’d paid more attention in your maths classes…

But fear not! In this post, we’ll go over the best strategy for winning a simple gunfight. Who knows? This might even save your life someday…

The Rules

You and your adversary stand 10 paces apart.
You take it in turns to act. On your turn, you can either shoot, or walk one pace forwards. We’ll assume here that neither of you ever run out of bullets.
At 10 paces, the chance that you hit your opponent is 1/10. At 9 paces, this improves to 2/10, at 8 paces 3/10, and so on, until at 1 pace away, you are certain to hit your opponent.
It should go without saying, but if you get shot, you lose.

The Strategy

So, should you use your turn to try and shoot your opponent, or take a step forward in order to improve your chances next time round?

If you’re only 1 pace away, and it’s your turn, then you’re certain to win if you shoot, so obviously, that’s what you should do. If you’re two paces away, however, then stepping forward means that your opponent is certain to win, so clearly you should shoot. What about 3 paces away, or further?

Let’s start by working out how likely you are to win if it’s your turn, and you decide to shoot every turn, no matter what your opponent does.

Two Paces

At two paces, we’ll assume that your opponent is intelligent, and never takes a step forward (so that you don’t shoot them with certainty). This means that the best strategy for either player is to shoot on their turn. But what is the chance that you actually win the gunfight? We can think about the shots fired as a sequence of hits and misses. Since the first player to hit wins the gunfight, this sequence will always be a long string of misses, followed by a hit.

If you take the first turn, then you win with the following sequences:

You hit
You miss, they miss, you hit
You miss, they miss, you miss, they miss, you hit

…and so on. There are infinitely many winning sequences like this and it’s easy to tell what they are, so we won’t write out the whole infinite list here. At two paces, the probability that you hit is 9/10, and the probability that either player misses is 1/10. Therefore, the probability that you miss, then they miss, is 1/10 x 1/10 = 1/100.

Then the probability of the first sequence is 9/10, the second is 9/10 x 1/100, the third is 9/10 x 1/100 x 1/100, and so on. These numbers form a geometric series so we can add them up using a simple to formula, to discover that our chance of winning the gunfight is equal to 10/11, or slightly over 90.9%.

More Than Two Paces

At three paces, assuming that nobody takes a pace forward, the chance of winning involves adding a geometric series like before, but with slightly different numbers. The probability of a hit is now 8/10, and the probability of a miss is 2/10. So the probability that you miss, and then they miss, is 2/10 x 2/10 = 4/100 = 1/25. We then find that in this case, your chance of winning the gunfight has dropped to just over 83%.

The same method gives your chance of winning for any number of paces. The results are shown in the table below (to one decimal place).

# Paces	First Player Win %	Second Player Win %
1	100.0	0.0
2	90.9	9.1
3	83.3	16.7
4	76.9	23.1
5	71.4	28.6
6	66.7	33.3
7	62.5	37.5
8	58.8	41.2
9	55.6	44.4
10	52.6	47.4

One important thing to note is that while the gunfight is in progress, any shots fired in the past don’t matter. Assuming that you’re still alive, and both players just keep shooting, the second column gives your chances of winning on your turn, and the third column gives your chances of winning on your opponent’s turn.

Now, we can see that taking a step forward is always a bad idea. This is because taking a step forward resets the situation at a slightly closer distance. Further, whoever takes a step forward gives the other player the opportunity to shoot first. For example, if you are 10 paces away, assuming that both players just shoot, your chance of winning is 52.6%. If the other player decides to take a step forward, they only increase your chance of winning to 55.6%. If you take a step forward, this gives your opponent a 55.6% chance of winning, which means that you have dropped to a 44.4% chance.

If it’s your turn and you just keep shooting, your chance of winning is at least the value in the second column (it increases if your opponent steps forward). If your opponent takes a pace forward, move one cell up. Your chance of winning if you just keep shooting is now at least the value in this cell. If you take a pace forward, move one cell up and one cell to the right in the table. Your chance of winning is now at most the value in this cell, assuming that both of you just keep shooting from now on.

So in this case, you should shoot first and ask questions later.

maycontainmaths

A blog about Maths and Computer Science

Birthday Paradoxes

How to Win a Gunfight