Birthday Paradox and Hash Functions - Gaurav's Blog

Birthday Paradox and Hash Functions - Gaurav's Blog

The Birthday Problem is concerned with computing the probability that, in a set of $n$ randomly chosen people, at least one pair of people will have the same birthday (let's call it a 'collision').

Intuitively, what would be your guess for the probability of collision to become > 0.5? Given that there are 365 possible days, I would imagine $n$ to be quiet large for this to happen. Let's compute it by hand.

What is the probability that there isn't a collision?

• The total number of combinations of birthdays possible for the set of $n$ people is $365^n$.

• However, for the birthdays to not overlap, each one should pick $n$ different birthdays out of the 365 possible ones. This is equal to $_{365}P_{n}$ (pick any $n$ out of the 365 days, and allow permutations).

Read full article from Birthday Paradox and Hash Functions - Gaurav's Blog