Birthday problem, Average number of people

Question

I'am trying to solve this Homework:

Suppose that people enter an empty room until a pair of people share a birthday. On average, how many people will have to enter before there is a match? Run experiments to estimate the value of this quantity. Assume birthdays to be uniform random integers between 0 and 364.

The average is 24.61659. See this wikipedia page for the maths. Birthday_problem

My approach:

• Generate random numbers in range [0 - 364]
• add them to a set until a duplicate is generated (set.add returns false)
• add the count (or set size) to a list
• repeat this X-times
• calculate the average of the list

Code:

public static void main(String[] args) {        
    List<Integer> list = new ArrayList<>();
    for(int i = 0; i<10000; i++){
        int count = 0;
        Set<Integer> set = new HashSet<>();
        while(set.add(ThreadLocalRandom.current().nextInt(0, 365))){
            count++;
        }
        list.add(count);
    }
    double avg = list.stream().mapToInt(Integer::intValue).average().getAsDouble();
    System.out.println(avg);
}

My output is always under 24. E.g 23.6285

• I've tried to run the for-loop 1000, 10000, 1000000 times
• I've tried ThreadLocalRandom.current().nextInt(0, 365), nextInt(0, 364), nextInt(0, 366)
• I've tried list.add(count); and list.add(set.size());

But I'am getting always an average < 24. Mostly something like 23.629237.

Do you see any mistakes and why I'am not getting the correct value, which is approx. ≈24.61659?

Answer 1

Note that your answer is almost exactly 1 less than the expected. That's a clue: it tells you that you're probably under-counting by 1, which is a very common bug.

Consider your condition:

while(set.add(<newPersonsBirthday>)){
    count++;
}

That won't count the last person! They won't be added to the count, and so you're not including them in the set of people in the room. You've counted everybody in the set except the person who triggered the match -- but they're part of the set.

Just add count + 1 to your list, to account for that person.