Probability selection algorithm

[Paul Rubin]

Dennis Lee Bieber <wlfraed at ix.netcom.com> writes:
> > Try something like:
> > 
> >     remaining = 1.0
> >     for i range(len(problist)):
> >        if urand() < remaining:
> >          selected = i
> >        remaining -= problist[i]
> > 
> > where urand returns a random number between 0.0 and 1.0 and
> > problist is your list of probabilities.  "selected" is set to
> > the appropriate randomly chosen index.
> > 
> > Do I have that right?
> 
>         I suspect you don't want to call "urand()" on each pass --
> once at the beginning, then do the loop.

I really meant to call it on each pass, but the algorithm is slightly
wrong.  See the followup post.  But actually, you're right--if you
know the probabilities in advance, you can call urand just once:

    t = 0.0
    r = urand()
    for i in range(len(problist)):
      t += problist[i]
      if t > r:
         break

That's a lot nicer.  The other scheme was adapted from a more general
method for when you don't know the probabilities or the size of the
list in advance.