CODEWITHSUNDEEP
java
nopens
nopens

Reputation: 761

Birthday problem, Average number of people

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:

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

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?

Upvotes: 6

Views: 416

Answers (1)

yshavit
yshavit

Reputation: 43456

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.

Upvotes: 11

Related Questions