Алгоритм для генерации Poisson и биномиальных случайных чисел?
Используйте регулярное выражение непотребления.
типичное (т.е. Perl/Java) нотация:
(?= expr)
Это означает "соответствие expr, но после этого продолжите соответствовать в исходном матч-пойнте".
можно сделать столько из них, сколько Вы хотите, и это будет "и". Пример:
(?=match this expression)(?=match this too)(?=oh, and this)
можно даже добавить группы получения в выражениях непотребления, если необходимо сохранить некоторые данные там.
3 ответа
Распределение Пуассона
Вот , как Википедия говорит, что Кнут говорит делать it :
init:
Let L ← e^(−λ), k ← 0 and p ← 1.
do:
k ← k + 1.
Generate uniform random number u in [0,1] and let p ← p × u.
while p > L.
return k − 1.
В Java это будет:
public static int getPoisson(double lambda) {
double L = Math.exp(-lambda);
double p = 1.0;
int k = 0;
do {
k++;
p *= Math.random();
} while (p > L);
return k - 1;
}
Биномиальное распределение
В соответствии с главой 10 из Генерация неравномерной случайной величины (PDF) Люка Девроя ( который я нашел по ссылке из статьи в Википедии ) дает следующее:
public static int getBinomial(int n, double p) {
int x = 0;
for(int i = 0; i < n; i++) {
if(Math.random() < p)
x++;
}
return x;
}
Обратите внимание на
Ни один из этих алгоритмов не является оптимальным. Первый - O (λ), второй - O (n). В зависимости от того, насколько велики эти значения и как часто вам нужно вызывать генераторы, вам может потребоваться лучший алгоритм. В документе, на который я ссылаюсь выше, есть более сложные алгоритмы, которые выполняются в постоянное время, но я оставлю эти реализации в качестве упражнения для читателя. :)
Для этой и других числовых задач Библия - это книга числовых рецептов.
Бесплатная версия для C находится здесь: http://www.nrbook.com/a/ bookcpdf.php (требуется плагин)
Или вы можете увидеть его в книгах Google: http://books.google.co.uk/books?id=4t-sybVuoqoC&lpg=PP1&ots=5IhMINLhHo&dq=numerical % 20recipes% 20in% 20c & pg = PP1 # v = onepage & q = & f = false
Код C должен быть очень легко перенесен на Java.
Эта книга на вес золота при решении множества числовых задач. На указанном выше сайте вы также можете купить последнюю версию книги.
Существует несколько реализаций от CERN в следующей библиотеке (код Java):
http://acs.lbl.gov/~hoschek/Colt/
относительно биномиальных случайных чисел , Он основан на бумаге с 1988 года «Биномиальная генерация случайных варинт», которые я рекомендую вам, поскольку они используют оптимизированный алгоритм.
С уважением