From: Chris Pine <nemo@...>
Date: 2003-04-20T23:53:23+09:00
Subject: Re: Biased weighted random?

----- Original Message -----
From: "Chris Pine" <nemo@hellotree.com>

So it's really close... any ideas?  And why the $@#! am I squaring the
weights??
----------------------------

Well, I think I figured out the squaring.  Basically, I *shouldn't* be
taking the square numbers, I should be taking the triangular numbers.  So
change

  weight**2

to

  (weight * weight + weight) /2

It's still not perfect, though.  It's *really* close, however.  (It slightly
favors rare events.)

I must confess that it does allow repetition of an event; however, with a
large selection of events (20 or more, I'd say), it is ***profoundly***
rare.  On the upside, this algorithm works with *every* set of weights, even
something like (1, 20).  (Of course, you can't have both.)

So why the triangular numbers?  Because when you consider something with
weight 1 five times in a row, it's time-of-last-choosing (int the
poorly-named `t' array) goes from 1 to 5.  So it was given 1+2+3+4+5=15
chances.  If you have something else which you want to have come up 5 times
as often, it needs a weight of 15 to compete with that... roughly.

So I'm quite pleased with this algorithm with a large number of objects (or,
I should say, with the largest weight being as small a percentage as
possible of the sum of all weights), which is what *I* want to use it for,
anyway.  Could it be improved for smaller numbers of weights?  Perhaps by
squaring the times in `t' and modifying the weights somehow??  I don't know.

Chris