0
$\begingroup$

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?
$\endgroup$
  • $\begingroup$ Can you treat it like the birthday problem except that now you have 2 days to choose (it exclude) from $\endgroup$ – Shailesh Feb 28 '16 at 5:03
  • 1
    $\begingroup$ @Shailesh: No. Even if his question was changed to "at most one day apart". $\endgroup$ – user21820 Feb 28 '16 at 5:04
  • 1
    $\begingroup$ 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)$. $\endgroup$ – A.S. Feb 28 '16 at 5:20
  • $\begingroup$ @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)}$? $\endgroup$ – user21820 Feb 28 '16 at 5:24
  • $\begingroup$ @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. $\endgroup$ – A.S. Feb 28 '16 at 5:46
0
$\begingroup$

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. =)

$\endgroup$
  • $\begingroup$ Note that the solution to the problem in the first paragraph depends on whether you consider dec 31 to be one day apart from jan 1. In this case, the hint is to split into two cases; either jan 1 is a birthday or it is not. $\endgroup$ – user21820 Feb 28 '16 at 5:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.