From: Daniel Carrera <dcarrera@...>
Date: 2003-04-19T01:55:39+09:00
Subject: Re: Biased weighted random?

Why not just use the same method I wrote before, (call it 
'weighted_random') but remove the entry that you don't want to repeat:

Let 'entries' be a hash whose keys are the items and whose values
are the weights.  Currently we can write:

item = weighted_random(entries)

And that gives you the proper weighted random.  Now, how about this:

# Pick 10 non-consecutively-repeating items with the appropriate
# probability distributions:

item_last = nil
prob_last = nil
item_curr = nil
prob_curr = nil
10.times do
    # delete the item we selected last time.
    entries.delete(item_curr)

    # Put back the item we selected the time before.
    entries[item_last] = prob_last unless item_last == nil

    # Get the new random item, and rotate.
    item_last, prob_last = item_curr.clone, prob_curr.clone
    item_curr = weighted_random(entries)
    prob_curr = entries[item_2]

    # Do something with item_2, prob_2
end

Now they should never repeat.

Does this look right?

Daniel.

On Fri, Apr 18, 2003 at 11:09:52PM +0900, Hal E. Fulton wrote:
> Hi, all...
> 
> Just thinking again about randomness.
> 
> A few weeks back I asked for a weighted random
> algorithm, and several people responded with
> nice ones.
> 
> Now I'm wanting to modify that problem.
> 
> Disclaimer: I'm not any kind of mathematician, 
> and I'm not sure that "biased" is the right
> term here.
> 
> Given a set of pairs [item,weight] select an
> item with likelihood corresponding to its
> weight... but with a twist.
> 
> Ensure that (while the overall statistical
> properties are as we expect), the likelihood
> of the same item appearing twice consecutively
> is relatively small. (As small as possible, 
> i.e., greater entropy or "variety" -- think of 
> "quotation of the day" or some such thing.)
> 
> Example:
> 
> Given a,5 b,4 c,2
> 
> I'd prefer the sequence
> 
>   a c a b a b c b a b a
> 
> to the sequence
> 
>   a a c b a b b a a b c
> 
> Of course, it's impossible to perfect this...
> if your weights are sufficiently skewed, there
> will always be some doubled items (or so my
> gut tells me).
> 
> Thoughts?
> 
> Hal
> 
> 

-- 
Daniel Carrera
Graduate Teaching Assistant.  Math Dept.
University of Maryland.  (301) 405-5137