Most of you must have heard this problem while studying Computer Engineering / Probability courses.
Problem Statement: What is the probability that in a group of n people, two people share their birthdays, ignoring leap years.Alternatively what should be the group size such that probability of two people sharing birthday is 50%.
Recently I face this problem in SRM match at TCO17 India Regional.This was a 1000 point problem. I couldn’t solved it in a stipulated time but this problem itched in my mind. I did knew the way to solve it for two people sharing birthday. But SRM problem was different, its a kind of generalization.
TopCoder SRM Problem statement can be found here. Basically it state minimum how many people we need before the probability that M people share birthday ≥ 0.5
Input would be M people sharing birthday and output should be how many people we need such that probability is ≥ 0.5
For M = 2 we knew N =23 i.e. if we have random group of 23 people, there are 50% chance that 2 people share birthday.
For M =3, it appears that N=88 i.e. if we have 88 people in room, there are 50% chances that 3 people shares a birthday.
After searching over Google and going through probability and mathematics courses, I had some understanding and going to share the same.
Solution for M = 2
Let’s see how we can solve for 2 people sharing birthday.
Probability: Desired outcome divided by total possible outcome.
Independent Event: Two event A and B occur independently of each other, like in this case two people can choose birthday independently.
P(A and B) = P(A) * P(B)
Mutually exclusive event: Either A or B can occur
P(A or B) = P(A) + P(B)
Permutation: Rearrangement of n things taken r at a time, order matters
P(n, r) = n! / n-r!
Combination: Order doesn’t matter, there will be r! , dividing that means
C(n, r) = n! /(r! * n-r!)
Complement Rule from Probability: This states that sum of the probabilities of an event and its complement must equal 1.
Pr(A) + Pr(A`) = 1
Pr(A) = Probability that two people share birthday.
Pr(A`) = Probability that no two people share birthday.
We will try to find Pr(A`) and then subtract from 1 to find Pr(A).
Lets take group of N people and find how 2 people shall not share birthday i.e. Pr(A`)
1st person can chose birthday in 365 ways.
2nd person can chose in 364 ways, remember that we are calculating not sharing birthday, this second person cannot chose the birthday what 1st person already chosen.
Similarly 3rd person Pr= 363 /365
Pr(A`) = Desired Way / Total Way =365 * 364 * 363……. 365 -(n-1) / 365^n
Permutation P(n, r) = n! / n-r! can also be written as n * n-1 * n-2 * n-(r-1)
Pr(A`) = P(n, r)/ 365^n
We need to find Pr(A) ≥ 0.5
Pr(A) = 1-Pr(A`)
Substituting that we get
Pr(A`) ≤ 0.5
This can be calculated using a simple C program, iterate for n until it is less than 0.5
#include <iostream>
using namespace std;
int main(int argc, char*argv[])
{
double p = 1;
double i= 1.0;
do{
p *= ((double)365-i)/365.0;
i++;
}while(p>=0.5);
cout << i <<endl;
}Solution for M=3
Now lets analyze how to calculate when 3 people share birthday in a group of n people.
Again we will calculate Pr(A`) i.e. how many ways 3 people not share birthday in a group of n people.
- All n people have independent birthday.We know from above how to calculate this
Pr_N(0) = P(365, n)/ 365^n - 1 pair share birthday and then rest n-2 have distinct birthdays.This can be calculated as follows
- Number of ways 1 pair (2 people) can be chosen = C(n, 2)
- This pair can take any of 365 days
- For these n-2 people they can pick 365–1 birthdays.
Pr_N(1) = C(n, 2) *365 * P(365–1, n-2) / 365^n - 2 pair share a birthday and rest n-4 have distinct birthdays.
- Number of ways 1st pair can be chosen = C(n, 2)
- Number of ways 2nd pair can be chosen = C(n-2, 2)
- Number of ways birthday can be picked for these 2 pairs = C(365, 2)
- Rest n-4 people can have all different birthday = P(365–2, n-4) since 2 birthday are already picked by above 2 pairs we are left with 363 birthdays and n-4 people
Pr_N(2) = C(n, 2) * C(n-2, 2) * C(365, 2) * P(363, n-4) /365^n
Maximum their would be n/2 pairs of 2 people.
Generalizing above formula for k pairs
This is for all the ‘k’ pairs C(n, 2) * C(n-2,2) * C((n-2(k-1),2) = n! / (2!)^k * (n -2 k)! =P(N,2K) / (2!)^k
Number of ways k birthday can be chosen for these k pairs are C(365, k)
Next the left overs can choose 365-k birthdays in = P(365-k, N-2k) ways
Pr_N(k) = P(N,2K) * P(365-k, N-2k) * C(365, k)/ ((2!)^k * 365^n)
Summing up everything will give us Pr(A`).
Generalization
So far we have seen if M=2 or M=3 , how probability can be calculated.
Next lets see how to calculate for any value of M.
Things gets tricky a bit.Lets see this by an example, suppose M=4, N=10
We will calculate how 4 people out of 10 doesn’t share a birthday.
- All n people have different birthday
- 1 pair (2 people) share birthday and the rest n-2 and there will be N/2 possible groups of size 2.
- 1 triplet(3 people) share birthday and the rest n-3 and there will be N/3 possible groups of size 3.
Point to note is we can go up-to M-1 group size for e.g. M=4 we went from group of size 1 to 3.
Another important point is the rest of people in i group can again form a group of size i to M-1 i.e. if a group of 3 people is formed, rest 7 people can form a group of 1 and 2 and this can be calculated recursively.Lets see all this through some slides.
