Generating binomial values

Thread view:

Daniel Dyer - 16 Sep 2006 17:06 GMT

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.

Signature

Daniel Dyer
http://www.dandyer.co.uk

Reply to this Message

Arne Vajhøj - 16 Sep 2006 17:27 GMT

> 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

Reply to this Message

Daniel Dyer - 16 Sep 2006 18:03 GMT

>> I'm looking for an algorithm for generating discrete random numbers
>> with a binomial distribution using a uniform RNG. Basically something
[quoted text clipped - 3 lines]
>
> 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.

Signature

Daniel Dyer
http://www.dandyer.co.uk

Reply to this Message

Arne Vajhøj - 17 Sep 2006 03:51 GMT

> 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

Reply to this Message

Alan Krueger - 17 Sep 2006 20:56 GMT

>> Thanks, this should be workable. Though if there are more efficient
>> approaches (for both Binomial and Poisson), I'd be interested to know.
[quoted text clipped - 5 lines]
> 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

Reply to this Message

Daniel Dyer - 17 Sep 2006 21:17 GMT

>>> Thanks, this should be workable. Though if there are more efficient
>>> approaches (for both Binomial and Poisson), I'd be interested to know.
[quoted text clipped - 3 lines]
>> than 25. For more it uses either Poisson approximation
>> or a "rejection method".

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.

Signature

Daniel Dyer
http://www.dandyer.co.uk

Reply to this Message

Daniel Dyer - 18 Sep 2006 20:48 GMT

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

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.

Signature

Daniel Dyer
http://www.dandyer.co.uk

Reply to this Message

Generating binomial values

Free Magazines