Probability that among $n$ random people, at least two have coinciding or successive birthdays

Question

I found the following riddle:

What is the probability that among $n$ people chosen randomly, at least two of them have their birthdays with at most one day difference.

Note: December 31 and January 1 are considered as having one day difference. For simplicity, we will consider that a year always contains 365 days.

I've found that the probability is

$$P\left( n\right) = 1-\prod\limits_{i=n+1}^{2n-1} \left( 1-\frac{i}{365}\right) $$

Numerically, it gives the following (for example): $P\left( 14\right) \approx 53.75$, $P\left( 24\right) \approx 90.86$, and $P\left( 33\right) \approx 99.07$.

I'm not sure about my reasoning, since it is not rigorous and the results are quite surprising. So I wonder if anyone can check if these results are true and give a simple and comprehensive solution. Thank you!

Answer 1

Your answer is correct.

Let us find the complementary probability, that every pair of people's birthdays are at least two days apart. An equivalent problem is to find the probability that, when you select $n$ vertices independently and uniformly randomly from a polygon with $365$ vertices, that no two selected vertices are equal or adjacent.

A selection is described by a list $(b_1,\dots,b_n)$, where each $b_i\in \{1,2,\dots,365\}$. Since each selection is equally likely, in order find the probability, we just need to count the number of valid selections, then divide by the total number of selections. Using this question, the number of ways to select $n$ distinct unordered points from a circle of $m$ points, such that no two are adjacent, is $$ \frac{m}n\binom{m-n-1}{n-1}. $$ Since we need to count ordered selections, we multiply this by $n!$. Finally, we divide by the total number of ways to assign birthdays to $n$ people, which is $365^n$. Therefore, $$ \begin{align} P(\text{no same or adjacent birthdays for $n$ people}) &=(365)^{-n}\cdot \frac{365}{n}\binom{365-n-1}{n-1}\cdot n! \\&=\frac{(365-n-1)!}{(365-2n)!(365)^{n-1}} \\&=\prod_{i=n+1}^{2n-1}\frac{365-i}{365}. \end{align} $$

Answer 2

Mike Earnest has give an analytical proof of why your formula is correct.

Here is a simulation using R which shows (allowing for simulation noise) that your calculated probabilities seem reasonable:

anyclose <- function(people, days, close){
  birthdays <- sample(days, people, replace=TRUE)
  distances <- diff(c(sort(birthdays), min(birthdays)+days))
  return(any(distances <= close))
  }
  
set.seed(2024)
mean(replicate(10^5, anyclose(people=14, days=365, close=1))) 
# 0.53819 
mean(replicate(10^5, anyclose(people=24, days=365, close=1))) 
# 0.90837
mean(replicate(10^5, anyclose(people=33, days=365, close=1)))
# 0.99073

and just to show that this simulation also confirms the solution of the traditional birthday problem (with close then being the same birthday)

mean(replicate(10^5, anyclose(people=22, days=365, close=0)))
# 0.47757
mean(replicate(10^5, anyclose(people=23, days=365, close=0)))
# 0.50744