# Birthday Within A Day Probability

So here's the problem:

• You have a room with n people
• What's the probability that at least one pair in the room will have birthdays that are exactly one day apart from each other?
• Can you treat it like the birthday problem except that now you have 2 days to choose (it exclude) from – Shailesh Feb 28 '16 at 5:03
• @Shailesh: No. Even if his question was changed to "at most one day apart". – user21820 Feb 28 '16 at 5:04
• There are $C=\binom n 2$ pairs and each pair is a "hit" with probability $2p$ for $p=365^{-1}$. The (weak) dependence kicks in only when you get at least two adjacent matches hence quite conservatively, for $\lambda=2pC$ not larger than 2-3, the probability of no hits is $\approx\exp(-2p\binom n 2)$. – A.S. Feb 28 '16 at 5:20
• @A.S.: Yes that is a reasonable rough estimate. But why didn't you just say that the probability of no hits is approximately $(1-2p)^{C(n,2)}$? – user21820 Feb 28 '16 at 5:24
• @user Well, I had to qualify when the events are only weakly dependent - otherwise simple product of probabilities won't work. Obviously, for small $p$, $1-2p\approx e^{-2p}$ and the form I've written depends on a natural single parameter of the problem - $\lambda$ - rather than on two separate parameters and allows for easy computer-less estimates. I've been reading on Poissonization/Poisson Clumping Heuristic recently so that played a role as well as I think that might be the formal way to describe what I did. – A.S. Feb 28 '16 at 5:46

As stated, the problem probably needs the inclusion-exclusion principle. However, if you change it to "at most one day apart", then it suffices to find the number of ways to sit $n$ people on $365$ chairs in a line such that no two people are in adjacent chairs, and then divide it by the number of ways to put $n$ people on those chairs without restriction.
If you really want "exactly one day apart", then you can divide into cases, where case $k$ is that the $n$ people have exactly $k$ distinct birthdays (possibly shared). The number of ways to divide $n$ people into $k$ non-empty groups is a Stirling number of the second kind. Each way corresponds to $k!$ ways of sitting $n$ people on exactly $k$ labelled chairs, and we can use the solution to the problem in the above paragraph to find how many ways we can choose those $k$ chairs from the original $365$ chairs.
By the way, in real life the probability you're asking for is either $0$ or $1$, especially since you've already asked all of them for their birthdays, and hence can determine with absolute certainty whether or not two of them have birthdays exactly one day apart. =)