Lawrence Wagerfield Lawrence Wagerfield - 3 years ago 158
Scala Question

Random.nextInt returns contiguous same-value integers (frequently)

I see results like the below when running

scala.util.Random().nextInt(3)
81 times (Java developers, please see
edit
for how this relates):

200010202002112102222211012021020111220022001021101222222022210222220100000100010


Notice the large contiguous blocks:
000
,
22222
,
111
,
222222
,
222
,
22222
,
00000
,
000
.

Intuitively, the sequence doesn't seem naturally / "real-world coin flip" random.

For example, to achieve
6x
contiguous
2
s there's only a
0.4%
chance (AFAIK) and for
5x
contiguous values there's a
1.2%
chance ... so it seems unlikely I should keep seeing patterns like this in the output.

Would this happen in the real-world with a 3-sided coin? Or is this an expected deviation from "true random" when using Java's
Random.nextInt(exclusiveMax)
method?

EDIT:

I've actually been using
scala.util.Random.nextInt(int)
, which creates a new global
java.util.Random
via
new java.util.Random()
.

Answer Source

This isn't a joke: I'd try it in the real world (probably easiest with two coins: Both heads = 0, mixed = 1, both tails = 2). I suspect you'll see the same result.

You only have three values, so the chances of something being a 2 are always 1:3. You're quite right that, having got a 2, your odds of getting 2 five more times in a row are about 0.04%, which is indeed unlikely in 81 rolls. But after getting a 2, your odds of getting four more are (as you say) 1.23% — much more likely, and not surprising in 81 rolls.

Running the program below myself, I routinely get runs of three in an 81-roll batch and frequently get runs of four, but only rarely runs of five, and quite rarely runs of six. All of which largely matches my expectation.

Measuring the randomness of a PRNG is a quite complicated topic. The simplistic measure is to run it millions of times and then see if you've gotten each value ~0.33333333% of the time. But of course, that could be a million 0s followed by a million 1s followed by a million 2s, which would be a suspicious random result. :-) But you could try several of the approaches discussed in that Wikipedia article if you want to test your setup. Or subscribe to sources of true randomness like https://www.random.org/. Or a random USB device (though I'd subject one of those to quite a lot of due diligence).

My program:

import java.util.*;

public class E {

    public static void main(String[] args) {
        Random r = new Random();
        Map<Integer,Integer> runs = new TreeMap<>();
        int last = -1;
        int run = 0;
        for (int i = 0; i < 81; ++i) {
            int v = r.nextInt(3);
            if (v != last) {
                if (i != 0) {
                    if (runs.containsKey(run)) {
                        runs.put(run, runs.get(run) + 1);
                    } else {
                        runs.put(run, 1);
                    }
                    System.out.println(" (" + run + ")");
                }
                last = v;
                run = 0;
            }
            ++run;
            System.out.print(v);
        }
        System.out.println("\n****");
        for (Map.Entry e : runs.entrySet()) {
            System.out.println(e.getKey() + ": " + e.getValue());
        }
    }
}
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download