Algorithm to generate Poisson and binomial random numbers?

For this and other numerical problems the bible is the numerical recipes book.

There's a free version for C here: http://www.nrbook.com/a/bookcpdf.php (plugin required)

Or you can see it on google books: 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

The C code should be very easy to transfer to Java.

This book is worth it's weight in gold for lots of numerical problems. On the above site you can also buy the latest version of the book.

Poisson distribution

Here's how Wikipedia says Knuth says to do 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.

In Java, that would be:

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

---

Binomial distribution

Going by chapter 10 of Non-Uniform Random Variate Generation (PDF) by Luc Devroye (which I found linked from the Wikipedia article) gives this:

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

---

Please note

Neither of these algorithms is optimal. The first is O(λ), the second is O(n). Depending on how large these values typically are, and how frequently you need to call the generators, you might need a better algorithm. The paper I link to above has more complicated algorithms that run in constant time, but I'll leave those implementations as an exercise for the reader. :)

Although the answer posted by Kip is perfectly valid for generating Poisson RVs with small rate of arrivals (lambda), the second algorithm posted in Wikipedia Generating Poisson Random variables is better for larger rate of arrivals due to numerical stability.

I faced problems during implementation of one of the projects requiring generation of Poisson RV with very high lambda due to this. So I suggest the other way.