Exercise 3

Random Experiments, Pre-Image, Collision

Generate random numbers between $0$ and $n - 1$ for a given upper limit $n$ in any programming language, until …

1. a predefined value $y$ is output (simulates pre-image)

2. a value $y$ is output that matches one of the previously generated values (simulates collision)

Count the number of generated numbers until the event occurs.

Verify by averaging the experiments that for $n = 10,000$ …

1. on average $10,000$ numbers need to be generated

2. on average approximately $125$ numbers need to be generated