Tranquility Tranquility - 9 months ago 38
Java Question

Java's Random class behaviour clarification

I have a class 'A' that holds an instance of Random, and which simulates rolling a die, e.g. 6 sides, with a result of 1 - 6 being generated on each 'roll'.

I have another class 'B' that may hold a reference to an object of type A, and should delegate to its 'roll' method.

Another person needs to write a unit test to assess that the method in class B is delegating to the 'roll' method in class A correctly. In order to do this I simply need to invoke the method X times and check that the score updates.

Currently in the unit test I have a loop that goes round up to 1000 times and if the score hasn't been updated then I assume it is beyond the realms of possibility that the same number could have been rolled consecutively 1000 times! I have however picked the number 1000 out of thin air. I wanted to pick a more accurate number, based on the actual behaviour of Java's Random class.

From reading the API it says it is states it is "a linear congruential pseudorandom number generator..". What I'm trying to ascertain is based on it using a 48-bit, is there a number of times for which it is impossible for the same value to be repeated. E.g. in my scenario where the numbers 1 - 6 could be generated, is it say impossible to get the same number, e.g. 6, more than 20 times in a row? I'm looking for that information if anyone knows it.

UPDATE -- I'll make the question simpler. With the Java random class, if I call nextInt(6), how many times is it possible for me to receive the same result consecutively. E.g. mathematically is there a limit based on the 48-bit seed and workings of the algorithm of the Random class? I want an answer that states, e.g. "It is categorically impossible to get the same result more than X times" where X is my answer.

Answer Source

The PRNG used by Random has only 248 different states according to the documentation. The sequence of numbers generated with nextInt(6) therefore repeats with a period of at most 248.

We can assume that all 6 possible outcomes are generated eventually independent of the seed value, otherwise, the generator is of very bad quality. Therefore, there must be a limit X < 248 satisfying "It is categorically impossible to get the same result more than X times".

To find the smallest such X is however not trivial. The brute force method would generate 248 sucessive numbers and check.