Birthday Paradox Simulation The birthday paradox, states that given a group of 2
ID: 3803525 • Letter: B
Question
Birthday Paradox Simulation
The birthday paradox, states that given a group of 23 (or more) randomly chosen people, the probability is more than 50% that at least two of them will have the same birthday.
Your task is to use simulation to corroborate the mathematical analysis.
Algorithm:
1) Include the following libraries: <iostream>,<iomanip>,<cstdlib>,<cmath>,.
2) Input (and echo to the output):
the number of times to run the simulation
a non-negative integer seed value to be used as the input parameter for srand().
3) Repeat the following simulation the number of times specified by the input:
1. Initialize a 365 (no leap day) element Boolean array to all false.
2. Declare and initialize a 365 element integer frequency array.
3. Randomly mark birthdays (true) in the 365 element Boolean array until there's a duplicate.
4. Every time there's not a duplicate birthday, increment the frequency array element whose index is the current number of unmatched birthdays.
5. When there is a duplicate, break out of the loop.
4) When finished, store, in a new (double) array, the ratio of each value in the frequency array to the total number of runs.
This value will be a the simulated probability of not-matching for that many birthdays.
5) In another array of the same size and type, store the theoretical probability of not-matching. ( N = number of birthdays not-matching) computed via the relations:
The probability that 0 or 1 birthday won't match is 1.
The probability that 2 birthdays won't match is (1 - 1/365) = (1 - ({N=2} - 1)/365) = P(2).
The probability that 3 birthdays won't match is (1 - 1/365)*(1 - 2/365) = P(2)*(1 - ({N=3} -1)/365).
The probability that N > 0 birthdays won't match is P(N - 1)*(1 - (N -1)/365).
6) output a table where for each row:
column 1 is the number of birthdays not-matching (starting with 2),
column 2 is the respective theoretical probability
column 3 is the respective simulated probability
column 4 is the respective absolute error {theoretical - simulated}
column 5 is the respective relative error {fabs((theoretical - simulated) / theoretical)}
7) Can you duplicate the instructors output?
(You'll need to use the following I/O manipulators: scientific, setw(), setprecision())
8) Answer the following questions:
1. What happens to the magnitude of the errors when you significantly increase the number of runs?
2. Run the simulations again using different random seeds. What happens?
3. Does your simulation verify that the smallest number of people for which there is a greater than 50% chance of having at least one common birthday is 23?
4. How would you modify your program to simulate the probabilities that M > 2 birthdays would-not match?
Explanation / Answer
#include<iostream>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<cmath>
using namespace std;
int main()
{
srand(time(NULL)); //seed random generator with a unique number
bool birthday[365] = {false};
int r,match;
cout<<"enter the number of trials";
cin>>n;
for(int i=2; i<50 ; i++)
{
match=0;
for(j=0; j<n; j++)
{
for(int k=0;k<0;k++)
{
r = rand( ) % 365; //0--364
if(birthday[r])
{
match++;
break; // two person already have same birthday
}
}
birthday[r]=true;
}
}
cout<<"The probaility of two person sharing the same birthday in a room of" <<i<<"person is"<< (float)match/n<<endl;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.