BirthdayProbability

Mathematics:

The probability that at least two people share their birthday in a room of 23 people approximately 50%

This is a pretty famous combinatorial problem, mainly because it is so counter intuitive.

Classic Combinatorial Method:

If we were to use the classic combinatorial method to solve this problem, we would start by finding the probability that none of the n people share their birthday. The probability is,

Now, the probability that at least two people share their birthday is,

 

After some cancellation, the result is,

Monte Carlo Method: 

First, create several "rooms" with n number of people. Randomly generate their birthday. For simplicity purposes, generating random integer from 1-365 is a good approach. Finally count the number of "rooms" where at least two people shared their birthday. The Monte Carlo Method estimates,

    

The result is (not always),

Java:

import java.util.ArrayList;
import java.util.Date;
import java.util.HashSet;
import java.util.Random;
import org.jscience.mathematics.number.Real;

public class BirthdayProbability {
 public static void main(String[] args) {
  // 365 days
  print(new Probability(10, 1024));
  print(new Probability(10, 2097152));
  print(new Probability(23, 1024));
  print(new Probability(23, 2097152));
  print(new Probability(300, 1024));
  print(new Probability(300, 2097152));
  // leap year
  print(new Probability(10, 1024, 366));
  print(new Probability(10, 2097152, 366));
  print(new Probability(23, 1024, 366));
  print(new Probability(23, 2097152, 366));
  print(new Probability(300, 1024, 366));
  print(new Probability(300, 2097152, 366));
 }

 public static long time() {
  return new Date().getTime();
 }

 public static Real probabilityClassic(int numOfPeople, int numOfDays) {
  Real.setExactPrecision(100);
  Real temp = Real.valueOf(1);
  for (int i = 1; i <= numOfPeople; i++)
  {
   temp = temp.times(numOfDays - numOfPeople + i);
  }
  return Real.valueOf(100).times(Real.valueOf(1).minus(temp.divide(Real.valueOf(numOfDays).pow(numOfPeople))));
 }

 public static double probabilityMonteCarlo(int numOfPeople, int numOfRooms, int numOfDays) {
  int randomnumber = 0, count = 0;
  Random random = new Random();
  ArrayList<Integer> arraylist;
  HashSet<Integer> hashset;
  for (int run = 1; run <= numOfRooms; run++)
  {
   arraylist = new ArrayList<Integer>();
   hashset = new HashSet<Integer>();
   for (int i = 0; i < numOfPeople; i++)
   {
    randomnumber = random.nextInt(numOfDays) + 1;
    // amortized constant time
    arraylist.add(randomnumber);
    // constant time
    hashset.add(randomnumber);
    if (arraylist.size() != hashset.size())
    {
     count++;
     break;
    }
   }
  }
  return ((double) count) / ((double) numOfRooms) * 100;
 }

 public static void print(Probability Probability) {
  long startMCM, startCCM;
  System.out.println(Probability.toString());
  startCCM = time();
  System.out.println("Probability based on Classic Combinatorial Method: " + probabilityClassic(Probability.getnumberOfPeople(), Probability.getnumberOfDays()) + "\nExecution Time: " + (time() - startCCM) / 1e3 + " secs.\n");
  startMCM = time();
  System.out.println("Probability based on Monte Carlo Method: " + probabilityMonteCarlo(Probability.getnumberOfPeople(), Probability.getnumberOfRooms(), Probability.getnumberOfDays()) + "\nExecution Time: " + (time() - startMCM) / 1e3 + " secs.\n");
  System.out.println("**************************\n\n");
 }
}

public class Probability {
 private int numberOfDays;
 private int numberOfPeople;
 private int numberOfRooms;

 public Probability(int numberOfPeople, int numberOfRooms) {
  this.numberOfPeople = numberOfPeople;
  this.numberOfRooms = numberOfRooms;
  this.numberOfDays = 365;
 }
 
 public Probability(int numberOfPeople, int numberOfRooms, int numberOfDays) {
  this.numberOfPeople = numberOfPeople;
  this.numberOfRooms = numberOfRooms;
  this.numberOfDays = numberOfDays;
 }

 public int getnumberOfPeople() {
  return numberOfPeople;
 }

 public int getnumberOfRooms() {
  return numberOfRooms;
 }

 public int getnumberOfDays() {
  return numberOfDays;
 }
 
 public String toString(){
  return "Number of People: "+numberOfPeople+"\nNumber of Days: "+numberOfDays+"\nNumber of Rooms: "+numberOfRooms+"\n";
 }
 
}

Number of People: 10
Number of Days: 365
Number of Rooms: 1024

Probability based on Classic Combinatorial Method: 11.6948177711077651869164770415495838768342667298982714059990945201552009201848139128614995295730927
Execution Time: 0.063 secs.

Probability based on Monte Carlo Method: 11.9140625
Execution Time: 0.025 secs.

