Unbiased random integer generator

Question

After reading some posts, I've found out that using Math.random() in Java to generate an integer is somehow biased.

I came across an algorithm in this post:

Unbiased random number generator using a biased one

It generates an unbiased result between 0 and 1 and I wanted to use it for my program.

However, I'm trying to create an unbiased generator between 0 and a certain value (e.g. 7) in Java but I'm not really sure that if this algorithm works for a range of numbers.

If it doesn't, what must I do in order to create an unbiased integer generator that I want?

@JonSkeet the documentation of `Math.random()` says "When this method is first called, it creates a single new pseudorandom-number generator, exactly as if by the expression new java.util.Random" — Daniel Kaplan, Jun 18 '13 at 17:52
Multiply the output by 7, and it will be unbiased modulo the introduced error. Then, for integer results, truncate it. — jpaugh, Jun 18 '13 at 17:53
@tieTYT: Ah, that makes sense. Perhaps SecureRandom instead? — Jon Skeet, Jun 18 '13 at 17:55
@Dgrin91: `java.util.Random` should absolutely be unbiased. If you need to get an integer between 0 and 7, then `Random.nextInt` is the proper way to do it. — Louis Wasserman, Jun 18 '13 at 17:56

score 4 · Answer 1 · answered Jun 18 '13 at 18:16

You need to cite the reference that claims that the Java Math.random() is biased, and in exactly what way. That would be a huge problem, as this is a very core portion of the Java standard library.

Java provides SecureRandom which is more appropriate for cryptographic-strength random number generation. To use this to generate a number between 0 and N, you can use the same algorithm presented in the Random.nextInt(int) documentation but with SecureRandom instead.

Don't implement your own random number generator algorithm unless you are willing to go to the trouble to prove that it is better than the stock one. It is very hard to create a good quality algorithm and you are very likely to just make the problem worse.

Daniel Kaplan · Answer 2 · 2013-06-18T18:19:47.953

2

You can just use Random.nextInt(int). For your needs, use new Random().nextInt(8). As it says in the documentation:

Returns a pseudorandom, uniformly distributed int value between 0 (inclusive) and the specified value (exclusive)

But actually, I think you could have used Math.random() all along. Its documentation says:

When this method is first called, it creates a single new pseudorandom-number generator, exactly as if by the expression new java.util.Random

The source code for Math.random() is:

public static double random() {
    if (randomNumberGenerator == null) initRNG();
    return randomNumberGenerator.nextDouble();
}

And the documentation for nextDouble also says:

Returns the next pseudorandom, uniformly distributed double value between 0.0 and 1.0

edited Jun 18 '13 at 18:19

answered Jun 18 '13 at 18:01

Daniel Kaplan

62,768
50
234
356

Well, the key question is: is it **biased** or not? – Has QUIT--Anony-Mousse Jun 18 '13 at 18:04
@Anony-Mousse: Doesn't "uniformly distributed" mean unbiased? What's the difference? – Daniel Kaplan Jun 18 '13 at 18:04
There are different kinds of bias. A RNG optimized for speed may even be biased in the way that it produces *overly* uniform random numbers. – Has QUIT--Anony-Mousse Jun 18 '13 at 18:09
@Anony-Mousse: If we're going to get that deep into bias, it's very likely that anything the OP does is likely to just make the problem worse, unless he is very mathematically inclined... randomness is hard! "Don't write your own random number generation algorithm" – Steven Schlansker Jun 18 '13 at 18:11
@Anony-Mousse then I think the question should be more specific about what it needs. Given the current vagueness, I think this is the best answer and what most people would be looking for. – Daniel Kaplan Jun 18 '13 at 18:13
I agree that he should just be using `nextInt(8)` for his purposes. But you really need to point him to the version with the parameter. – Has QUIT--Anony-Mousse Jun 18 '13 at 18:15
@Anony-Mousse Ah right, "exclusive". Thanks for the correction. – Daniel Kaplan Jun 18 '13 at 18:19
2

