Работа с нормальным (гауссовым) распределением

Question

Я в основном stucked на довольно простую задачу:

Toss N монет и обнаружить, сколько из них участки головы

производительность Решение не должно зависеть от N, поэтому мы не можем просто позвонить Math.random() < 0.5 N раз. Очевидно, что для спасения есть распределение Гаусса.

Я использовал метод Бокса-Мюллера для него:

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); 
} 

Математика говорит, что означают из N бросков монеты является N/2 и дисперсия является N/4

Затем я сделал тест, который бросает N монет М раз, давая минимальное, максимальное и среднее количество головок.

Я сравнивал результаты наивного подхода (Math.random() много раз) и подход Гаусса Бокса-Мюллера.

Существует типичный выход тестов:

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 

Как мы можем видеть на N = 1000 он подходит почти идеально.

BUT, on N = 10 Box-Muller сходит с ума: он позволяет получить такие результаты тестов, где я могу получить (довольно редко, но это возможно) 11.17 головок из 10 монетных монет! :)

Несомненно, я делаю что-то неправильно. Но что именно?

Существует source of test, и ссылка на launch it

Обновлено x2:, кажется, раньше я не описал проблему наилучшим образом. Существует общая версия этого:

Как получить выборочные среднее из N однородных случайных величины (либо дискретных или непрерывных) в амортизационном постоянная время. Гауссовское распределение эффективно для больших N, но есть ли способ заставить его работать на небольших N? Или на каком именно N решение должно переключиться с гауссовского метода на какой-нибудь другой (для простого сравнения).

Answer 1

Математика говорит, что среднее значение N бросков монеты является N/2 и дисперсия N/4.

Math только говорит, что если это честная монета. И нет способа решения не зависит от N.

Предполагая, что все швы не зависят друг от друга, для точного поведения используйте биномиальное распределение, а не нормальное распределение.Binomial имеет два параметра: N - количество монетных бросков, p - вероятность получения голов (или хвостов, если хотите). В псевдокоде ...

function binomial(n, p) { 
    counter = 0 
    successes = 0 
    while counter < n { 
    if Math.random() <= p 
     successes += 1 
    counter += 1 
    } 
    return successes 
} 

Есть более быстрые алгоритмы для больших N, но это просто и математически правильно.

Answer 2

Основываясь на том, что обсуждалось в approved answer, я подошел к этому конкретному решению.

Есть правильное правило n*p >= 10 and n*(1-p) >= 10, но позволяет определить более строгий.

Прежде всего, Бокс-Мюллер будет сложно ограниченно на [-6,6], для обеспечения надлежащего результата (640 кБ должны ... я имею в виду, 6 сигмы должна быть достаточно для всех).

Затем, используя 6 постоянный, мы заявляем, что для того, чтобы Box-Muller дал достоверные результаты, Math.sqrt(variance) * 6 не должен превышать mean. После использования N/2 и N/4 как mean и variance соответственно, и сокращения, мы в конечном итоге с этим:

Math.sqrt(N) * 6 <= N 

N >= 36 

Хотя это условие истинно, то можно смело использовать ограничен Box-Muller Гаусса. При любом более низком размере образца придерживайтесь решения Binomial.

Проверено это правило статистически - при относительно большом количестве (10 миллионов) тестов минимальное значение перестает выпадать из границ от размера выборки 32 и выше.