Birthday Paradox Simulation The birthday paradox , states that given a group of

Question

1. 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?

  int irand2bound(int bound) {     return static_cast<int>( rand() / (RAND_MAX + 1.0) * bound ); }  

Explanation / Answer

#include <iostream>
#include <cmath>
#include <cstdlib>
#include <iomanip>
#include <ctime>
using namespace std;

int count;
float percentcalculate;
float percentrandom;
float percentdiff;
int DAYS = 365;
int TESTCOUNT = 5000;
int people;
int i;
int test;

void main ()

{
cout << "this is the birthday paradox program" << endl;
cout << "this determines, from 2 - 50 people" << endl;
cout << "the observed and actual probability" << endl;
cout << "of any of those 2 people to share the same birthday" << endl;
cout << "going off of only month and day" << endl;
cout << "people" ;
cout.width (10);
cout << "ob. prob.";
cout.width (10);
cout << "ac. prob.";
cout.width (10);
cout << "percent diff" << endl;

for (count = 2; count <=50; count ++);
{
int people = count;
for (test = 1; test <= TESTCOUNT; test ++);
{
int birthday [count];
birthday [count] = rand () % 365 + 1;
if (birthday [count] = 0
{
birthday = 1;
}
else if (birthday [count] = 1)
samecount ++;

}

percentrandom = ;
percentcalculate = ;
percentdiff = abs(percentrandom - percentcalculate) * 100;
cout << people;
cout.width(10);
cout << percentrandom;
cout.width(10);
cout << percentcalculate;
cout.width(10);
cout << percentdiff << endl;
count++;
}


}

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.