The birthday paradox is strange and counter-intuitive. It's a "paradox" because our brain finds it difficult to handle the compounding power of exponents. Real-world applications for this include a cryptographic attack called the "birthday attack".
Birthday Paradox is one of the most interesting but also challenging to understand and explain to others! Moreover, there is a similar problem that seems to be equivalent, but in fact, it is not. Therefore, we will concentrate on this difference and show it using a simple example.
What is the probability that at least two of them have the same birthday in a given set of n randomly chosen people? A more specific version but the same problem is: How many people must be in a group of randomly chosen people, such that there is more than 50% probability that at least two of them have the same birthday.
We will first try to solve the specific version of the problem before deriving the general formula. Suppose the number of people in the group is n and a year has 365 days.
Case 1: For n = 1
There is one person in the group and that person has definitely a birthday on one day in the year. So probability p = 1 = 365/365.
Case 2: For n = 2
The group consists of two people. Person1 has a birthday one day in a year. Then the probability that person2 has a birthday on another day than person1 is 364/365 (there are 364 remaining days). So the probability that both persons have the same birthday p = 1 - 364/365 = 1/365.
Case 3: For n = 3
Here we extend the case n = 2. Again, person 1 has a birthday on one day, and person 2 has a birthday on a different day with p = 364/365. So it follows that person 3 has a birthday on a different day than person 1 and person 2 with a probability of 363/365.
So we can derive a general formula for n persons.
If we put n = 23 in the above formula, the probability is 50.7%. That means in a room with 23 people, the probability that two or more persons have the same birthday is bigger than 50%! In a room with 41 people, it‟s even bigger than 90%!
In general, suppose there are k people and n dates. The simple way to approach this problem is to start by finding the probability of not getting a match. Imagine you are putting the names of people into some boxes one by one. The first name would have no matches. The second name would have a choice of n-1 out of n names to avoid a match, or 1 – 1/n. The third name would have a choice of n-2 out of n names to prevent a match or 1 – 2/n. If we were to continue this trend for k people:
P (Chance of no matche) = (1 − 1/n) (1 − 2/n) … (1 − k-1/n)
= (n - 1)(n - 2)...(n - k - 1)/n^k
= !n/(n^k)(!n-k)
P (Chances of a match) = 1 - P (Chance of no matche)
For n much larger than k, each factor is close to 1. This corresponds to a low chance of matching for each factor. This formula could solve the problem, given k and n.
For most of us, this result seems to be surprisingly low. We would have estimated many more people to exceed the 50% border. Other estimated even 365/2 = 182. The most obvious reason is that the actual problem is misinterpreted.
Many people mix the birthday paradox with the following question, which is NOT the same: What is the probability that in a given set of n randomly chosen people, at least one of them has the same birthday as a specific person (or at least one of them has a birthday on a particular date)?
Another (similar) version is:
How many people must a group of randomly chosen people contain, such that there is more than a 50% probability that at least one of them has a birthday on the same day as person x?
Compare those versions with the correct birthday paradox to understand the slight but far-reaching difference! So let's solve this one. We want to derive the probability for n people that at least two of them have a birthday on the same predefined date.
Case 1: For n = 1
The first person has a birthday on one date. The probability that this person has no birthday on that date is p' = 364/365. On the other way, the probability that he/she has a birthday on that given date is p = 1 – p' = 1 - 364/365 = 1/365.
Case 2: For n = 2
The first person has no birthday on that date with p' = 364/365. The same applies to the second person. This results that both persons have no birthday on a given date with probability p‟ = p' * p' = (364/365)^2. So the desired probability that at least one of them has a birthday on that date is p = 1 – p‟ = 1 - (364/365)^2.
So we can generalize the formula for n: P = 1 − (364/365)^n.
So for what value of n does this probability exceeds 50%? That is for n >= 253! So there must be at least 253 persons in a room so the probability exceeds 50% that at least two of them have a birthday on a predefined date.
We are transforming the birthday paradox into a dice game. Suppose there is n number of people. We assume that each person throws a dice exactly once i.e. they can throw a number between 1 and 6 using a dice once.
Enjoy learning, enjoy mathematics!
You have given n-bulbs connected in a circle with a switch for each bulb. The connection is such that if you change the state of anyone bulb may be on or off, it will toggle the state of its adjacent bulbs. All the bulbs are initially switched off. You have to find the number of steps such that all the bulbs are switched on.
There are 3 doors behind which are two goats and a car. You pick door 1 hoping for the car but don’t open it right away. Monty Hall, the game show host who knows what's behind the doors, opens door 3, which has a goat. Here's the game: do you want to pick door No. 2? Is it to your advantage to switch your choice?
You’ve got someone working for you for seven days and a gold bar to pay him. The gold bar is segmented into seven connected pieces. You must give them a piece of gold at the end of every day. What is the fewest number of cuts to the bar of gold that will allow you to pay him 1/7th each day?