Prajwalan’s Weblog

with one comment

We all have encountered coincidences of sort in our lives. For example, it happens that we keep on thinking about a particular person and suddenly we get a phone call or email or even a visit from that person. Similarly, we promise to meet someone at a particular time and venue but out of no where something emergency turns up and have to cancel the previously agreed meeting. A list of such coincidences can get very long. Mathematics also has a term for such coincidences and it is called Probability. There are so many things in Probability Theory that surprises us. And, one such is Birthday paradox.

In Probability Theory, ‘Birthday Paradox’ refers, that in a group containing certain randomly chosen people, there is a finite probability for some two people to have exactly the same birthday. For a group with 23 people, this probability is around 50%. This increases exponentially as the number people in the group increases. With as many as 80 people, the probability gets around 100%. This is of course, based on the idea that people are randomly chosen and each day is equally likely to become a birthday for someone.

For more details you may visit http://en.wikipedia.org/wiki/Birthday_problem.

Birthday paradox holds an important position in computer security also. It can be used to attack the hash functions. For example, let us say f is a hash function such as f(x) = y. With hash functions, it should be impossible to guess ‘x’ given ‘y’. In other words they are one way. Another characteristic is that it should be very difficult to find two inputs that yield same output i.e. it should be hard to find x1 and x2 such that f(x1) = y and f(x2) = y. This property is called collision resistance. But using birthday paradox it becomes relatively easier to find such collisions.

Today 16 May is my birthday. And, in facebook I have around 275 friends. Interesting thing is that I do not have a single friend whose birthday coincides with mine. So either some of them have entered incorrect birth date or hidden their birth date from display or for some reason facebook is not notifying me of this. Otherwise, based on birthday paradox I should have at least one friend with birthday today. Perhaps if I include the ‘near-miss effect’ then we can get some coincidences. For example, number of people with birthday separated by certain days. Such latitude will increase the probability of coincidence. But originally birthday paradox theory does not include this near miss effect.