"near-birthday problem" example of Poisson paradigm

Question

I have an example from page 460 of the textbook Introduction to Probability (second edition) by Blitzstein and Hwang:

For example, suppose there are 14 people in a room. How likely is it that there are two people with the same birthday or birthdays one day apart? This is much harder to solve exactly than the birthday problem, so in Example 4.7.6 we used a Poisson approximation. But we may want a guarantee from a bound rather than worrying about whether the Poisson approximation is good enough. Let $X$ be the number of “near birthday” pairs. Using indicator r.v.s, we have $E(X) = \binom{14}2 \dfrac{3}{365}$. So

$$P (X = 0) \le \dfrac{1}{E(X) + 1} < 0.573$$

The true answer for $P(X = 0)$ turns out to be $0.46$ (to two decimal places), which is consistent with the bound.

How did the authors find that the true answer for $P(X = 0)$ is $0.46$? How do we do this? Is it something that must be calculated computationally using something like R? Thank you.

Answer 1

Analytical Solution

It turns out there's an analytical solution for the near-birthday problem.

Let's consider the example with 14 people in 365 days and calculate the probability of having no pair with birthdays on the same day or one say apart.

Let's assume the first person has a birthday on a fixed day, January 1st, which we'll call $b_1$. We'll later generalize that initial date.

Then we can distribute the 13 other birthdays $b_2$ to $b_{14}$ through the other 364 days, leaving 14 intervals of days, $a_1$ to $a_{14}$, which we expect to have at least one day. The sum of the intervals will be $365 - 14 = 351$ days.

So we have:

$$ \left\{ \begin{aligned} \sum_{i=1}^{14} a_i &= 351 \\[2ex] a_i &\ge 1 \\[2ex] \end{aligned} \right. $$

This is a familiar problem, a 14-part composition of 351. We can calculate those using a stars and bars technique using 13 bars in the 350 locations between the 351 stars. The total number of 14-part combinations of 351 is:

$$ {350}\choose{13} $$

If we consider the 13 birthdays in any order, then we have a total number of permutations of:

$$ {{350}\choose{13}} \times 13! = {}_{350}\mathrm{P}_{13} $$

All that's missing is to generalize the first birthday. In order to have it on any date, we can simply multiply the number of permutations by 365, by shifting the whole set of birthdays by a number of days going from 0 to 364:

$$ 365 \times {}_{350}\mathrm{P}_{13} $$

That's the total number of permutations of birthdays for 14 people, respecting order, where no pairs of birthdays are within one day of each other.

The total number of ways for 14 people to have birthdays in 365 days is $365^{14}$.

So the probability that in a room of 14 people, no two of them share a near-birthday is:

$$ \frac{{}_{350}\mathrm{P}_{13}}{365^{13}} = 0.46250721196335653$$

This matches the exact result you were expecting of 0.46 to two decimal places.

 

We can generalize this formula. In an year of $n$ days, in a group of $k$ people, the probability that none of them have near-birthdays is:

$$\frac{{}_{n-k-1}\mathrm{P}_{k-1}}{n^{k-1}}$$

We can further look at clashes of birthdays at least $d$ days apart, by having the $k$ intervals between them have be $\ge k$. We can reduce this back to the compositions problem by adding $(d-1)$ to the $k$ intervals, which is the same as subtracting $k(d-1)$ from the target value. Putting it all together and simplifying, we get that the probability that none of them have birthdays at most $d$ days apart is:

$$\frac{{}_{n-kd-1}\mathrm{P}_{k-1}}{n^{k-1}}$$

(I checked this formula for some examples that are easy to calculate by hand, such as 2 and 3 people at most one day apart, the 0.46 result matches the one from the book too. Checked limits when the probability is expected to drop to zero when it's impossible to fit as many people as days. This formula also gracefully degrades to the actual "birthday problem" when $d$ is zero.)

See also: The "Near-miss" Birthday Problem, by Gregory Quenell

 

 

Authors' Claim and Poisson Approximation

It's unclear to me why the authors used this particular example to explain the merits of using a distribution as an approximation or to set bounds to a specific probability.

By "much harder to solve exactly than the birthday problem", does that mean they didn't know about this solution to this problem? Did they expect it needed a computational solution? Did they use a brute-force approach to calculate the exact 0.42 probability for that specific case?

Or did they mean that even though an analytical solution is possible, it may be hard to reason about it, hard to figure out all the details, think about all the corner cases, double-check all the math, etc. In such cases, finding a rough approximation through a distribution can be quite useful.

 

For an example of a problem that requires a computational approach to calculate an exact probability, see number of names per draw to draw 90% of 200 names in 30 draws, with 90% probability, where an analytical formula is most likely not to be found and iterative calculations are needed to find the exact probability. But, in that particular case, the probability closely follows a binomial distribution, which makes it possible to quickly get approximate results that are quite useful. The approximation is so close that it makes a lot of sense to just use it in most cases.