Probability selection algorithm

[Paul Rubin]

Paul Rubin <phr-n2003b at NOSPAMnightsong.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?

Whoops, no I didn't have it right.  Try this instead:

    def sprob(problist):
        remaining = 1.0
        for i in range(len(problist)):
            p = problist[i]
            if urand()*remaining < p:
                return i
            remaining -= p
        raise "shouldn't get here"

Again, this depends on your probability list adding up to 1.
Otherwise, add up the probabilities and scale everything appropriately.