Подтвердить что ты не робот

Алгоритм генерации пуассоновских и биномиальных случайных чисел?

Я смотрю вокруг, но я не уверен, как это сделать.

я нашел эту страницу, которая в последнем абзаце гласит:

Простой генератор случайных чисел, взятый из распределения Пуассона, получается с использованием этого простого рецепта: если x 1, x 2,... является последовательность случайных чисел с равномерным распределением между нулем и одним, k - первое целое число, для которого произведение x 1 · x 2 ·... · x k +1 < е -λ

Я нашел другую страницу, описывающую, как генерировать биномиальные числа, но я думаю, что он использует приближение генерации пуассона, я помогу мне.

Например, рассмотрим биномиальные случайные числа. Биномиальное случайное число - это количество головок в N тонах монеты с вероятностью p головок при любом одиночном броске. Если вы генерируете N равномерных случайных чисел на интервале (0,1) и считаете число меньше p, то счетчик является биномиальным случайным числом с параметрами N и p.

Я знаю, что есть библиотеки для этого, но я не могу их использовать, только стандартные унифицированные генераторы, предоставляемые языком (в данном случае java).

4b9b3361

ОТВЕТЫ

Ответ 1

Распределение Пуассона

Здесь как Википедия говорит, что Кнут говорит, чтобы сделать это:

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) Люка Devroye (которое я нашел связанный из статьи в Википедии):

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). В зависимости от того, насколько велики эти значения, и как часто вам приходится обращаться к генераторам, вам может потребоваться лучший алгоритм. В документе, который я ссылаюсь на выше, есть более сложные алгоритмы, которые выполняются в постоянное время, но я оставлю эти реализации в качестве упражнения для читателя.:)

Ответ 2

Для этой и других числовых задач библия - это книга с числовыми рецептами.

Здесь есть бесплатная версия для 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.

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

Ответ 3

Несмотря на то, что ответ, опубликованный Kip, совершенно применим для генерации пуассоновских RV с малой скоростью прихода (лямбда), второй алгоритм, размещенный в Википедии Генерация пуассоновских случайных переменных лучше для большего количества прибытий из-за численной стабильности.

У меня возникли проблемы при реализации одного из проектов, требующих генерации Пуассона RV с очень высокой лямбдой из-за этого. Поэтому я предлагаю другой способ.

Ответ 4

Существует несколько реализаций из CERN в следующей библиотеке (код Java):

http://acs.lbl.gov/~hoschek/colt/

В отношении биномиальных случайных чисел он основан на статье 1988 года "Биномиальное случайное изменение вариации", которую я рекомендую вам, поскольку они используют оптимизированный алгоритм.

Привет