**************************


Number of People: 10
Number of Days: 365
Number of Rooms: 2097152

Probability based on Classic Combinatorial Method: 11.6948177711077651869164770415495838768342667298982714059990945201552009201848139128614995295730927
Execution Time: 0.001 secs.

Probability based on Monte Carlo Method: 11.704587936401367
Execution Time: 1.445 secs.

**************************


Number of People: 23
Number of Days: 365
Number of Rooms: 1024

Probability based on Classic Combinatorial Method: 50.72972343239854072254172283370325002359718452929878099019740020018841839181277159923316805370532012
Execution Time: 0.001 secs.

Probability based on Monte Carlo Method: 51.3671875
Execution Time: 0.004 secs.

**************************


Number of People: 23
Number of Days: 365
Number of Rooms: 2097152

Probability based on Classic Combinatorial Method: 50.72972343239854072254172283370325002359718452929878099019740020018841839181277159923316805370532012
Execution Time: 0.001 secs.

Probability based on Monte Carlo Method: 50.70667266845703
Execution Time: 3.014 secs.

**************************


Number of People: 300
Number of Days: 365
Number of Rooms: 1024

Probability based on Classic Combinatorial Method: 99.9999999999999999999999999999999999999999999999999999999999999999999999999999999375466755293758512381129978461284734548583347684249819000883774880640819313421049375212650378828337
Execution Time: 0.02 secs.

Probability based on Monte Carlo Method: 100.0
Execution Time: 0.002 secs.

**************************


Number of People: 300
Number of Days: 365
Number of Rooms: 2097152

Probability based on Classic Combinatorial Method: 99.9999999999999999999999999999999999999999999999999999999999999999999999999999999375466755293758512381129978461284734548583347684249819000883774880640819313421049375212650378828337
Execution Time: 0.008 secs.

Probability based on Monte Carlo Method: 100.0
Execution Time: 4.246 secs.

**************************


Number of People: 10
Number of Days: 366
Number of Rooms: 1024

Probability based on Classic Combinatorial Method: 11.6645411803999900086835739583084814093115540505256706115485640589964528406979927411348744338253793
Execution Time: 0.001 secs.

Probability based on Monte Carlo Method: 12.890625
Execution Time: 0.001 secs.

**************************


Number of People: 10
Number of Days: 366
Number of Rooms: 2097152

Probability based on Classic Combinatorial Method: 11.6645411803999900086835739583084814093115540505256706115485640589964528406979927411348744338253793
Execution Time: 0.0 secs.

Probability based on Monte Carlo Method: 11.67612075805664
Execution Time: 1.296 secs.

**************************


Number of People: 23
Number of Days: 366
Number of Rooms: 1024

Probability based on Classic Combinatorial Method: 50.63230118194599075847570192608255953114267617437643013841590630887057713930353071663127356519578656
Execution Time: 0.001 secs.

Probability based on Monte Carlo Method: 52.34375
Execution Time: 0.001 secs.

**************************


Number of People: 23
Number of Days: 366
Number of Rooms: 2097152

Probability based on Classic Combinatorial Method: 50.63230118194599075847570192608255953114267617437643013841590630887057713930353071663127356519578656
Execution Time: 0.001 secs.

Probability based on Monte Carlo Method: 50.653934478759766
Execution Time: 3.121 secs.

**************************


Number of People: 300
Number of Days: 366
Number of Rooms: 1024

Probability based on Classic Combinatorial Method: 99.999999999999999999999999999999999999999999999999999999999999999999999999999999847585449413476628793612104938729586908196369901220689544986844445385366856828346677128124471484063
Execution Time: 0.008 secs.

Probability based on Monte Carlo Method: 100.0
Execution Time: 0.003 secs.

**************************


Number of People: 300
Number of Days: 366
Number of Rooms: 2097152

Probability based on Classic Combinatorial Method: 99.999999999999999999999999999999999999999999999999999999999999999999999999999999847585449413476628793612104938729586908196369901220689544986844445385366856828346677128124471484063
Execution Time: 0.006 secs.

Probability based on Monte Carlo Method: 100.0
Execution Time: 4.314 secs.

**************************

Couple of observations:

It gets really interesting when n is a large number (less than 366). For example, when n is 300 like in the last part of the result, the probability is very large. It is so large that if we really put 300 random people in a room, we will "always" find at least a couple who share birthdays. Therefore, Monte Carlo is not really useful in these extreme situations. Also, the library jscience is brilliant when it comes to precision. Before coming across this library, I had to settle with a different approach since Java could not handle calculations like . For example, the Birthday probability for n = 300 would be represented by,



Not real exciting.

However now, the probability that java returns is,
99.9999999999999999999999999999999999999999999999999999999999999999
9999999999999984758544941347662879361210493872958690819636990122068
9544986844445385366856828346677128124471484063

CRAZY.