From: "Mauricio Fernández" <batsman.geo@...>
Date: 2003-03-29T19:09:50+09:00
Subject: Re: Weighted random selection -- how would you do this?

On Sat, Mar 29, 2003 at 05:14:58PM +0900, Daniel Carrera wrote:
> On Sat, Mar 29, 2003 at 05:04:32PM +0900, Phil Tomson wrote:
> 
> > >event = events.each do |event, weight|
> > >	val -= weight; 
> > >	return event if val < 0
> > >end
> >
> > Hmmm.... Wouldn't this be biased by order?
> > 
> 
> Would it?
> This is my thinking, perhaps you can help me see if I'm wrong:
> 
> Example:
> Take two events with weights:
> event1 => 3
> event2 => 7
> 
> Pick a random number from 0 to 3+7=10
> There is a 30% chance that the number will be between 0 and 3 and there is 
> a 70% chance that the number will be between 3 and 10.
> 
> By selecting an event based on which range the random number lies in I 
> should get the biased probability that I desire.
> 
> I think I should replace the "val < 0" in my code by "val <= 0".
> Is this the error you were referring to?  Or is there a problem with my 
> reasoning?

Should be right w/ val <= 0, as the underlying distribution function is
defined as F(x) = p( X <= x ), or maybe not :-)

Just for fun, the mandatory inefficient one liner:
batsman@tux-chan:/tmp$ expand -t2 y.rb
events = {
        "event1" => 5,
        "event2" => 17,
        "event3" => 6,
        "event4" => 13
}

p((a = events.to_a.map{ |e,i| [e] * i }.flatten)[rand(a.size)])
batsman@tux-chan:/tmp$ ruby y.rb
"event2"

-- 
 _           _                             
| |__   __ _| |_ ___ _ __ ___   __ _ _ __  
| '_ \ / _` | __/ __| '_ ` _ \ / _` | '_ \ 
| |_) | (_| | |_\__ \ | | | | | (_| | | | |
|_.__/ \__,_|\__|___/_| |_| |_|\__,_|_| |_|
	Running Debian GNU/Linux Sid (unstable)
batsman dot geo at yahoo dot com

Why are there always boycotts?  Shouldn't there be girlcotts too?
	-- argon on #Linux