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