From: "Hal E. Fulton" <hal9000@...>
Date: 2003-04-19T03:11:43+09:00
Subject: Re: Biased weighted random?

----- Original Message -----
From: "Chris Pine" <nemo@hellotree.com>
To: "ruby-talk ML" <ruby-talk@ruby-lang.org>
Sent: Friday, April 18, 2003 12:07 PM
Subject: Re: Biased weighted random?


> ----- Original Message -----
> From: "Daniel Carrera" <dcarrera@math.umd.edu>
>
> Now they should never repeat.
>
> Does this look right?
> ----------------------------
>
> Nope.  :)
>
> See my earlier response.  You met the "does not repeat" requirement, but
> your distribution probabilities have been changed.

OK, it fails... but not miserably so.

I've taken Daniel's idea and simplified it a little.

Here's the code and the output. Notice how the ordering
requirement is met perfectly, but the frequencies are
naturally not correct then.

But for a "psychological" selection algorithm as Chris
(?) called it, this might be reasonable.

Then again, there's probably a way to adjust the weights
dynamically so that things come out right.

Actually, this one is probably good enough for my own
purposes. But I'm still interested in the theory, so if
anyone has any more insights, I'm curious about them.

Cheers,
Hal


#---------------------------------
def random_weighted(items)
  total = 0
  pick = nil
  items.each do |item, weight|
    pick = item if rand(total += weight) < weight
  end
  pick
end

def try(trials)
  entries = [ ["a", 8], ["b",6], ["c",4], ["d",2] ]
  freq = {"a" => 0, "b" => 0, "c" => 0, "d" => 0}

  last = nil
  print "\n" if trials < 100
  trials.times do
    last = entries.find {|x| x[0]==last}
    list = (entries-[last])
    item = random_weighted(list)
    last = item
    print item if trials < 100
    freq[item] += 1
  end
  print "\n" if trials < 100
  "#{'%6d' % trials}: #{freq.inspect}"
end


puts try(20)
puts try(40)
puts try(80)
puts try(200)
puts try(2000)
puts try(20000)
puts try(200000)
# --------------------------------


And the output...


acbababcadbabacacaba
    20: {"a"=>9, "b"=>6, "c"=>4, "d"=>1}

babcdcacacabcdadcbcadbacbacabdabcadcbaba
    40: {"a"=>13, "b"=>10, "c"=>11, "d"=>6}

bdabcadacbcacabcdbacbdabacabadbababcabdadbcabdabacdadcababdbacbdbcbabacacbac
abab
    80: {"a"=>27, "b"=>25, "c"=>16, "d"=>12}
   200: {"a"=>73, "b"=>61, "c"=>41, "d"=>25}
  2000: {"a"=>700, "b"=>608, "c"=>449, "d"=>243}
 20000: {"a"=>6842, "b"=>6064, "c"=>4492, "d"=>2602}
200000: {"a"=>68441, "b"=>60009, "c"=>45798, "d"=>25752}