Many programming languages have bad built-in random number generators, but Java's is actually pretty good, and `nextInt()` does all the right things to be correct. It's not the fastest, though. If you need one that's both fast and accurate, try my [ojrandlib](http://github.com/lcrocker/ojrandlib). – Lee Daniel Crocker Jun 18 '13 at 18:25

Has QUIT--Anony-Mousse · Answer 3 · 2013-06-18T18:20:18.957

I believe you misread those posts. The one you linked essentially says that you shouldn't use random.nextInt() % max, which is indeed biased; so this approach is very naive. However, if you look at the documentation or source code of Javas nextInt(max) function, it is more clever than that. Probably unbiased enough for you. Just learn more about the Java API, it has a lot of functionality...

The example discussed in detail generates a single bit in an unbiased way, not an unbiased double random between 0 and 1!

I'm not convinced that Java random generator is substantially biased in the way that you are concernced with. But it certainly is not a high-quality random, because it needs to be fast for most users. If you want a high entropy random, try using the high-quality random sources of your operating system.

Either way, If you want a random number from 0 to 7 using the method linked from your post (which probably is total overkill!), do this:

int bit1 = generateOneBitOfRandom();
int bit2 = generateOneBitOfRandom();
int bit3 = generateOneBitOfRandom();
int zerotoseven = (bit1 << 2) + (bit2 << 1) + bit3;

// Probably at least as good is the proper Java API:
Random random = new Random();
int zerotoseven2 = random.nextInt(8);

Again, most likely, java.util.Random nextInt(8) will be good enough for you. Unless you are doing cryptography. Then you really should consider just reading a byte from /dev/random, which may be accessing a hardware entropy pool, if your CPU or mainboard has such features (just hope that one isn't biased / bias cancelled). Which is most likely what Javas SecureRandom does. Again an example that the Java API is probably much more clever than you think it is.

score 1 · Answer 4 · answered Jun 18 '13 at 17:54

Try this:

int randomizer(int min, int max)
{
    int n = max - min + 1;
    int remainder = RAND_MAX % n;
    int x;
    do
    {
        x = rand();
    } while (x >= RAND_MAX - remainder);
    return min + x % n;
}

It is a modified version of the other algorithm you linked to.

score -1 · Answer 5 · answered Jun 18 '13 at 17:50

-1

If it only works from 0 to 1 just multiply whatever it gives you by 7, and you will have an unbiased random number from 0 to 7.

answered Jun 18 '13 at 17:50

David says Reinstate Monica

19,209
22
79
122

1

Actually, this will **not** work that easily, because rounding to integers messes this up. However, as @JonSkeet already pointed out, `java.util.Random` has a couple of stuff to choose from. – Has QUIT--Anony-Mousse Jun 18 '13 at 17:51
1

@Anony-Mousse It **will** still work even with rounding because if you get the same random number twice you round to the same point every time. The number might not be exactly the value you get when you properly multiply by 7, but its still random, and since it comes from the unbiased generator it is unbiased. – David says Reinstate Monica Jun 18 '13 at 17:53
Multiplying will always introduce some bias, because some numbers will be impossible as output. (In this case, only "multiples" of 7 are posible.) – jpaugh Jun 18 '13 at 17:55
If you naively round, it will actually have approx. 1/14th as chance for a 0, and < 1/14th the chance for a 7. If you `floor`, you will not get a 7 at all... – Has QUIT--Anony-Mousse Jun 18 '13 at 17:57
@Anony-Mousse Where do you get 1/14th chance for a 0? I think it would be much, much less. – David says Reinstate Monica Jun 18 '13 at 17:58
@Dgrin91 The interval [0;0.5[ is roughly 1/14th of [0;7[, which is what you get when you multiply [0;1[ with 7... – Has QUIT--Anony-Mousse Jun 18 '13 at 18:00
Ah, I didn't notice he wanted ints, I thought doubles where fine. In that case you are right. – David says Reinstate Monica Jun 18 '13 at 18:03
Well, "integer" is in the title and a couple of times in the post... ;-) – Has QUIT--Anony-Mousse Jun 18 '13 at 18:04

Unbiased random integer generator

5 Answers5