Recently I am taking a free course online namely stat 110 from Harvard. The course is fantastic mainly because of its instructor Joe Blitzstein and the way he teaches counter intuitive stuff in intuitive manner. Moreover the problems discussed in the lectures are phenomenal but are intricate so in order to understand them properly and as a note to myself I will write about these problems and the underlying principle they are based on.
Okay, So the First problem The Birthday problem.
Statement: There is a party and you have to find the minimum number of people that should attend the party so there is a 50% chance that at least two people will have their birthday on the same day
Solution: Say n people are attending the party so the probability that no pair of people have their birthday on the same day is given by because the first person can have his birthday on any one of the 365 days. Similarly second person can have his birthday on any day except for the day on which the first person has his birthday. So this give us 364 days and so on for the other people at the party. The multiplication symbol in between the days is obvious from the multiplication rule i.e person A can have his birthday on any of the 365 days and Person B can have his birthday on any of the 364 days, so the number of ways they both can have a birthday is and this can generalised further.
At this point we are nearly done, Probability of no match is P(no match), so the probability of match is 1 - P(no match) i.e,
Now we just have to substitute the various values of n and find the point at which P(match) gets bigger than 0.5.
When we substitute various values of n, it takes a minimum 23 people such that the probability of two people having birthday on the same day is 50%.
INTUITION: The result n=23 seems to be pretty counterintuitive, in the sense that the result says we require a very few people. But the important thing here is pairs of people and not the individual people themselves.
So, with 23 people how many pairs can we form now this seems pretty good because out of 253 pairs any one pair can have their birthday on the same date.