C++ Birthday Probability

Question

I am trying to teach myself C++ in preparation for graduate school this coming fall but I am having some trouble with this birthday paradox problem. My code seems to run ok but I am not getting the correct output. If anyone has any suggestions please let me know.

 #include <cstdlib>
 #include <iostream>
 #include <ctime>

 using namespace std;

int main()
{
    srand(time(NULL));

    const int trials = 100000;
    int birthdays[50];
    int numMatches;


    for(int i = 2; i <= 50; i++)
    {
        numMatches = 0;

        for(int j = 1; j <= trials; j++)
        {

            for(int k = 1; k <= i; k++)
            {
                birthdays[k] = (rand() % 365) + 1;
            }

            int m = 1;
            bool matched = false;
            while(m < i && !matched){
                int n = m + 1;

            while(n <= i && !matched){
                if(birthdays[m] == birthdays[n]){
                    numMatches++;
                    matched = true;
                }
                n++;
            }
                m++;
            }
        }

        cout << "Probability of " << i << " people in a room sharing a birthday is \t"
          << ( float(numMatches) / float(trials) ) << endl;
    }  
}

Answer 1

Your code is not computing the probability of two people in a room of 50 sharing a birthday. There's several bugs, mostly with indexing, but here's the biggest issue:

for(int j = 1; j <= trials; j++) {
    // assigns a random birthday to the first i people (should be 0 indexed)
    for(k = 1; k <= i; k++)
        birthdays[k] = (rand() % 365) + 1;
    // Does *exactly* the same thing as the previous loop, overwriting what
    // the initial loop did. Useless code
    for(m = 1; m <= i; m++)
        birthdays[m] = (rand() % 365) + 1;
    // At this point, m = k = i + 1. Here you check if
    // the i + 1st array value has the same b-day. It will, because they're
    // the same thing. Note you never set the i + 1st value so the loops
    // above did nothing
    if(birthdays[k] == birthdays[m])
        ++numMatches;
}

So what you've got here is something like:

• Perform 48 iterations of the following (from your first loop which goes from 2 to 50: no idea where those values came from)
  • For each of those 48 iterations, perform 10k iterations of:
    • assign a bunch of random stuff to an array overwriting stuff
    • Ignore the values you wrote in the array, do a comparison that's always true and increment numMatches by 1

Answer 2

I think the code must be something like this.

#include <cstdlib>
#include <iostream>
#include <ctime>

using namespace std;

int main() {
  srand(time(NULL));
  int birthdays[10000][50];
  int numMatches;
  int trials=10000,check;
  for(int n=0;n<trials;n++)
    {
    for(int j=0;j<50;j++)
      {
        birthdays[n][j]=rand()%365+1;
      }
    }
  for(int i=2;i<=50;i++)
     {
       numMatches=0;
       for(int n=0;n<trials;n++)
          {
         check=1;
         for(int j=0;j<i;j++)
            {
              for(int k=j+1;k<=i;k++)
                {
                  if(birthdays[n][j]==birthdays[n][k]&&check)
                    {
                     numMatches++;
                     check=0;
                    }
                }
            }
      }
 cout << "Probability of " << i << " people in a room sharing a birthday is \t" <<
     (static_cast<float>(numMatches) / (trials)) << endl;
   }
}

Answer 3

Consider what's going on here:

    for(int j = 1; j <= trials; j++) {
        for(k = 1; k <= i; k++)
            birthdays[k] = (rand() % 365) + 1;
        for(m = 1; m <= i; m++)
            birthdays[m] = (rand() % 365) + 1;
        if(birthdays[k] == birthdays[m])
            ++numMatches;
    }

You go through i birthdays and assign a random number, then you go through the same i birthdays and assign them a new random number. Then you try to find a match for just one value of k and m (which both happen to equal i+1, which isn't one of the values set!).

My suggestion is to break the problem down into smaller units that will make it easier to figure out how to code - here are the functions I would try to write.

/* randomizeBirthdays()
 *   Put n random birthdays into the pre-allocated array birthdays.
 *   birthdays must of course be of length <= n.
 */
void randomizeBirthdays(int * birthdays, int n);

/* hasMatchingBirthdays()
 *   Check if birthdays array has two people with the same birthday
 *   in the first n entries.
 *   Return value is boolean.
 */
bool hasMatchingBirthdays(int * const birthdays, int n);

/* probabilityOfMatch()
 *   Calculate the probability that at least 2 out of n people will
 *   have the same birthday, using nTrials number of trials.
 *   Return value is double.
 */
double probabilityOfMatch(int n, int nTrials);

If you break it down like this it becomes easier to write and easier to troubleshoot.

Answer 4

As I said in comments already:

I think your aim is to test if 2 people in room of 2-50 people share birthday, not if 2-50 people share birthday as you say in output. And that's 2 people out of 23 have 50.7%, not 24.

I completely reworked your code:

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

#define DAYS_IN_YEAR 365
#define TRIALS 10000

void clearArray (bool * array)
{
    for (int i = 0; i < DAYS_IN_YEAR; i++)
        array[i] = false;
}

int main()
{
    srand(time(NULL));
    bool birthdays[DAYS_IN_YEAR]; //we are trying to hit same day in year twice
    int r, numMatches;

    for(int i = 2; i < 50; i++)
    {
        numMatches = 0;

        for(int j = 0; j < TRIALS; j++)
        {
            clearArray(birthdays);

            for(int k = 0; k < i; k++)
            {
                r = rand() % DAYS_IN_YEAR; // == 0-364
                if (birthdays[r])
                {
                    numMatches++;
                    break;  // 2 people already have same birthdays here
                }
                birthdays[r] = true;
            }
        }

        cout << "Probability of 2 people having same birthday in room of " << i << " people is "
             << (float)numMatches / TRIALS << endl;

    }
 }

Output:

Probability of 2 people having same birthday in room of 23 people is 0.516