Birthday Paradox - Dieptranivsr/DroneIVSR GitHub Wiki

How many people must be there in a room to make the probability 100% that at-least two people in the room have same birthday?

Answer: 367 (since there are 366 possible birthdays, including February 29).

The above question was simple. Try the below question yourself.

How many people must be there in a room to make the probability 50% that at-least two people in the room have same birthday?

Answer: 23

The number is surprisingly very low. In fact, we need only 70 people to make the probability 99.9 %.

Let us discuss the generalized formula.

What is the probability that two persons among n have same birthday?

Let the probability that two people in a room with n have same birthday be P(same). P(Same) can be easily evaluated in terms of P(different) where P(different) is the probability that all of them have different birthday.

P(same) = 1 – P(different)

P(different) can be written as 1 x (364/365) x (363/365) x (362/365) x …. x (1 – (n-1)/365)

How did we get the above expression?

Persons from first to last can get birthdays in following order for all birthdays to be distinct:

The first person can have any birthday among 365

The second person should have a birthday which is not same as first person

The third person should have a birthday which is not same as first two persons.

……………

……………

The n'th person should have a birthday which is not same as any of the earlier considered (n-1) persons.

Approximation of above expression

Implementation of approximate formula.

The following is program to approximate number of people for a given probability.

// C++ program to approximate number of people in Birthday Paradox
// problem
#include <cmath>
#include <iostream>
using namespace std;

// Returns approximate number of people for a given probability
int find(double p)
{
    return ceil(sqrt(2*365*log(1/(1-p))));
}

int main()
{
    cout << find(0.70);
}

Output:

    30

Applications:

1. Birthday Paradox is generally discussed with hashing to show importance of collision handling even for a small set of keys.
2. Birthday Attack

Below is an alternate implementation in C language :

#include<stdio.h>
int main(){
    // Assuming non-leap year
    float num = 365;

    float denom = 365;
    float pr;
    int n = 0;
    printf("Probability to find : ");
    scanf("%f", &pr);

    float p = 1;
    while (p > pr){
        p *= (num/denom);
        num--;
        n++;
    }

    printf("\nTotal no. of people out of which");
    printf("there is %0.1f probability that two of them ");
    printf("have same birthdays is %d ", p, n);

    return 0;
}