C #: численный алгоритм для генерации чисел из биномиального распределения - PullRequest
Новая
       55

C #: численный алгоритм для генерации чисел из биномиального распределения

8 голосов
/ 13 ноября 2009

Мне нужно сгенерировать случайные числа из биномиального (n, p) распределения.

Биноминальная (n, p) случайная величина - это сумма n равномерных переменных, которые принимают 1 с вероятностью p. В псевдокоде x=0; for(i=0; i<n; ++i) x+=(rand()<p?1:0); сгенерирует бином (n, p).

Мне нужно сгенерировать это для малых и действительно больших n, например, n = 10 ^ 6 и p = 0,02. Есть ли быстрый численный алгоритм для его генерации?

РЕДАКТИРОВАТЬ -

Прямо сейчас это то, что я имею в качестве приближения (наряду с функциями для точного распределения Пуассона и нормального распределения) - 

    public long Binomial(long n, double p) {
        // As of now it is an approximation
        if (n < 1000) {
            long result = 0;
            for (int i=0; i<n; ++i)
                if (random.NextDouble() < p) result++;
            return result;
        }
        if (n * p < 10) return Poisson(n * p);
        else if (n * (1 - p) < 10) return n - Poisson(n * p);
        else {
            long v = (long)(0.5 + nextNormal(n * p, Math.Sqrt(n * p * (1 - p))));
            if (v < 0) v = 0;
            else if (v > n) v = n;
            return v;
        }
    }

Ответы [ 3 ]

5 голосов
/ 19 ноября 2009

Другим вариантом будет выборка из Normal или Poisson, как вы делаете, а затем добавьте шаг Metropolis-Hastings , чтобы принять или отклонить ваш образец. Если вы принимаете, что все готово, если вы отклоняете, вы должны полностью повторить повторную выборку. Я предполагаю, что из-за того, что аппроксимация настолько близка, вы почти всегда получаете шаг принятия, время от времени вы можете отказаться.

Также В книге Люка Деврой есть несколько отличных алгоритмов для биномиальной выборки.

PS Если у вас получится хороший алгоритм; Не могли бы вы поделиться им на Math.Net Numerics ?

4 голосов
/ 13 ноября 2009

Если вы готовы заплатить, взгляните на NMath от Centerspace.

В противном случае код C, используемый программой Stats R, равен здесь и должен быть простым для переноса на C #.

РЕДАКТИРОВАТЬ: Есть детали (в том числе код) о создании метода для этого на p178 из Практические численные методы с C # Джеком Сюй.

ДРУГОЕ РЕДАКТИРОВАНИЕ: Бесплатная библиотека C # , которая делает то, что вы хотите.

3 голосов
/ 13 ноября 2009

Нет очевидного способа сделать это эффективно. Для малого n вы можете просто использовать формулу для вычисления обратного PDF. Для больших n вам, вероятно, лучше использовать одно из приближений к другим распределениям , которые легче вычислить.

...