Re: Biased weighted random?

So, I think I'm close.

The repetition factor is *really* nice.  What is also nice is that I don't
have to keep track of running probabilities like I thought I would have to.

However, the distribution isn't *quite* right (these should all be about
1000):

  [973, 982, 988, 983, 954, 1003, 1031, 946, 970]

Not too bad, but look at some more:

  [972, 942, 962, 973, 979, 1010, 1027, 939, 988]
  [943, 961, 993, 977, 997, 1003, 1020, 990, 999]
  [960, 962, 939, 973, 990, 1002, 1035, 961, 972]
  [954, 924, 958, 983, 968, 1006, 1030, 960, 992]
  [990, 972, 969, 987, 954, 1007, 1028, 938, 968]

These are converging to the wrong numbers; bummer.  (Awfully tight
convergence, though, huh?  Nice...)

So what do I do?  I just weight each choice by the default weight multiplied
by how long it has been since we last saw this choice.  Oh, except that I
squared the default weights first.  (just seemed to work... <blush>)

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

Chris


-------------------------------


class PsychoRandom
  RESET_WEIGHT = 1  #  Pretty sure this should NOT be 0.

  def initialize weights
    if !weights.kind_of?(Array)
      #  Sorry, but these need to be ordered; no hashes.
      raise 'PsychoRandom needs array of [item, weight] pairs.'
    end
    @items = weights.map {|item,weight| item}
    @w = weights.map {|item,weight| weight**2}
    @n = @w.length
    @t = Array.new(@n,@n*1000)  #  Encourage everything to come up once at
the beginning.
  end

  def currentWeights
    (0...@n).map {|idx| @w[idx] * @t[idx]}
  end

  #  Tabby's lovely method.
  def getNextIndex
    total = 0
    pick = nil
    currentWeights.each_with_index do |weight, idx|
      total += weight
      pick = idx if rand(total) < weight
    end
    #  Modify times.
    @t.map! {|x| x+1}
    @t[pick] = RESET_WEIGHT
    #  Return chosen index.
    pick
  end

  def getNextItem
    @items[getNextIndex]
  end
end


weights = [
  ['a', 2],
  ['b', 1],
  ['c', 1],
  ['d', 3],
  ['e', 2],
  ['f', 7],
  ['g',11],
  ['h', 1],
  ['i', 3],
]
sumWeights = weights.inject(0) {|sum,pair| sum + pair[1]}

pr = PsychoRandom.new weights

# 1000.times {print pr.getNextIndex, ' '}
# puts
# puts

timesSelected = weights.map {0}
(sumWeights*1000).times {timesSelected[pr.getNextIndex] += 1}

for i in 0...(timesSelected.length)
  timesSelected[i] /= weights[i][1]
end

p timesSelected