Birthday Problem

Revision en8, by AshutoshChoudhary, 2024-09-02 11:20:17

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en10 English AshutoshChoudhary 2024-09-02 11:21:19 0 (published)
en9 English AshutoshChoudhary 2024-09-02 11:20:54 8
en8 English AshutoshChoudhary 2024-09-02 11:20:17 24
en7 English AshutoshChoudhary 2024-09-02 11:19:34 90
en6 English AshutoshChoudhary 2024-09-02 11:17:45 81
en5 English AshutoshChoudhary 2024-09-02 11:16:24 36
en4 English AshutoshChoudhary 2024-09-02 11:15:28 36
en3 English AshutoshChoudhary 2024-09-02 11:14:59 2 Tiny change: 'irthdays\nsource :' -> 'irthdays\n\nsource :'
en2 English 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 English AshutoshChoudhary 2024-09-02 11:12:41 2541 Initial revision (saved to drafts)