Three Share a Birthday

Date: 09/17/1999 at 16:06:46
From: Kay McGraw
Subject: Probability

In my classroom one year I discovered a very rare situation as we were 
graphing our birthdays (month/day). In a class of 24, I had 3 students 
sitting one behind the other with exactly the same birthday. As I do 
this activity every year, I would like to be able to tell them the 
probability of that occurrence and let them know how truly unusual 
this is. No one, including retired and current teachers, seems to know 
how to combine the fact that 3 out of 24 students have the same 
birthday with the fact that they are one behind the other in a room of 
24. Many of us would appreciate it if you could send me the formula, 
and while I won't explain it in detail to my class of 9-year-olds, I 
will give them the chances of that happening again. 

I can't begin to tell you the combinations different staff members 
have suggested. One that might make sense is 365*365*24*23*22, but it 
seems too large an answer. I realize that the probability of having a 
birthday on any given date in a year is not a constant, but I'm 
willing to ignore that. (The date is Jan. 21, if you're curious.)

Thank you very much for any assistance that you might give me.

Kay McGraw

Date: 09/17/1999 at 17:37:18
From: Doctor Anthony
Subject: Re: Probability

With 23 people in a class there is a 50% probability of at least two 
sharing a birthday. The probability of at least three in a class of 24 
sharing a birthday is calculated as follows.

First find the probability that no two share a birthday and then that 
exactly two share a birthday. Add these probabilities and subtract 
from 1 and we have the probability of three or more sharing a 
birthday.

If no two share a birthday, then the first person can choose a 
birthday in 365 ways, the second person in 364 ways, the third in 363 
ways, and so on. If there are n people in the room, the probability 
that no two share a birthday is:

     365 * 364 * 363 * ... * (365-n+1)     P(365,n)
     ---------------------------------  =  --------
                   365^n                    365^n

Setting n = 24, we get:

                                  P(365,24)
     P(none sharing a birthday) = ---------
                                   365^24

                                = 0.4616557

Next we find the probability of exactly 2 sharing a birthday.

We can choose 2 from 24 in C(24,2) = 276 ways.

These two can choose their birthday in 365 ways and then all the other 
22 must have different birthdays.

               276 * 365 * 364 * ... to 23 factors
Probability  = -----------------------------------
                             365^24

               276 * P(365,23)
             = ---------------
                   365^24

             = 0.37256428

So the probability of none or two sharing a birthday 

             = 0.4616557 + 0.37256428

             =  0.83422

So the probability of 3 or more sharing a birthday

             = 1 - 0.83422

             = 0.16578

approx. probability = 1/6

As you can see this is not such an unusual occurrence for a class of 
24.

Unfortunately, there is not enough information to complete the 
question about the probability of three students with the same 
birthday sitting one behind the other in a room of 24. We would need 
to know how the desks are arranged: 6 x 4, 8 x 3, or (highly 
improbable) 1 x 24 seating arrangements would have different 
solutions.

- Doctors Anthony and TWE, The Math Forum
  http://mathforum.org/dr.math/   

Date: 01/15/2001 at 11:30:25
From: John McGregor
Subject: The Birthday Problem - a mistake?

Dr. Anthony:

In your reply to a question about "Three share a birthday" given on 
July 19/99, there seems to me to be an error.

Essentially you say that the probability that 3 or more share a 
birthday equals the probability that 2 or more share a birthday minus 
the probability that exactly 2 share a birthday:

     P(>=3 share) = p(>=2 share) - p(exactly 2 share)

This is fine as far as it goes, but what you then actually calculate 
for the third term is:

     p(exactly ONE SET of 2 share)

so that your resultant p(>=3 share) is an overestimate since it also 
includes the probability that MORE THAN ONE SET of 2 share.

regards
John

Date: 01/18/2001 at 13:17:57
From: Doctor Rick
Subject: Re: The Birthday Problem - a mistake?

Hi, John. Dr. Anthony may not have seen your comments, but I've been 
working on this problem since you sent it in.

You're quite right! The partition into:

     1. none share a birthday
     2. exactly two share a birthday
     3. three or more share a birthday

is not correct. A correct partition is:

       1.   none share a birthday
       2.   one pair shares a birthday
       3.   two pairs share different birthdays
       4.   three pairs share different birthdays
       :
     1+N/2. N/2 pairs share different birthdays
     2+N/2. three or more share a birthday

The probability that no two people out of N share a birthday is, as 
Dr. Anthony had it, is:

     P_N(0) = P(365,N)/365^N

where P(N,M) is the number of permutations of N things taken M at a 
time.

The probability that exactly one pair share a birthday, and all the 
others are different, is (as Dr. Anthony showed):

     P_N(1) = 365*C(N,2)*P(365-1,N-2)/365^N

The probability that exactly two pairs share a birthday is:

     P_N(2) = C(365,2)*C(N,2)*C(N-2,2)*P(365-2,N-4)/365^N

That's because you

   -- choose 2 birthdays, one for each pair: C(365,2)
   -- choose two people for the first pair:  C(N,2)
   -- choose two people for the second pair: C(N-2,2)
   -- choose all different birthdays for the remaining N-4 people: 
       P(365-2,N-4)

You can calculate the probability for exactly K pairs in the same way:

  P_N(K) = C(365,K)*C(N,2)*C(N-2,2)*...*C(N-2K+2,2)*P(365-K,N-2K)/365^N

This can be simplified by noting that the successive C(...,2) terms 
have factorials that cancel in one denominator and the following 
numerator. The simplified formula is:

     P_N(K) = C(365,K)*P(N,2K)*P(365-K,N-2K)/(2^K*365^N)

The probability that at least three people out of N will share a 
birthday is 1 minus the sum of P_N(0) and P_N(K) for K=1 through N/2. I 
haven't gotten this into closed form, but using a spreadsheet, I found 
the following:

        Number of pairs with same birthday           At least Exactly
People     0        1        2        3      Total     trio   1 trio
=====================================================================
   2    0.99726  0.00273                    1        0        0
   4    0.98364  0.01630  2.2E-05           0.99997  2.9E-05  2.9E-05
   6    0.95953  0.03998  0.00033  3.0E-07  0.99985  0.00014  0.00014
   8    0.92566  0.07239  0.00151  8.4E-06  0.99958  0.00041  0.00040
  10    0.88305  0.11162  0.00437  6.1E-05  0.99911  0.00088  0.00083
  12    0.83297  0.15530  0.00984  0.00025  0.99837  0.00162  0.00140
  14    0.77689  0.20084  0.01877  0.00079  0.99733  0.00266  0.00227
  16    0.71639  0.24562  0.03183  0.00198  0.99591  0.00408  0.00326
  18    0.65308  0.28713  0.04936  0.00427  0.99407  0.00592  0.00438
  20    0.58856  0.32319  0.07125  0.00818  0.99175  0.00824  0.00558
  22    0.52430  0.35207  0.09694  0.01429  0.98892  0.01107  0.00680
  24    0.46165  0.37256  0.12545  0.02309  0.98551  0.01448  0.00796
  26    0.40175  0.38403  0.15541  0.03499  0.98150  0.01849  0.00900
  28    0.34553  0.38643  0.18523  0.05012  0.97683  0.02316  0.00987
  30    0.29368  0.38021  0.21323  0.06834  0.97146  0.02853  0.01053

The column labeled "At least trio" is the probability that at least 3 
people share the same birthday; it is calculated as 1 minus the sum of 
columns 0 through N/2. I omitted columns 4 through 15 so the table 
could fit on one line.

The last column, "Exactly 1 trio", is the probability that exactly 3 
people share the same birthday, and all others have different 
birthdays. This is a sanity check: if it were greater than the "At 
least trio" column, there would be something wrong. It is calculated 
as:

     P_N(1 trio) = 365*C(N,3)*P(364,N-3)/365^N

The conclusion is that the probability of at least 3 people out of 24 
sharing the same birthday is much less than the roughly 1 in 6 that we 
previously estimated. It is more like 1 in 70. The probability of 
finding two pairs is much higher, about 1 in 8, accounting for most of 
the 1/6. It is more likely even to find THREE pairs than to find one 
trio!

- Doctor Rick, The Math Forum
  http://mathforum.org/dr.math/