Poisson paradigm in "near-birthday problem" example

Question

I am presented with an example called the "near-birthday problem":

What if we want to find the number of people required in order to have a 50-50 chance that two people would have birthdays within one day of each other (i.e., on the same day or one day apart)? Unlike the original birthday problem, this is difficult to obtain an exact answer for, but the Poisson paradigm still applies. The probability that any two people have birthdays within one day of each other is $\dfrac{3}{365}$ (choose a birthday for the first person, and then the second person needs to be born on that day, the day before, or the day after). Again there are $\binom{m}2$ possible pairs, so the number of within-one-day matches is approximately $\text{Pois}(\lambda)$ where $\lambda = \binom{m}2 \dfrac{3}{365}$. Then a calculation similar to the one above tells us that we need $m = 14$ or more. This was a quick approximation, but it turns out that $m = 14$ is the exact answer!

I understand the nature of the Poisson distribution, but I don't understand why this paradigm is appropriate for this birthday example, and I don't understand why the rate parameter $\lambda$ is $\binom{m}2 \dfrac{3}{365}$. After all, I don't see much resemblance here to a "rate", which is what the Poisson paradigm is focused around.

I am a novice to the Poisson paradigm, so I think that it is my lack of understanding that is causing my trouble. It could also be my lack of understanding of the combinatorics involved in the problem. Would someone please explain this, so that I can understand it? Thank you.

If we have $m$ people and make the usual assumptions about birthdays, then each pair of people has probability $p = \dfrac{1}{365}$ of having the same birthday, and there are $\binom{m}2$ pairs. By the Poisson paradigm the distribution of the number $X$ of birthday matches is approximately $\text{Pois}(\lambda)$, where $\lambda = \binom{m}2 \dfrac{1}{365}$. Then the probability of at least one match is

$$P(X \ge 1) = 1 - P(X = 0) \approx 1 - e^{-\lambda}.$$

For $m = 23$, $\lambda = \dfrac{253}{365}$ and $1 − e^{−\lambda} \approx 0.500002$, which agrees with our finding from Chapter 1 that we need $23$ people to have a 50-50 chance of a matching birthday.

Note that even though $m = 23$ is fairly small, the relevant quantity in this problem is actually $\binom{m}2$, which is the total number of “trials” for a successful birthday match, so the Poisson still performs well.

Answer 1

Imagine taking a random sample of two people from the population. The probability that their birthdays are near each other is $\frac3{365}.$

You probably didn't get a near match on the first try. So keep trying until you get a match. We can expect this to take a lot of tries. In fact the exact expected number of tries (assuming birthdays uniformly and independently distributed over $365$ days of the year, and counting Dec 31 as "near" to Jan 1) is $\frac{365}3 = 121+\frac23.$

Now consider a long procedure in which someone takes many samples of this kind, one after the other, and imagine it as a Poisson process with expected time $\frac{365}3$ to the next event, regardless of when we start watching the procedure. Notice that we are making an approximation already, because the waiting time of a Poisson process is a continuous random variable, whereas the number of samples until the next near match is a discrete variable. But the difference between two waiting times of the discrete process can be less than $1\%$ of the expected waiting time, so that's about the amount of inaccuracy introduced by assuming the waiting time is continuous.

Now suppose that instead of sampling from the entire population, the procedure is that we have $m$ people in a room and we choose two of them. For each sample, we choose two people from the room, different from any pair we have chosen before.

That introduces another "approximation", in that the samples used to be independent (which was significant because the waiting times of a Poisson process should be independent of each other), and now they are not independent. This introduces a systematic bias into the results, but the question is how much. (The answer turns out to be "not a huge amount".)

We continue this process until we have sampled each possible pair of people in the room. So that's $\binom m2$ samples.

Recalling that the expected number of near matches in one sample is $\frac{3}{365},$ and that the expectation of a sum is the sum of the expectations, even if the variables being added are not independent, and the expected number of near matches in the $\binom m2$ samples is $\binom m2 \frac{3}{365}.$

So now we have a procedure that produces some number of near matches, and the expected number of near matches is $\binom m2 \frac{3}{365}.$ If we suppose that this procedure is sufficiently "similar" to a Poisson process so that we can analyze the distribution of its outcomes (the number of near matches) as if that distribution were a Poisson distribution, then the reasonable assumption is that we should pick a distribution that has the same expected value as the known expected value of the actual distribution of the number of near matches. And that distribution is the Poisson distribution $\mathrm{Poisson}(\lambda)$ whose expected value is $\lambda = \binom m2 \frac{3}{365}.$

This method does not calculate the exact probability that there will be a near match among just $14$ people in a room. The probability it calculates will be different from the actual probability. But the point is that it's not too much different. To solve the "near birthday" problem we just need to know that the probability of a near match with $13$ people is less than $\frac12$ (we don't care how much less) and the probability with $14$ people is $\frac12$ or more (we don't care how much more). The difference between those two actual probabilities is large enough that we can make a noticeable error in calculating each of them without changing the fact that one is less than $\frac12$ and the other is greater than $\frac12.$ And that is what actually does happen in this particular application. The answer $m=14$ that we got via the approximation is the "exact" correct answer because we would have had to make a larger error than we actually do in the estimated probabilities for $13$ or $14$ people in order to conclude that $13$ was enough or that $14$ was too few. The results of the exact algorithm (to three digits) are $0.483$ probability of a near match among $13$ people and a $0.537$ probability of a near match among $14$ people (using the formula from Wikipedia), so (for example) as long as we don't overestimate the probabilities by more than $0.016$ then we won't mistakenly think that $13$ is enough.