r/javahelp • • Apr 26 '21

Solved How random is Java.util.Random() ?

I am trying to simulate a coin flip, to do this I generate a random number either 0 or 1. 0 for heads, 1 for tails. I tested this by flipping a coin 1000 times, but 66% of the times it is heads.

int coin_flip() {

Random rand = new Random();

int flip = rand.nextInt(2);

return flip ;

}

22 Upvotes

44 comments sorted by

•

u/AutoModerator Apr 26 '21

Please ensure that:

  • Your code is properly formatted as code block - see the sidebar (About on mobile) for instructions

  • You include any and all error messages in full

  • You ask clear questions

  • You demonstrate effort in solving your question/problem - plain posting your assignments is forbidden (and such posts will be removed) as is asking for or giving solutions.

    Trying to solve problems on your own is a very important skill. Also, see Learn to help yourself in the sidebar

If any of the above points is not met, your post can and will be removed without further warning.

Code is to be formatted as code block (old reddit: empty line before the code, each code line indented by 4 spaces, new reddit: https://imgur.com/a/fgoFFis) or linked via an external code hoster, like pastebin.com, github gist, github, bitbucket, gitlab, etc.

Please, do not use triple backticks (```) as they will only render properly on new reddit, not on old reddit.

Code blocks look like this:

public class HelloWorld {

    public static void main(String[] args) {
        System.out.println("Hello World!");
    }
}

You do not need to repost unless your post has been removed by a moderator. Just use the edit function of reddit to make sure your post complies with the above.

If your post has remained in violation of these rules for a prolonged period of time (at least an hour), a moderator may remove it at their discretion. In this case, they will comment with an explanation on why it has been removed, and you will be required to resubmit the entire post following the proper procedures.

To potential helpers

Please, do not help if any of the above points are not met, rather report the post. We are trying to improve the quality of posts here. In helping people who can't be bothered to comply with the above points, you are doing the community a disservice.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

23

u/HairbrainedScheme Apr 26 '21

You should not be creating a new instance of Random for each flip. Create one single instance at program startup, and reuse it.

3

u/[deleted] Apr 26 '21

In the main method ?

Edit : I figured it out, thanks.

6

u/sweetno Apr 26 '21

While you can see the replies here mentioning that Random is not entirely random, it was designed to replicate statistical behavior of true random numbers. Therefore if you see the difference from the modelled distribution this large, you need to look for mistakes in the code.

-2

u/msx Apr 26 '21

Java Random is random enought for all applications

1

u/sweetno Apr 26 '21

Really? What is its period?

3

u/BS_in_BS Extreme Concrete Code Factorylet Apr 26 '21

248

1

u/msx Apr 26 '21

Don't remember exacly but pretty huge, something in the range of Integer

12

u/[deleted] Apr 26 '21

If you create the Random instance at program startup, the random number sequence is seeded only once, with the system time at startup.

If you create the Random instance on every flip, the random number sequence is seeded on every flip, with the system time at flip.

14

u/spdqbr Apr 26 '21

Which can be a problem if you're seeding it inside a tight loop. If the loop executes multiple times more quickly than the resolution of the timer used to seed the RNG, you'll get multiple calls with the same seed and offset (thus giving in the same result).

4

u/HecknChonker Extreme Brewer Apr 26 '21

The seed is changed every time a random number is generated. The timestamp is only used for the initial seed value. There is no need to instantiate a new instance of Random each time.

2

u/amfa Apr 27 '21 edited Apr 27 '21

The seed is changed every time a random number is generated.

The seed is always the same.

If you use the same seed you get the same sequence of "random" numbers.

If you are able to create two different random object at the same system time both will give ou the exact same "random" number if you call nextInt()

Ok looked it up not true as each invokation of the Random constructor will (likely) use a different seed even if you manage to invoke it at the same "System.nanoTime()"

1

u/nutrecht Lead Software Engineer / EU / 20+ YXP Apr 27 '21

This is the correct answer. By creating new Random instances inside a tight loop instead of just reusing the same instance your random numbers become LESS random.

1

u/msx Apr 26 '21

This. Random is seeded with millis (iirc), that program probably runs in just a bunch of them, it will use the same seeds multiple time, hence the imbalance.

1

u/amfa Apr 27 '21 edited Apr 27 '21

I just looked it up. should not happen.First it uses System.nanoTime() I did not get the same time after two calls right after each other so this should always be a different time.

Additionally there is an seedUniquifier method that will create "unique" seeds for every call to the constructor of Random

https://hg.openjdk.java.net/jdk8/jdk8/jdk/file/tip/src/share/classes/java/util/Random.java

2

u/msx Apr 27 '21

You're right, evidently i didn't remember correctly :)

Anyway, it still stands that randomness is granted if you start with a seed and keep "extracting" from that seed. If you instead keep reseeding the Random each loop, there's no guarantee of randomness.

0

u/HecknChonker Extreme Brewer Apr 26 '21

Each time a random number is generated the seed is modified. The random number generator only uses the system timestamp for the initial seed value.

0

u/nutrecht Lead Software Engineer / EU / 20+ YXP Apr 27 '21

That's not the point. The problem is that if you create new instances all the time instead of just reusing the same instance, the output becomes less random.

1

u/HecknChonker Extreme Brewer Apr 27 '21

What are you even talking about? It continues cycling through a massive number of seeds every time you generate a number, and it maintains it's pseudo randomness.

Also the person I was replying to stated incorrectly that it would reuse the same seeds which is also incorrect.

0

u/nutrecht Lead Software Engineer / EU / 20+ YXP Apr 27 '21

What are you even talking about? It continues cycling through a massive number of seeds

Both of you are confusing each other, probably also due to how you use the term seed. The term is only used for the initial value used to 'seed' the internal state. That internal state indeed cycles with each call to the class. What that person mean, which is correct, is that when you use the same seed again, you will get the same sequence of numbers out of it.

What I said, which is also correct, that you get less random results if you create a new random instance before every call, because while sequential numbers might be very well distributed, time isn't.

1

u/HecknChonker Extreme Brewer Apr 27 '21 edited Apr 27 '21

The term is only used for the initial value used to 'seed' the internal state.

I am talking about a variable inside the Random class called seed.

There is an initial seed value, but the seed is set to a new random value every time you generate a number. It's definitely still called the seed.

If you dig into the source code for Random it does this on every call to generate a number:

protected synchronized int next(int bits) {
    seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
    return (int) (seed >>> (48 - bits));
}

OpenJDK uses this implementation:

protected int next(int bits) {
    long oldseed, nextseed;
    AtomicLong seed = this.seed;
    do {
        oldseed = seed.get();
        nextseed = (oldseed * multiplier + addend) & mask;
    } while (!seed.compareAndSet(oldseed, nextseed));
    return (int)(nextseed >>> (48 - bits));
}

And yes, using the same initial seed will generate the same sequence of numbers. This is indicated in the javadoc:

If two instances of {@code Random} are created with the same
seed, and the same sequence of method calls is made for each, they
will generate and return identical sequences of numbers

3

u/RiceKrispyPooHead Apr 27 '21

You probably aren't measuring the number of heads vs tails correctly. There really isn't any reason it shouldn't work.

1

u/[deleted] Apr 27 '21

This the answer, I wasn't keeping track of the number I got from random, and instead comparing a new random number each time, when I stored the random number in a variable it worked fine.

28

u/x42bn6 Apr 26 '21

66% is suspiciously-close to two-thirds, so I'd check to see if your checking-of-heads logic is correct. Maybe you have some code that compares three (not two) values, and you're populating heads and tails, but not the third missing value.

It's also good practice to not create a new Random object within a loop. Pretend new Random() creates a mysterious box that spits out random numbers. You don't need a thousand mysterious boxes - you just need to poke the box a thousand times. So call new Random() outside of the loop, but within the loop, call nextInt(2).

3

u/nutrecht Lead Software Engineer / EU / 20+ YXP Apr 27 '21 edited Apr 27 '21

Holy crap there are a lot of bad responses here. There are two main issues:

  • Random is very well distributed so if you see a 66/33 distribution it simply means your code is wrong.

  • You should not recreate random objects on every call, this makes the outcome less evenly distributed because Random uses the system time as a seed, and the pattern of instantiation is not random.

What is NOT the problem:

  • Random itself is not the problem

  • Using SecureRandom in such a situation is pointless; it's mainly used for cryptography. For anything outside of that; you generally just should use Random.

Proof:

import java.util.Random;

public class Example {
    private Random random = new Random();

    int coin_flip() {
        Random rand = new Random();
        int flip = rand.nextInt(2);

        return flip ;
    }

    int betterCoinFlip() {
        return random.nextInt(2);
    }

    public static void main(String... argv) {
        var example = new Example();
        var one = new int[2];

        for(int i = 0;i < 1000;i++) {
            one[example.coin_flip()]++;
        }
        System.out.println("Original:");
        for(int i = 0;i < 2;i++) {
            System.out.println(i + ": " + one[i] + " (" + one[i] / 10.0 + "%)");
        }

        var two = new int[2];

        for(int i = 0;i < 1000;i++) {
            two[example.betterCoinFlip()]++;
        }
        System.out.println("Proper one");
        for(int i = 0;i < 2;i++) {
            System.out.println(i + ": " + two[i] + " (" + two[i] / 10.0 + "%)");
        }
    }
}

Output:

Original:
0: 519 (51.9%)
1: 481 (48.1%)
Proper one
0: 497 (49.7%)
1: 503 (50.3%)

So the issue here is OP is simply measuring wrong.

2

u/[deleted] Apr 27 '21

Yep I wasn't keeping track of the number I got from random, and instead compared a new random number each time, to check if it was heads or tails, when I stored the random number in a variable it worked fine.

9

u/[deleted] Apr 26 '21 edited Apr 26 '21

How are you measuring it?

This is what I'm getting;

int[] vals = { 0, 0 };
for (int i = 0; i < 1_000_000; i++) {
    Random r = new Random();
    vals[r.nextInt(2)]++;
}
IntStream.of(vals).mapToDouble(cnt -> cnt / 1_000_000.0).forEach(System.out::println);

0.499753
0.500247

14

u/dionthorn this.isAPro=false; this.helping=true; Apr 26 '21 edited Apr 28 '21

Here is the source code for Random.

Internally it is using a mersenne twister* which is pseudo-random but generally 'good enough'

Use much larger samples than 100 or run the 100 test 1000 times and aggregate the results.

http://developer.classpath.org/doc/java/util/Random-source.html

/* It is not, see commenter below.

4

u/BS_in_BS Extreme Concrete Code Factorylet Apr 26 '21

Internally it is using a mersenne twister

where are you seeing that?

44:  * This class generates pseudorandom numbers.  It uses the same
45:  * algorithm as the original JDK-class, so that your programs behave
46:  * exactly the same way, if started with the same seed.
47:  *
48:  * The algorithm is described in <em>The Art of Computer Programming,
49:  * Volume 2</em> by Donald Knuth in Section 3.2.1.  It is a 48-bit seed,
50:  * linear congruential formula.

1

u/dionthorn this.isAPro=false; this.helping=true; Apr 27 '21

Good call it is a different algorithm.

7

u/glesialo Apr 26 '21

I have never used it but there is also a 'java.security.SecureRandom':

A cryptographically strong random number minimally complies with the statistical random number generator tests specified in FIPS 140-2, Security Requirements for Cryptographic Modules, section 4.9.1. Additionally, SecureRandom must produce non-deterministic output. Therefore any seed material passed to a SecureRandom object must be unpredictable, and all SecureRandom output sequences must be cryptographically strong, as described in RFC 4086: Randomness Requirements for Security.

7

u/msx Apr 26 '21

You souldn't use SecureRandom when random is good enought. Performances are much worst than Random. SecureRandom is for cryptography

1

u/glesialo Apr 26 '21

It is a tradeoff between 'randomness' and performance. The programmer should decide.

3

u/nutrecht Lead Software Engineer / EU / 20+ YXP Apr 27 '21

In this case you're pointing OP in a direction that's wrong for them. This is not the cause of the problem OP has.

4

u/le_bravery Extreme Brewer Apr 26 '21

Other commenters are right to point you in the direction of SecureRandom and advise you to reuse your object.

In isolation, computers aren’t random. However, many computers handle this by capturing “entropy” around them. Seemingly unrelated things can be treated as random inputs, like random mouse movements. Key clicks and what nanosecond they fire on. Stuff like that. This works great for standard desktop computers.

For servers, this falls apart a little bit so data centers solve this problem by directly adding entropy to a system. If you don’t have this properly configured on servers, and you’re using secure random, you can actually exhaust all your entropy and your program can freeze up.

This kind of thing is relevant in credit card processing and other secure systems that rely on random stuff for their security algorithms.

4

u/nutrecht Lead Software Engineer / EU / 20+ YXP Apr 27 '21 edited Apr 27 '21

Other commenters are right to point you in the direction of SecureRandom and advise you to reuse your object.

There's no point at all in moving to SecureRandom for what OP is doing. This is not the cause of the 66/33 distribution.

1

u/TilionDC Apr 27 '21

If seed is time in ms and it took 3 ms to perform the operation and you reset random each time you get 3 different results of which 2 seems to be the same since you are expecting a binary outcome.

Use the same random and just do nextint 1000 times instead.

-1

u/URockFest Apr 26 '21

I’ve never actually tried this, but could you get a larger range to get more chance of random numbers, then just modulo it to find out if that number is even or odd. Associating heads and tails with even and odd?

1

u/juckele Barista Apr 27 '21

That's not the problem here. Internally Random already has really big numbers (that it's doing a lot of bit math on) that it converts to the small number you request right at the end. Asking it for a big number and squishing it yourself is at best wasting an operation for no gain, and could potentially harm the quality depending on algorithms used.

1

u/URockFest Apr 27 '21

Yeah, it was just an idea

0

u/stickles101 Apr 26 '21

Maybe use Math.random(2)

0

u/[deleted] Apr 26 '21

[deleted]

0

u/dionthorn this.isAPro=false; this.helping=true; Apr 26 '21

random.org gives a good overview of Randomness and provides a True Random Number generator:

https://www.random.org/faq/#Q2.1