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

Question

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

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

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

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

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

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

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

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

Answer 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.

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

Answer 3

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

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

Answer 4

Вы можете добавить это в build.gradle

implementation 'org.kie.modules:org-apache-commons-math:6.5.0.Final'

и использовать класс PoissonDistribution подробнее для класса PoissonDistribution

Answer 5

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

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

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

Привет