Birthday Paradox:
The problem is to find that how many people must be there in a room for having same birthday.Than what is paradox in it? Paradox is that you may think that the possibility will only come when there are many (lets say 365) people in the room. But you will see that the probability will occur even for few people.
To solve this problem we index the total number of the people in the room as
1,2,3….k where k is equal to the total number of people in room.
And also let us assume that all years has 365 days (ignoring the issue of leap years). Lets say
n=365 days
For
i=1,2,3,…,k
let bi be the day on which the birthday of ith person occurs, assuming
1< bi
r = + 1
Now, for example if we have n=365 and k=28 we get by using equation k(k-1)/2n
=> 28(27)/2(365) =1.0368
Thus with 28 people in the room and 365 days in a year we get one pair of people having birthday on the same day.
Balls And Bins:
The problem we are going to discuss is named as balls and bins.
Let say we have b bins and we randomly throw balls into these bins. And the probability is equally likely to that they can fall in any of the bin. In other words, we randomly throw balls to land up in any of the bins.
As explained that the total number of bins are b. So the probability of a ball to fall in any bin is as follow:
Prob. the ball land in given bins = 1/b
Following are hints that can be used to built a complete solution to the problem:
1. “if we through n balls than the expected amount of balls that fall in the total amount of given bin is n/b ”
2. “The expected number of throws until the given bins ,on average, contains a ball is b”
3. The amount of balls we should have to throw that each bin contains atleast one ball can be analyzed as follow:
Let use the word ‘Hit’ when a balls enter a bin. So in the ith stage is when (i-1) hits have occurred. For each toss in the ith stage, as (i-1) bins contains balls, so the number of empty bins left behind are
b – ( i – 1)
So the probability of getting a hit or in other words the ball landing in a bin will be equal to empty bins left behind divided by total number of bins i.e. probability of hit at ith stage will be:
p={b – ( i – 1)} / b}
Let us consider ni be the number of throws at ith stage. So, total amount of throws required to attain hits equals to the number of bins b will be denoted as:
n = ni
now by applying expectation on both sides of above equation, we get
E ( n ) = E ( ni )
Solving the above equation
E ( n ) = ni )
= ni ) (expectation of geometric dist. is given by E(x)=1/p)
=
= b
Now by using mathematics to solve above summation we get
= b ( ln b + O(1) )
So, above equation shows that we have to do blnb throws before we can expect that each bin has a ball.