What are the odds that in a group of $$n$$ randomly chosen people, some of them will have the same birthday.? An intuitive guess would suggest that the chance of two individuals sharing the same birthday in a group of 23 is much lower than 50%, but that this is not the case. A 99% probability is even reached with just 57 people. This is called the birthday paradox1, because the mathematical truth contradicts naive intuition.

Suppose that a certain type of event has m possible outcomes. For example, you can throw a dice and get the values one through six, which means in this case m = 6, or a birthday can be on one of the 365 days of the year (where we do not take leap years into account), which means $$m = 365$$. Based on the probability theory, it can be proven that when there are n events, the probability that at least two events have the same outcome is equal to \[ P_2(n,m) = 1 - \frac{m!}{(m-n)! m^n} \quad \text{waarbij } m\in\mathbb N, 0\leq n\leq m \] In this exercise, however, we will not start from this formula, but we will experimentally demonstrate the birthday paradox.

Assignment

  1. Write a function happen_together that generates $$n$$ random outcomes for an event type with $$m$$ possible outcomes, and returns whether at least two events have the same outcome (True) or not (False). The values of $$m$$ and $$n$$ should be passed to the function as arguments.
    Hint: use a collection to draw events that have already occurred

  2. Write a function estimate_chance which calculates the probability that at $$n$$ random events with $$m$$ possible outcomes, at least two events have the same outcome. Here, the function must successively perform a test a number of times where $$n$$ random outcomes are generated, and re-occuring outcomes are frequently checked (in which case the function happen_together can be useful). The probability is then calculated as the number of tests in which certain outcomes occurred several times divided by the number of tests performed. The values of $$m$$, $$n$$, and the number performed tests must be passed to the function as a parameter, and the function must return the calculated odds as a result.

Note with evaluation: The functions happen_together and estimate_chance will be tested by examining whether the estimated probability lies close enough to the exact odds. So it is not inconceivable (but unlikely) that your source code is completely correct and the test still fails. In that case, you can just submit again. This is after all an assignment about probability.

Example

>>> happen_together(6, 3)
True
>>> happen_together(6, 3)
False
>>> estimate_chance(6, 2, 10000)
0.1676
>>> estimate_chance(365, 23, 10000)
0.5024