5

How would one go about solving a variant of the birthday problem given below

"What is the probability of at least two people having the same birthday in a group of 23"

I know the answer is just above 0.5 but I am interested in how it is solved when one computes it by taking probabilities of two people having the same birthday, then of three people having the same birthday and so on rather solving it by finding the probability of people not having the same birthday.

Obi Ike-Nwosu
  • 51
  • Hint: Consider the complement, which is that none of the 23 people share the same birthday. How many ways (positive outcomes) are there for that to happen? How many total outcomes can there be? – Calvin Lin Apr 28 '13 at 21:50
  • I know about the complement method. What has got me stumped is how to go about it directly – Obi Ike-Nwosu Apr 28 '13 at 21:51
  • 2
    The direct method will use the Principle of Inclusion and Exclusion, but is pretty ugly / unenlightening. – Calvin Lin Apr 28 '13 at 21:53

1 Answers1

5

Solving it directly means enumerating and counting all the possibilities. That's the reason the complement is easier -- it's easy to describe and compute.

Starting with three people, Alice, Bob, and Charlie, we have the following groupings of "same birthday":

  • $(A=B)$ with $P=\frac{1}{365}$, and $C \ne A$ with $P=\frac{364}{365}$ resulting in $\frac{1}{365}\frac{364}{365}$
  • $(B=C)$ similarly with $B \ne A$ for $\frac{1}{365}\frac{364}{365}$
  • $(A=B=C)$ with probability $\left( \frac{1}{365} \right)^2$

Probability of any of those is the sum of all probabilities, or $$\frac{1}{365}\frac{364}{365} + \frac{1}{365}\frac{364}{365} + \left( \frac{1}{365} \right)^2 = \frac{729}{365^2}$$

Add Donna to the mix and we have (for simplicity, say the common birthday is $x$):

  • $P(A=B; C \ne x; D \ne x,C) = \frac{1}{365} \cdot \frac{364}{365} \cdot \frac{363}{365}$
  • $P(A=C; B \ne x; D \ne x,B) = \frac{1}{365} \cdot \frac{364}{365} \cdot \frac{363}{365}$
  • $P(A=D; B \ne x; C \ne x,B) = \frac{1}{365} \cdot \frac{364}{365} \cdot \frac{363}{365}$
  • $P(B=C; A \ne x; D \ne x,A) = \frac{1}{365} \cdot \frac{364}{365} \cdot \frac{363}{365}$
  • $P(B=D; A \ne x; C \ne x,A) = \frac{1}{365} \cdot \frac{364}{365} \cdot \frac{363}{365}$
  • $P(C=D; A \ne x; B \ne x,A) = \frac{1}{365} \cdot \frac{364}{365} \cdot \frac{363}{365}$
  • $P(A=B=x; C=D=y, x \ne y) = \frac{1}{365} \cdot \frac{364}{365} \frac{1}{365}$
  • $P(A=C=x; B=D=y, x \ne y) = \frac{1}{365} \cdot \frac{364}{365} \frac{1}{365}$
  • $P(A=D=x; B=C=y, x \ne y) = \frac{1}{365} \cdot \frac{364}{365} \frac{1}{365}$
  • $P(A=B=C; D \ne x) = \left( \frac{1}{365} \right) ^2 \cdot \frac{364}{365}$
  • $P(A=B=D; C \ne x) = \left( \frac{1}{365} \right) ^2 \cdot \frac{364}{365}$
  • $P(A=C=D; B \ne x) = \left( \frac{1}{365} \right) ^2 \cdot \frac{364}{365}$
  • $P(B=C=D; A \ne x) = \left( \frac{1}{365} \right) ^2 \cdot \frac{364}{365}$
  • $P(A=B=C=D) = \left( \frac{1}{365} \right) ^3$

Probability of any of those is the sum of all: $$ \frac{({_4C_2}+{_{364}P_2}) + ({_4C_3}+{_{364}P_1}) + ({_4C_4}+{_{364}P_0}) + 3 \cdot 364 }{365^3} $$

The number of possibilities grows combinatorically.

Mark Ping
  • 401
  • 3
  • 8
  • Don't forget $P(A=B\ne C=D),$ $P(A=C\ne B=D),$ and $P(A=D\ne B=C).$ – Will Orrick Apr 28 '13 at 23:00
  • Excellent point, which is why this gets so nasty so quickly. – Mark Ping Apr 28 '13 at 23:04
  • I also believe that in the case of 3 people, A, B and C, you missed out the case (A = C) and (A != B). The actual probability is 0.008204166. The sum you compute is 0.0054794 which underestimates the true value. – rhody Sep 24 '17 at 17:47