From: "Hal E. Fulton" <hal9000@...>
Date: 2003-04-18T23:09:52+09:00
Subject: Biased weighted random?

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