[RC5] Birthday Paradox

Joe Zbiciak j-zbiciak1 at ti.com
Fri Mar 20 20:36:57 EST 1998

'Lorenzo Gonzalez' said previously:

| My goodness, is this something you learn in stats?  I personally wouldn't
| mind a quick little overview of why 23 equals 50% likelihood of a duplicate
| of 365 possibilites...

That's part of why it's a 'paradox.'  Where most people get hung up is in
confusing the odds that two particular people have the same birthday, vs.
the odds that in a group of people, there are at least two people who share
a birthday.

The concept is simpler to understand when you reduce the set you're
dealing with.  Suppose that instead of 365 days, we limit ourselves to
a range of 100 "days".  The odds of a random pair of people having the
same birthday is 1%, then.  

Now, suppose you jump to three people.  Let's call them 'A', 'B', and
'C'.  The odds that at least two people in this group share a birthday
now jumps to 2.98% -- you can have 'A' and 'B' collide (1%), 'B' and 'C'
collide (1%), or 'A' and 'C' collide (1%).  (The probability isn't 3% because
the cases where 'A', 'B' and 'C' all collide is redundant across all
three, and that accounts for 0.02%.)

If you jump to four people, the probability of collision continues to
climb, this time to 5.89% -- you can pair four people six ways, so you
get 6 * 1% for each pairing, minus the redundant combinations.  For
five people it jumps to 9.65%... and so on.  The key here is that as
you add people to the mix, the number of combinations in which you can
pair them goes up exponentially.  So, the likelihood that at least two
share a birthday also goes up, nearly along the same curve, at least
until the redundancy overtakes the combinatorial explosion in pairing.

Let's do this for 23 people, then, with birthdays on normal dates.
For 23 people, there are 253 possible pairings, each with a 1/365th
chance of colliding.  Even with the large number of redundant pairs
that are possible, you can see that the probability that at least
one pair "collides" is fairly high.

(I can't seem to work through the exact math right now... I guess
that's Friday for you.  ;-)



 +----------- Joseph Zbiciak ----------+
 | - - - -  j-zbiciak1 at ti.com  - - - - |       Ignorance is the
 |- http://www.primenet.com/~im14u2c/ -|       Mother of Devotion.
 | - - -Texas Instruments, Dallas- - - |          -- Robert Burton
 +-----#include "std_disclaimer.h"-----+
To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest

More information about the rc5 mailing list