Generating binomial values

[Daniel Dyer]

I'm looking for an algorithm for generating discrete random numbers with a
binomial distribution using a uniform RNG. Basically something like the
Box-Muller algorithm but for binomials. I know I can use a normal
distribution (and hence Box-Muller) as an approximation, I was just
wondering if there is a better approach.

I guess all this stuff is in Knuth vol. 2, but I don't have a copy here.

Thanks,

Dan.

 

[Guest]

I'm looking for an algorithm for generating discrete random numbers with
a binomial distribution using a uniform RNG. Basically something like
the Box-Muller algorithm but for binomials. I know I can use a normal
distribution (and hence Box-Muller) as an approximation, I was just
wondering if there is a better approach.

What about the obvious:

n=0, for loop with N iterations, for each iteration
get a random number between 0.0 and 1.0, if it
it greater than p then increment n, return n

(if N is big then approximate with other distribution)

?

Arne

 

[Daniel Dyer]

What about the obvious:

I'm statistically-challenged

n=0, for loop with N iterations, for each iteration
get a random number between 0.0 and 1.0, if it
it greater than p then increment n, return n

You're right, that should have been obvious since I'm already using a more
complicated variant of the same approach to generate Poisson values
(though I borrowed the code rather than wrote it myself).

(if N is big then approximate with other distribution)

?

Arne

Thanks, this should be workable. Though if there are more efficient
approaches (for both Binomial and Poisson), I'd be interested to know.

Dan.

 

[Guest]

Thanks, this should be workable. Though if there are more efficient
approaches (for both Binomial and Poisson), I'd be interested to know.

Knuth is (as usual) above my abilities.

Numerical Recipes in C has a function (page 290)
which basically use the method I proposed for less
than 25. For more it uses either Poisson approximation
or a "rejection method".

Arne

 

[Alan Krueger]

Knuth is (as usual) above my abilities.

Numerical Recipes in C has a function (page 290)
which basically use the method I proposed for less
than 25. For more it uses either Poisson approximation
or a "rejection method".

For those who don't own it, there appears to be a free, online version
of the book.

http://www.nrbook.com/a/bookcpdf.html

 

[Daniel Dyer]

Arne, thanks for the suggestion. That implementation looks to be as good
as I will find.

For those who don't own it, there appears to be a free, online version
of the book.

http://www.nrbook.com/a/bookcpdf.html

Alan, thanks, that's a very useful link to make a note of.

Dan.

 

[Daniel Dyer]

Knuth is (as usual) above my abilities.

I had the opportunity to look at a copy today. It has about 40 pages of
dense material on the subject of non-uniform probability distributions.
You are right, it's not easy going. I didn't attempt to follow the maths,
but I was able to ascertain that, for binomials, his advice is to use the
method you suggested for small values of n and to use a beta distribution
for larger values.

Dan.