Birthday Problem

Правка en3, от AshutoshChoudhary, 2024-09-02 11:14:59

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 should have different birthdays so probability that n — i will have different birthdays is

p2 = (364 / 365) * (364 / 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, What is wrong with my code or logic, plss help!!

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

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en10 Английский AshutoshChoudhary 2024-09-02 11:21:19 0 (published)
en9 Английский AshutoshChoudhary 2024-09-02 11:20:54 8
en8 Английский AshutoshChoudhary 2024-09-02 11:20:17 24
en7 Английский AshutoshChoudhary 2024-09-02 11:19:34 90
en6 Английский AshutoshChoudhary 2024-09-02 11:17:45 81
en5 Английский AshutoshChoudhary 2024-09-02 11:16:24 36
en4 Английский AshutoshChoudhary 2024-09-02 11:15:28 36
en3 Английский AshutoshChoudhary 2024-09-02 11:14:59 2 Tiny change: 'irthdays\nsource :' -> 'irthdays\n\nsource :'
en2 Английский AshutoshChoudhary 2024-09-02 11:13:50 0 Tiny change: '\nn : 30\n20.1374\n28.8381\n8.70077\' -> '\nn : 30\n\n20.1374\n\n28.8381\n\n8.70077\'
en1 Английский AshutoshChoudhary 2024-09-02 11:12:41 2541 Initial revision (saved to drafts)