The Birthday Paradox

Vsalsa! Kevin here. I have 23 babies. Which means there's a 50% chance that two of them will have the same

birthday

? Hey? Let me explain. Each of these babies has a random

birthday

, meaning that each of them has the same probability of being born on any of the 365 days of the year. So what are the odds that two of them share the same birthday? We'll keep it simple: there are no twins, there are no leap years, there are no patterns that suggest parents fathered their babies at specific, non-random times. The odds are not 23 out of 365, which would be about 6%.

In reality, the chances are 50%. There is a 50% chance that out of 23 random people, 2 will have the exact same birthday. Which seems impossible given that we have so few babies and so many possible birthdays. And if we only have 50 babies, the chances of them matching their birthdays increase to 97%. At 75 years old, it is 99.97%, which makes it practically certain that when we put together 75 babies (or 75 things with birthdays, they don't have to be babies) two of them will share a birthday. The birthday

paradox

is a true

paradox

. It's surprising and sounds absurd, but we have the calculations to prove it's true.

How is it possible that so few babies can have so many chances of sharing the same birthday? And how is it that despite 365 possibilities, we only need one-sixth of that number to be pretty sure there's a match? The easiest way to do this is not to...excuse me, babies. Babies... oh dear. Awww, jeez. Babies… erasing babies! Okay, that's not good. The simplest way to do this is not to calculate the probability that two babies of any number share the same birthday; is to calculate the probability that they will not do so. To do that, we assume that Baby #1 has been born.

So the probability of this baby having a birthday is 1, or 365/365. We then multiply it by baby number 2's probability of not sharing that birthday: 364/365. We multiply that result by Baby 3's probability of not sharing a birthday with either Baby 1 or Baby 2, which is 363/365... and we continue doing this for as many babies as we want to calculate the probabilities for. In Baby #23, we are multiplying by 343/365. To simplify this calculation we can write it as: 364! Factorial: We'll start with 364 because 365 over 365 is just 1, over 342! Because 365 minus our 23 babies gives us 342, multiplied by 365 days of the year raised to the 22nd power, which is our 23 babies minus baby one again. -- and the result of the entire equation gives us .492703, or about 49.3%.

Again, that's the probability that we don't have a 23 baby birthday match, so we subtract it from 1 to find the probability that we do, which is 0.507297, which is about 50.7%. The trick here is that each baby is tested against each other; I actually broke my pen trying to do all these lines of evaluation. It's not about whether Babies #2 through #23 share a birthday only with Baby #1, to have a 50% match with a single predefined birthday, as much as a 50% chance of finding a match with the specific birthday of the Baby #5, we would need a group of 253 babies, which sounds pretty good and isn't particularly surprising.

This is if two babies share a birthday with each other. The high probability, 50%, with a low baby count, 23, is surprising, but the math works. And if we continue to expand the series and the results show that with 100 babies (less than a third of the possible birthdays in a given year) the chances of them matching are 99.99997%, which means that the chances of NOT having a birthdays overlap. would be only 0.00003%, or 3 in 10 million. If we replace our birthday babies with online passwords, we have the basis for a type of hack known as a Birthday Attack. When you create a password for a website, that password is processed into a fixed-length hash value that stores and identifies the combination of characters you enter.

So "12345" becomes "827ccb0eea8a706c4c34a16891f84e7b". Simple. When the MD5 message digest algorithm was a standard for encryption, its 128-bit, 32-hexadecimal hashes were vulnerable to a hack based on my babies. The goal was to find and force a collision, when two hashes have exactly the same value, regardless of what that value is. So if Vsauce2.doc and Kevin.doc had the same hash value, you could change the information in one and affect the other or you could eventually use collisions like this to decode the encryption algorithm and learn how it works. And the best way to do it was not a trial and error or “brute force” attempt to guess a specific match among the 3.4 × 10^38 possible results in a 128-bit hash.

It was putting the birthday paradox into practice. Hackers developed an algorithm based on the mathematics of the birthday paradox to cause hash collisions more quickly and ultimately crack one of the most widely used cryptographic algorithms of its time. Therefore, probability around birthdays helped improve Internet security. And right now online, as long as 70 people watch this video at the same time, there's a 99.9% chance that two of you will blow out birthday candles on the same day of the year. So... when were you born? And as always, thanks for watching.