The Birthday Paradox Modeling Vs. Theory

• Tweet
• 

        //*This short c++ program will model the birthday paradox (http://en.wikipedia.org/wiki/Birthday_paradox) and comare the modeling to the theoretical math*//

#include <iostream>
#include <iomanip>
#include <time.h>
#include <math.h>
using namespace std;

//vars
int GroupOfPeople[50];
//bool v = true;

//funcs
void Fill (int M);
bool CheckDuplicates (int M);
double T_Math(int M);
int MaxSamples = 50000;

int main(){
	//srand ( time(NULL) );
	srand(1);//for debug; static seed	
	double ModelSum = 0;
	double Modelavg = 0;
	cout	<< setw(15) <<"Num in group"
	<<setw(17) << "\% Modeled"
	<<setw(15) << "\%Theoretical"
	<<setw(23)<< "Theoretical - Modeled"<<endl;
	for (int M=1; M<50; M++) {//this loop performs checks for groups of size M
		ModelSum=0;
		for (int ii=0; ii<MaxSamples; ii++) {//this loop perfroms checks on multiple samples
			Fill(M);//ensures a new sample each call
			if (CheckDuplicates(M)){	ModelSum++;}//endif
		}//end for
		Modelavg=ModelSum/MaxSamples;
		//printf("The Theoretical probability of duplicate birthdays in a group of %d is %f\n",M,T_Math(M));
		//printf("The Modeled probability of duplicate birthdays in a group of %d is %f\n",M,Modelavg);
		double TP = T_Math(M);
		cout<<fixed<<setprecision(2);
		cout	<< setw(15) <<(M +1)
				<<setw(15) << (Modelavg*100)<<"\%"
				<<setw(15) << (TP*100) << "\%";
		cout<<fixed<<setprecision(5)
				<<setw(15)<< (TP - Modelavg) << endl;
	}//end for
}//end main

void Fill(int M){
	for (int i=1; i<M+1; i++) {//limited iterations by Max preventing wasted resources
		GroupOfPeople[i] = ((rand()%365)+1);
	}//end for
}//end fill

bool CheckDuplicates (int M){
	//nested loop for self comparison, we don't need more memory(M$, take note!)
	for (int i=0; i< M; i++) {
		for (int ii=(i+1); ii<M; ii++) {
			if (GroupOfPeople[i]==GroupOfPeople[ii]) {
				return true;
			}//end if
		}//end for
	}//end for
	return false;
}//end CheckDuplicates

double T_Math(int M){
	double a = ( 364 / (static_cast<double> ( 365 ) ) );
	double e = ( ( M * ( M - 1 ) ) / (static_cast<double> ( 2 ) ) ); 
	return 1 - pow(a, e);
}//end T_Math

Tags:
• Array
• birthday
• duplicate
• paradox
• Statistics