If you have small p
values, you'll like this one better than the naive implementation you cited. It still loops, but the expected number of iterations is O(np)
so it's pretty fast for small p
values. If you're working with large p
values, replace p
with q = 1-p
and subtract the return value from n
. Clearly, it will be at its worst when p = q = 0.5
.
public static int getBinomial(int n, double p) {
double log_q = Math.log(1.0 - p);
int x = 0;
double sum = 0;
for(;;) {
sum += Math.log(Math.random()) / (n - x);
if(sum < log_q) {
return x;
}
x++;
}
}
The implementation is a variant of Luc Devroye's "Second Waiting Time Method" on page 522 of his text "Non-Uniform Random Variate Generation."
There are faster methods based on acceptance/rejection techniques, but they are substantially more complex to implement.