Birthday Problem
Разница между en9 и en10, 0 символ(ов) изменены
**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↵








История

 
 
 
 
Правки
 
 
  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)