vendredi 30 septembre 2016

Dealing with normal (Gaussian) distribution

I basically stucked on rather simple problem:

Toss N coins and discover, how many of them land heads

Solution performance must not depend on N, so we can't just call Math.random() < 0.5 N times. Obviously, there is Gaussian distribution to the rescue.

I used Box-Muller method for it:

function gaussian_random(mean, variance) {
  var s;
  var x;
  var y;
  do {
    x = Math.random() * 2.0 - 1.0;
    y = Math.random() * 2.0 - 1.0;
    s = Math.pow(x, 2) + Math.pow(y, 2);
  } while ( (s > 1) || (s == 0) );

  var gaussian = x * Math.sqrt(-2*Math.log(s)/s);
  return mean + gaussian * Math.sqrt(variance);
}

Math says, that mean of N coin tosses is N/2 and variance is N/4

Then, I made test, which tosses N coins M times, giving Minimum, Maximum, and Average number of heads.

I compared results of naive approach (Math.random() many times) and Gaussian Box-Muller approach.

There is typical output of tests:

Toss 1000 coins, 10000 times
Straight method: 
Elapsed time: 127.330 ms
Minimum: 434
Maximum: 558
Average: 500.0306
Box-Muller method: 
Elapsed time: 2.575 ms
Minimum: 438.0112461962819
Maximum: 562.9739632480057
Average: 499.96195358695064

Toss 10 coins, 10000 times
Straight method: 
Elapsed time: 2.100 ms
Minimum: 0
Maximum: 10
Average: 5.024
Box-Muller method: 
Elapsed time: 2.270 ms
Minimum: -1.1728354576573263
Maximum: 11.169478925333504
Average: 5.010078819562535

As we can see on N = 1000 it fits almost perfectly.

BUT, on N = 10 Box-Muller goes crazy: it allows such tests outcomes, where i can get (quite rarely, but it is possible) 11.17 heads from 10 coin tosses! :)

No doubt, i am doing something wrong. But what exactly?

There is source of test, and link to launch it




Aucun commentaire:

Enregistrer un commentaire