Why does this random() distribution look asymmetric?

Question

Edit: This is using Google Chrome 36

I was messing around with html5 canvas, generating points randomly distributed inside a cube and projecting that onto a 2D canvas. Surprisingly, the results don't look very symmetric at all, and I suspect that Javascript's Math.random() is letting me down.

Can anyone tell me why this is happening? Is it possible to make it actually look random, without making it slower?

var ctx = canvas.getContext('2d');

for (var i = 0; i < 10000000; i++) {
    var x = Math.random()*2-1, y = Math.random()*2-1, z = 2+Math.random()*2-1;
    x = (.5 + .5*x/z) * canvas.width;
    y = (.5 + .5*y/z) * canvas.height;
    ctx.fillRect(Math.floor(x), Math.floor(y), 1, 1);
}

http://jsfiddle.net/y10tvj26/ (Takes a while to load)

Silverpoint

Are you trying to cluster around the edges, or do you want it truely random throughout the square? – Tims

Obvious answer dilbert.com/dyn/str_strip/000000000/00000000/0000000/000000/… – Fiendish

What browser are you using? It's totally fine in Opera. – Epistasis

It looks good in Firefox as well, those white lines are not present. – Unlock

@Epistasis I see the described behavior in Chrome 38.0.2121.3. – Harder

Doesn't happen in Chrome with a different rng (window.crypto.getRandomValues), so yes its a problem with Chrome's default rng. – Unlock

Answer 1

Chrome has a documented issue that subsequent calls to Math.random() are correlated. In your algorithm, correlated values will tend to fall on a line on the canvas. An extra call to Math.random() breaks that correlation. I haven't seen reports that other browsers are affected.

Just call Math.random() an extra time on each call, and you'll get what you want.

var ctx = canvas.getContext('2d');

function r() {
    Math.random();
    return Math.random();
}
for (var i=0; i<10000000; i++) {
    var x = r()*2-1, y = r()*2-1, z = 2+r()*2-1;
    x = (.5 + .5*(x/z)) * canvas.width;
    y = (.5 + .5*(y/z)) * canvas.height;
    ctx.fillRect(x, y, 1, 1);
}

Updated on: http://jsfiddle.net/y10tvj26/5/

Reactant

Why? Please explain how that solves the issue. Also, OP does ask for the reason why the pattern emerged in the first place, not [only] how to deal with it. – Epistasis

I had put a comment regarding that below a different answer, which was otherwise misleading. I edited my response to include the reason and a reference. – Reactant

Answer 2

This is a case of pseudorandom number generation vs. random generation. Basically, there are numbers that will occur more often than others when you generate pseudorandom numbers (such as with the Math.random() function). See here for more information about the difference.

As far as actually making it look more "random", I would note that for a smaller range of i the image does look random, it's only when you choose a very large value that the flaws become apparent. Additionally, I don't believe seting your own seed for Math.random will be an adequate solution either, because you will still see degradation in the "randomness" when you iterate a very large number of times.

A potential solution would be to use a different library to generate pseudorandom numbers and see if it produces a better looking output. Other than that, you're pretty much constrained to the deterministic properties of computers (at least until powerful quantum computers show up on the market!).

Edit - This problem is unique to Google Chrome's implementation of Math.random() and documented in the following locations: Why is Google Chrome's Math.random number generator not *that* random? https://code.google.com/p/chromium/issues/detail?id=276886 https://code.google.com/p/v8/issues/detail?id=558

Killingsworth

Numbers that occur more often than others? No, the implementation would need to be severly f**ed up for that. Numbers that occur in patterns (that become visible when for example painting images), yes that might happen when poor algorithms are used. – Epistasis

@Epistasis as this error only is reported in Chrome, it appears that although random (see xkcd.com/221) there is something screwed up with the random number generator. Some numbers are indeed more likely than others. – Killingsworth

Looking at the code, the issue is correlations between adjacent calls to Math.random(). You can play games filtering specific bits from the generator and the problem persists. The additional call each time appears to work. – Reactant

@Erik: Both those bug reports you linked discuss a low entropy of V8's random() function. However, your first paragraph suggest that the distribution would be non-uniform - which is not the case. – Epistasis

As noted in documentation "The random number generator is seeded from the current time" so perhaps it is the additional time between calls that makes the difference? Also, this doesn't explain why the code only fails in Chrome, highlighing a problem with how it generates random numbers. – Killingsworth

@bergi developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/… – Killingsworth

@Erik: Those docs are specific to Mozilla's implementation. Also you need to understand how seeding works, multiple calls will typically use the same PRNG which was seeded at the time of the first call. – Epistasis

To be clear, the frequency of occurrence wasn't the issue. If you take the OP's code and make y=x+.00001, you get a straight line--so the issue is that back-to-back calls to Math.random() are correlated, and therefore they fall on a straight line in the OP's use case. If the OP had used a counter, every number would have appeared once, but the cross-correlation would have been 1, and there would clearly be no randomness. Even with back-to-back calls there is still some very minor residual correlation--but the requirement to "look random" is still met. – Reactant