Simulating the Birthday Paradox on a given Set As a first step, we will simulate
ID: 3790390 • Letter: S
Question
Simulating the Birthday Paradox on a given Set
As a first step, we will simulate the problem on a set of size n, where n is provided as a parameter to our program.The overall goal is to repeatedly draw randomly from that set until an element has been drawn twice. We want to repeat this test a number of times, and see how many draws are required on average. We will also report the minimum and maximum value found, as well as the standard deviation.
By default, the size of the set to draw from is 365 elements, and the experiment is repeated 50 times. It is however possible to optionally specify both the size of the set and the number of elements from the command line.
Here is a sample run using the default values:
> java BirthdayParadox
We have run 50 experiments.
the minimum was 4
the maximum was: 49
the mean was: 23.8
the standard deviation was: 11.65
Here is another sample run, this time on a set of size 10,000, with 2,500 experiments:
> java BirthdayParadox 10000 2500
We have run 2500 experiments
the minimum was 4
the maximum was: 429
the mean was: 126.34
the standard deviation was: 66.25
As can be seen, for both mean and standard deviation, only two decimal are shown.
A detailed description of the classes can be found here:
Explanation / Answer
public class BirthdayParadox { /** * Random generator */ private static java.util.Random generator = new java.util.Random(); /** * Runs the series of experiments, and stores the result into * a Statistics object * * @param range the size of the set from which random number are drawn * @param numberOfRuns the number of experiments to run * * @return a reference to a Statistics instance that holds the result * of the experiment */ public static Statistics runExperiments(int range, int numberOfRuns){ // REPLACE THE BODY OF THIS METHOD WITH YOUR OWN IMPLEMENTATION } /** * Runs a single experiment. * The parameter range defines the size of the set from which * the experiment is drawn * * @param range the size of the set from which random number are drawn * * @return the number of random draw in the set that the method * used before drawing the same element for the second time */ private static int oneRun(int range){ // REPLACE THE BODY OF THIS METHOD WITH YOUR OWN IMPLEMENTATION } /** * Main method. The default size of the set is 365, and * the experiment is run 50 times. Both numbers can be reset * from the command line. * This method runs the experiments and prints the * resulting Statistics * * @param args if not empty, contains the runtime values for * the size of the set and the number of runs */ public static void main(String[] args) { // REPLACE THE BODY OF THIS METHOD WITH YOUR OWN IMPLEMENTATION } } public class Statistics { // ADD HERE INSTANCE VARIABLES DECLARATION /** * Constructor. * * @param numberOfRuns the number of experiments that will be run */ public Statistics(int numberOfRuns){ // REPLACE THE BODY OF THIS METHOD WITH YOUR OWN IMPLEMENTATION } /** * Updates statistics after one experiment. * This method cannot be called more times than the * paramter that was passed in the constructor. If * it is, an error message should be printed and * no change should occur. * @param value the result of the new experiment */ public void updateStatistics(int value){ // REPLACE THE BODY OF THIS METHOD WITH YOUR OWN IMPLEMENTATION } /** * @return the current average of the values passed * to the method updateStatistic */ public double average(){ // REPLACE THE BODY OF THIS METHOD WITH YOUR OWN IMPLEMENTATION } /** * @return the current standard deviation of the values passed * to the method updateStatistic */ public double standardDeviation(){ // REPLACE THE BODY OF THIS METHOD WITH YOUR OWN IMPLEMENTATION } /** * @return Returns the complete statistics information: * current minimum, current maximim, current average and * current standard deviation. For the last two, only two * digits decimals are shown */ public String toString(){ // REPLACE THE BODY OF THIS METHOD WITH YOUR OWN IMPLEMENTATION } }