More information about randomInt being biased?

[voltrevo]

I looked sideways at your readme when you said that:

function randomInt(min, max) {
  return Math.floor(Math.random() * (max - min)) + min;
}

produced a biased/non-uniform distribution. Math.random()'s contract is to produce a random number from a uniform distribution on [0, 1), and given that contract, I don't see how randomInt incorrectly transforms that to a uniform distribution of the integers in [min, max). It's a bit unclear whether you're suggesting that Math.random() fails to be uniformly distributed on [0, 1). Are you suggesting that? If so, which browsers are affected?

I tried this on Chrome 45:

function randomInt(min, max) {
  return Math.floor(Math.random() * (max - min)) + min;
}

var tallies = [0, 0, 0, 0, 0];

for (var i = 0; i !== 1000000; i++) {
  tallies[randomInt(0, 5)]++;
}

console.log(tallies);

And got this output:

[199601, 200204, 200379, 200016, 199800]

So it at least appears to be right. Could you elaborate please?

[ckknight]

It is vastly more apparent in integers close to 232, or really any integer that approaches but not surpass 2n. Given the distribution of bits in an integer, it is impossible to achieve true lack of bias simply by relying on floating point math, as in your case, 5 simply does not fit evenly into 2**32.

Given a perfectly uniform integer distribution, one can play a monte carlo game and run through each possibility of integers. In the following example, assume that we're only dealing with a floating point that holds 4 bits instead of 53 or 32 (which is Math.random()'s bit randomness, based on the engine):

Math.floor(0 * 5) = 0
Math.floor(0.0625 * 5) = 0
Math.floor(0.125 * 5) = 0
Math.floor(0.1875 * 5) = 0
Math.floor(0.25 * 5) = 1
Math.floor(0.3125 * 5) = 1
Math.floor(0.375 * 5) = 1
Math.floor(0.4375 * 5) = 2
Math.floor(0.5 * 5) = 2
Math.floor(0.5625 * 5) = 2
Math.floor(0.625 * 5) = 3
Math.floor(0.6875 * 5) = 3
Math.floor(0.75 * 5) = 3
Math.floor(0.8125 * 5) = 4
Math.floor(0.875 * 5) = 4
Math.floor(0.9375 * 5) = 4

As you can see, in this contrived example, we are slightly biased toward rolling a 0 compared to rolling 1-4. Of course, as you add more bits of entropy, the bias shows itself less and less, based on how close your integer distribution is to 2**n.

[ckknight]

Also, to clarify, Math.random() is perfectly uniform within [0, 1).

[rawr51919]

I can see why this would cause bias problems when trying to use a random number < 2n, but should this be made clear in the readme? @voltrevo has a good point there.

[rawr51919]

This I'll make an effort to fix in PR #65