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.

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

### 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,

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.

Not real exciting.

However now, the probability that java returns is,

99.9999999999999999999999999999999999999999999999999999999999999999

9999999999999984758544941347662879361210493872958690819636990122068

9544986844445385366856828346677128124471484063

CRAZY.