Re: Is there a better way to simulate randomly choosing from a weighted set?

On Mon, 27 Feb 2006 01:34:00 -0800, yay_frogs wrote:

[I originally posted this to comp.lang.c++ since that is the language I'm
working in, but then I realized that my problem isn't language specific
and this would probably be a better group.]

Here is my problem: suppose there are, say, five events with these
probabilities:

event1 0.7
event2 0.1
event3 0.1
event4 0.05
event5 0.05

Note that sum of the probabilities is 1.0. I would like a function that
simulates these events and returns an int to indicate which event
occurred: the function should statistically return 1 about 70% of the
time, 2 about 10% of the time, and so on.

I have figured out a way to do this, but I suspect my way is suboptimal.
<cumulative prob. method snipped>
So is there a better way?

Sometimes a crude method can help. You can allocate a char or int array
of size N and set N*p1 of them E1, n*p2 of them to E2 and so on. Pick a
number between 0 and N-1 and use the event number you find in the array.
Even a 1000 elements is quite small for today's computers. You can also
adjust this method to give you exact results by keeping a count of
each event and setting some reserved elements to event numbers that are
"falling behind" the expected proportions.

--
Ben.
.