**Question** : Given n number of people we have to find the expected value of total number of distinct birthdays↵
↵
**source** : https://www.youtube.com/watch?v=U_h3IjreRek&t=120s (time stamp : 34 : 38)↵
↵
**Actual Answer :** ↵
↵
expected value = 365 * (1-(364 / 365) ^ n) ↵
↵
**My Logic :** ↵
↵
i : total number of same same birthdays↵
probability that there are i same birthday's -> ↵
p1 = (1 / 365) ^ (i-1) * (ways of choosing i people out of n => nCi)↵
↵
now remaining n-i; i should have different birthdays so probability that n-i i will have different birthdays is↵
↵
p2 = (364 / 365) * (363 / 365) .. (364-(n-i-1)) / 365↵
↵
expected value is ↵
↵
f(x) * x, where (f(x) is the value, and x is prob of that event)↵
↵
expected value is sum of (n-i+1) * p1 * p2, for i from 2 to n↵
+ the additional case where all birthdays are distinct↵
↵
My logic gives accurate answers for small values of n, but gives very different results as n is increasing, Can anyone tell↵
what's the issue with my logic or code, I am unable to figure out on my own↵
↵
**Code :** ↵
↵
long double ncr(int n, int r) {↵
if (r > n) return 0;↵
if (r == 0 || r == n) return 1;↵
↵
long double res = 1;↵
for (int i = 1; i <= r; i++) {↵
res = res * (n - r + i) / i;↵
}↵
return res;↵
}↵
↵
int main(){↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
↵
int t;↵
cin >> t;↵
while (t --){↵
int n;↵
cin >> n;↵
long double my_answer = 1;↵
for (int i = 1; i <= n; ++ i){↵
my_answer *= (long double)(365 - i + 1) / 365;↵
}↵
my_answer *= n;↵
for (int i = 2; i <= n; ++ i){↵
long double val = (n - i + 1) * ncr(n, i) * pow((long double)1 / 365, i - 1);↵
int cnt = 0;↵
for (int j = i + 1; j <= n; ++ j){↵
val *= (long double)(365 - ++ cnt) / 365;↵
}↵
my_answer += val;↵
}↵
long double actual_answer = 365 * (1 - pow((long double)364 / 365, n));↵
cout << my_answer << "\n" << actual_answer << "\n";↵
cout << abs(my_answer - actual_answer) << "\n\n";↵
}↵
}↵
↵
↵
**Results for N = 1 -> 30**↵
↵
**my answer**↵
↵
**actual answer**↵
↵
**difference in answer**↵
↵
**n : 1**↵
↵
1↵
↵
1↵
↵
7.80626e-18↵
↵
**n : 2**↵
↵
1.99726↵
↵
1.99726↵
↵
8.78204e-18↵
↵
**n : 3**↵
↵
2.99179↵
↵
2.99179↵
↵
8.89046e-18↵
↵
**n : 4**↵
↵
3.98355↵
↵
3.98359↵
↵
4.49132e-05↵
↵
.↵
.↵
.↵
↵
**n : 28**↵
↵
20.3702↵
↵
26.9886↵
↵
6.61839↵
↵
**n : 29**↵
↵
20.2953↵
↵
27.9146↵
↵
7.61934↵
↵
**n : 30**↵
↵
20.1374↵
↵
28.8381↵
↵
8.70077↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
**source** : https://www.youtube.com/watch?v=U_h3IjreRek&t=120s (time stamp : 34 : 38)↵
↵
**Actual Answer :** ↵
↵
expected value = 365 * (1-(364 / 365) ^ n) ↵
↵
**My Logic :** ↵
↵
i : total number of same same birthdays↵
probability that there are i same birthday's -> ↵
p1 = (1 / 365) ^ (i-1) * (ways of choosing i people out of n => nCi)↵
↵
now remaining n-i; i should have different birthdays so probability that n-i i will have different birthdays is↵
↵
p2 = (364 / 365) * (363 / 365) .. (364-(n-i-1)) / 365↵
↵
expected value is ↵
↵
f(x) * x, where (f(x) is the value, and x is prob of that event)↵
↵
expected value is sum of (n-i+1) * p1 * p2, for i from 2 to n↵
+ the additional case where all birthdays are distinct↵
↵
My logic gives accurate answers for small values of n, but gives very different results as n is increasing, Can anyone tell↵
what's the issue with my logic or code, I am unable to figure out on my own↵
↵
**Code :** ↵
↵
long double ncr(int n, int r) {↵
if (r > n) return 0;↵
if (r == 0 || r == n) return 1;↵
↵
long double res = 1;↵
for (int i = 1; i <= r; i++) {↵
res = res * (n - r + i) / i;↵
}↵
return res;↵
}↵
↵
int main(){↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
↵
int t;↵
cin >> t;↵
while (t --){↵
int n;↵
cin >> n;↵
long double my_answer = 1;↵
for (int i = 1; i <= n; ++ i){↵
my_answer *= (long double)(365 - i + 1) / 365;↵
}↵
my_answer *= n;↵
for (int i = 2; i <= n; ++ i){↵
long double val = (n - i + 1) * ncr(n, i) * pow((long double)1 / 365, i - 1);↵
int cnt = 0;↵
for (int j = i + 1; j <= n; ++ j){↵
val *= (long double)(365 - ++ cnt) / 365;↵
}↵
my_answer += val;↵
}↵
long double actual_answer = 365 * (1 - pow((long double)364 / 365, n));↵
cout << my_answer << "\n" << actual_answer << "\n";↵
cout << abs(my_answer - actual_answer) << "\n\n";↵
}↵
}↵
↵
↵
**Results for N = 1 -> 30**↵
↵
**my answer**↵
↵
**actual answer**↵
↵
**difference in answer**↵
↵
**n : 1**↵
↵
1↵
↵
1↵
↵
7.80626e-18↵
↵
**n : 2**↵
↵
1.99726↵
↵
1.99726↵
↵
8.78204e-18↵
↵
**n : 3**↵
↵
2.99179↵
↵
2.99179↵
↵
8.89046e-18↵
↵
**n : 4**↵
↵
3.98355↵
↵
3.98359↵
↵
4.49132e-05↵
↵
.↵
.↵
.↵
↵
**n : 28**↵
↵
20.3702↵
↵
26.9886↵
↵
6.61839↵
↵
**n : 29**↵
↵
20.2953↵
↵
27.9146↵
↵
7.61934↵
↵
**n : 30**↵
↵
20.1374↵
↵
28.8381↵
↵
8.70077↵
↵
↵
↵
↵
↵
↵
↵
↵
