Re: generate binomial distributed random numbers
- From: Robert Israel <israel@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx>
- Date: Thu, 10 May 2007 11:49:08 -0500
mueale5@xxxxxxxxxxxxx writes:
Hello!
Is there a very fast algorithm for generating binomial distributed
random numbers. Exactly:
I have an container with N balls (N1 white and N2 black ones).
How many black and white balls will I have in it after taking away
M balls and adding M new ones from an reservoir (with probability
p of adding a white one).
Of course, binomial distribution is only a special case for N=M.
I don't want to simulate every single event to take away a ball
or adding a new one. Is there an algorithm that works in constant
time - or at least in logarithmic time? For example with the help
of a lookup table.
In my program, N is around 2000 - but I want to calculate the new
number of balls billions of times.
Calculate the cumulative distribution function F(x) = Prob(X <= x)
for integers x from 0 to N. Let u be a random number with uniform
distribution in [0,1], and return x where F(x-1) < u <= F(x), found
by binary search.
--
Robert Israel israel@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
.
- Follow-Ups:
- Re: generate binomial distributed random numbers
- From: mueale5
- Re: generate binomial distributed random numbers
- References:
- generate binomial distributed random numbers
- From: mueale5
- generate binomial distributed random numbers
- Prev by Date: Direct external vs Cartesian
- Next by Date: Re: Towards a Formula for Primes
- Previous by thread: generate binomial distributed random numbers
- Next by thread: Re: generate binomial distributed random numbers
- Index(es):
Relevant Pages
|
