Algorithmus zur Erzeugung von Poisson- und Binomial -Zufallszahlen?

Question

Ich habe mich umgesehen, aber ich bin mir nicht sicher, wie ich es machen soll.

Ich habe gefunden diese Seite Was im letzten Absatz sagt:

Ein einfacher Generator für Zufallszahlen einer Poisson -Verteilung wird unter Verwendung dieses einfachen Rezepts erhalten: wenn x₁, x₂, ... ist eine Folge von Zufallszahlen mit gleichmäßiger Verteilung zwischen Null und eins, k ist die erste Ganzzahl, für die das Produkt x₁ · x₂ · ... · x_K+1 <e^-λ

Ich habe gefunden eine andere Seite Beschreibe, wie man Binomialzahlen erzeugt, aber ich denke, es verwendet eine Annäherung an die Poisson -Generation, was mir nicht hilft.

Betrachten Sie beispielsweise Binomial -Zufallszahlen. Eine Binomial -Zufallszahl ist die Anzahl der Köpfe in n Wurfs einer Münze mit Wahrscheinlichkeit p von einem Köpfe auf jedem einzelnen Wurf. Wenn Sie n gleichmäßige Zufallszahlen im Intervall (0,1) n generieren und die Zahl weniger als P zählen, ist die Anzahl eine Binomial -Zufallszahl mit den Parametern n und p.

Ich weiß, dass es Bibliotheken gibt, die es tun, aber ich kann sie nicht verwenden, nur die von der Sprache bereitgestellten Standard -Uniformgeneratoren (Java, in diesem Fall).

Answer 1

Poisson-Verteilung

Hier ist Wie Wikipedia sagt, dass Knuth sagt, dass es dies tun soll:

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.

In Java wäre das:

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

---

Binomiale Verteilung

Gehen von Kapitel 10 von Ungleichmäßige zufällige Variationserzeugung (PDF) von Luc Devroye (von dem ich festgestellt habe Der Wikipedia -Artikel) gibt dies:

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

---

bitte beachten Sie

Keiner dieser Algorithmen ist optimal. Das erste ist o (λ), das zweite ist o (n). Abhängig davon, wie groß diese Werte normalerweise sind und wie häufig Sie die Generatoren aufrufen müssen, benötigen Sie möglicherweise einen besseren Algorithmus. Das Papier, mit dem ich oben verlinke, hat kompliziertere Algorithmen, die in ständiger Zeit ausgeführt werden, aber ich werde diese Implementierungen als Übung für den Leser überlassen. :)

Answer 2

Für diese und andere numerische Probleme ist die Bibel das numerische Rezeptebuch.

Hier gibt es eine kostenlose Version für C: http://www.nrbook.com/a/bookcpdf.php (Plugin erforderlich)

Oder Sie können es in Google Books sehen: http://books.google.co.uk/books?id=4t-Sybvuoqoc&lpg=pp1&otots=5iHminlhho&dq=numerical%20Recipes%20in%20c&pg=pp1#v=onepage&q=&f=false

Der C -Code sollte sehr einfach auf Java übertragen sein.

Dieses Buch lohnt sich in Gold für viele numerische Probleme. Auf der obigen Website können Sie auch die neueste Version des Buches kaufen.

Answer 3

Obwohl die von KIP veröffentlichte Antwort perfekt für die Generierung von Poisson -Wohnmobilen mit geringer Ankünfte (Lambda) gültig ist, ist der zweite Algorithmus, der in Wikipedia veröffentlicht wurde Erzeugen von Poisson -Zufallsvariablen ist für eine größere Ankünfte aufgrund der numerischen Stabilität besser.

Ich hatte Probleme während der Umsetzung eines der Projekte, bei denen der Poisson -RV mit sehr hoher Lambda erzeugt wurde. Also schlage ich den anderen Weg vor.

Answer 4

In der folgenden Bibliothek gibt es mehrere Implementierungen von CERN (Java -Code):

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

In Bezug auf binomiale Zufallszahlen basiert es auf dem Papier von 1988 "Binomial Random Variate Generation", den ich Ihnen empfehle, da sie einen optimierten Algorithmus verwenden.

Grüße

Answer 5

Sie können dies zum Build.gradle hinzufügen

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

und Klasse verwenden Poisson-Verteilung Weitere Details für die Klassenpoissonverteilung