Java random shuffle list with two elements using Collections.shuffle

Question

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;

public class ShuffleList {
  public static void main(String[] args) {
    String [] file = {"1","2"};
    long seed = 3;
    ArrayList<String> fileList = new ArrayList<String>(Arrays.asList(file));
    for (int i=0; i<200; i++) {
      Collections.shuffle(fileList, new Random(seed));
      seed = seed +1;
      System.out.println(seed + "," + fileList);
    }
  }
}

The output is 200 lines of [1,2], not random shuffle at all. In fact this is true for all seed < 4000. Why is that? I tried with a list of 3 elements and seeds from 1 to 100 makes the list seemingly random. But what's wrong with a list of 2 elements?

Answer 1

The problem isn't with shuffle - it's with Random with small seeds. Here's a program demonstrating that:

import java.util.Random;

public class Test {
    public static void main(String[] args) {
        int total = 0;
        for (int seed = 0; seed < 4000; seed++) {
            Random rng = new Random(seed);
            total += rng.nextInt(2);
        }
        System.out.println(total);
    }
}

You'd expect an output of about 2000 - about half calls to nextInt should return 0, and about half should return 1. Instead, it's 4000 - every call returns 1.

Using seeds [10000, 13999) you get 240 - so vastly more of the calls return 0 than 1.

Using seeds [100000, 103999) you get 3226 - getting a bit better...

Using seeds [1000000, 1003999) you get 2105 - much better.

I don't know nearly enough about the maths of RNGs to say why this happens, but it does look like java.util.Random is kinda broken for small seeds.