I received the following email (extract) from a colleague:

With the birthday question the chances of 23 people having unique birthdays is less than ½ so probability of shared birthdays is greater than 1-in-2. 

Coincidentally on the day you sent out the paper, the following question/math fact was in my son’s 5th Class homework.

We are still debating the answer, hopefully you could clarify…

In a group of 368 people, how many should share the same birthday. There are 16×23 in 368 so there are 16 ways that 2 people should share same birthday (?) but my son pointed out, what about 3 people or 4 people etc.

I don’t think this is an easy problem at all.

First off we assume nobody is born on a leap day and the distribution of birthdays is uniform among the 365 possible birthdays. We also assume the birthdays are independent (so no twins and such).

They were probably going for 16 or 32 but that is wrong both for the reasons given by your son but also for the fact that people in different sets of 23 can also share birthdays.

The brute force way of calculating it is to call by X the random variable that is the number of people who share a birthday and then the question is more or less looking for the expected value of X, which is given by:

\displaystyle \mathbb{E}[X]=\sum_{i=2}^{368}i\cdot \mathbb{P}[X=i].

Already we have that \mathbb{P}[X=2]=\mathbb{P}[X=3]=0 (why), and \mathbb{P}[X=4] is (why) the probability that four people share one birthday and 364 have different birthdays. This probability isn’t too difficult to calculate (its about 10^{-165}) but then things get a lot harder.

For X=5, there are two possibilities:

  • 5 share a birthday, 363 different birthdays, OR
  • 2 share a birthday, 3 share a different birthday, and the remaining 363 have different birthdays

Then X=6 is already getting very complex:

  • 6 share a birthday, 362 different birthdays, OR
  • 3, 3, 362
  • 4, 2, 362
  • 2, 2, 2, 362

This problem is spiraling out of control.

 

There is another approach that takes advantage of the fact that expectation is linear, and the probability of an event E not happening is

\displaystyle\mathbb{P}[\text{not-}E]=1-\mathbb{P}[E].

Label the 368 people by i=1,\dots,368 and define a random variable S_i by

\displaystyle S_i=\left\{\begin{array}{cc}1&\text{ if person i shares a birthday with someone else} \\ 0 & \text{ if person i does not share a birthday}\end{array}\right.

Then X, the number of people who share a birthday, is given by:

\displaystyle X=S_1+S_2+\cdots+S_{368},

and we can calculate, using the linearity of expectation.

\mathbb{E}[X]=\mathbb{E}[S_1]+\cdots \mathbb{E}[S_{368}].

The S_i are not independent but the linearity of expectation holds even when the addend random variables are not independent… and each of the S_i has the same expectation. Let p be the probability that person i does not share a birthday with anyone else; then

\displaystyle\mathbb{E}[S_i]=0\times\mathbb{P}[S_i=0]+1\times \mathbb{P}[S_i=1],

but \displaystyle\mathbb{P}[S_i=0]=\mathbb{P}[\text{ person i does not share a birthday}]=p, and

\displaystyle \mathbb{P}[S_i=1]=\mathbb{P}[\text{not-}(S_i=0)]=1-\mathbb{P}[S_i=0]=1-p,

and so

\displaystyle\mathbb{E}[S_i]=1-p.

All of the 368 S_i have this same expectation and so

\displaystyle\mathbb{E}[X]=368\cdot (1-p).

Now, what is the probability that nobody shares person i‘s birthday?

We need persons 1\rightarrow i-1 and i+1\rightarrow 368 — 367 persons — to have different birthdays to person i, and for each there is 364/365 ways of this happening, and we do have independence here (person 1 not sharing person i‘s birthday doesn’t change the probability of person 2 not sharing person i‘s birthday), and so \mathbb{P}[\text{(person k not sharing) AND (person k not sharing)}] is the product of the probabilities.

So we have that

\displaystyle p=\left(\frac{364}{365}\right)^{367},

and so the answer to the question is:

\displaystyle\mathbb{E}[X]=368\cdot \left(1-\left(\frac{364}{365}\right)^{367}\right)\approx 233.54\approx 234.

There is possibly another way of answering this using the fact that with 368 people there are

\displaystyle \binom{368}{2}=67528

pairs of people.

 

 

Advertisements