Your answer is one click away!

loukios February 2016
### Java birthday paradox algorithm

I've made a small implementation of the famous birthday paradox, trying to find a collision between two random birthdates (here integer between 1 and 365) for the first time. But it returns always a value around let's say 40 and 70, which does not fit the stats at all. Is something wrong with my algo, or with the random int generator, both ? Thanks for your feedback.

Here is the code :

```
public static void main(String[] args){
int[] birthday = new int[200];
for(int i = 0; i<20;i++){
Collision(birthday);
}
}
public static int Collision(int birthday[]){
Random rand = new Random();
for(int i = 1; i<birthday.length;i++){
birthday[i] = rand.nextInt(365);
}
int count = 0;
for(int i = 0; i<birthday.length; i++){
for(int j= i+1 ; j<birthday.length; j++){
if (birthday[i] == birthday[j]){
count++;
}
}
}
System.out.print(count+" ");
return count;
}
```

Here is the output for ex :

45 50 60 52 53 53 50 49 37 68 52 53 51 43 49 51 46 43 45 35

radoh February 2016

EDIT:

What you essentially did in your algorithm is that you generated 200 random birthdays and counted how many collisions exist among them.

You know you could make things a lot simpler by using a `Set`

, which is empty at the beginning. Then in a simple while loop generate birthdays (numbers up to 365), try adding them in the `Set`

, and the first time you get a collision - the number is already in the `Set`

- you have your answer (the answer being the size of the Set).

That is, if your goal really is to find a collision in minimum number of birthdays.

E.g., this:

```
Random rand = new Random();
for (int t = 0; t < 20; t++)
{
Set<Integer> b = new HashSet<Integer>();
while (true)
{
int n = rand.nextInt(365);
if (!b.add(n))
break;
}
System.out.print(b.size() + " ");
}
```

Produces:

```
15 30 24 4 8 19 10 40 32 31 30 14 41 30 15 7 15 52 24 27
```

Bathsheba February 2016

Your numbers look fairly reasonable.

But you are repeatedly instantiating a new `Random`

instance. That ruins the generator's statistical properties. Do it once at the beginning of your program.

(Eventually you'll need to consider February 29th too but that's very much a second-order effect).

Bohemian February 2016

Your algorithm seems OK and the results are reasonable.

FYI you could use streams to very efficiently do all the heavy lifting in 1 line:

```
private static Random rand = new Random();
public static int collision(int size) {
return size - Stream.generate(() -> rand.nextInt(365)).limit(size).distinct().count();
}
```

And a 1-line main:

```
public static void main(String[] args){
Stream.of(200).map(MyClass::collision).forEach(System.out::println);
}
```

Asked in February 2016

Viewed 2,931 times

Voted 14

Answered 3 times

Viewed 2,931 times

Voted 14

Answered 3 times