Coincidence?

In a group of 23 people, at least 2 people have the same birthday with the probability higher than 50%.

This could be reformulated the following way. There is a bag of 365 different items. We pick an item at random. Note which one it was and return it back into the bag. The question: how many items should we pick so that with a probability higher than 1/2 we would have picked the same item twice. The items in the bag are assumed to be thoroughly mixed before every trial. Is it not surprising that all it takes is 23 items?

To prove our assertion let us start with just two people. What is the probability p₂ that two random persons have the same birthday? It's easier to answer a related question. What is the probability q₂ that two random persons have different birthdays? Obviously, p₂ + q₂ = 1. Thus answering one question we automatically get an answer to another.

Thus we have a person with a birthday which falls onto one of the 365 days and ask what is the probability that another person has a different birthday. Since any day out of 365 but the birthday of the first person would make a different birthday, q₂ = 364/365.

Consider now three people. What is the probability q₃ that no two of them have the same birthday? Obviously p₃ + q₃ = 1, where p₃ is the probability that at least two of the group have the same birthday. As before, take one fellow and his birthday. The second has now 364 days to choose from and, if the third was born on any of the remaining 363 days they would form a "no-overlapping-birthday" group. Thus q₃ = 364/365·363/365.

Proceeding in this fashion we'll get q₄ = (364/365)·(363/365)·(362/365), and so on. Since every fraction in these products is less than 1, the sequence q₂, q₃, q₄, ... is decreasing. Therefore, the sequence p₂, p₃, p₄, ... is increasing. Now, perhaps, it would be less surprising to learn that p₂₃ > 1/2. Recollect that

q23 = 364/365 · 363/365 · ... · 343/365