Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

NetLogo, weighted random draw from a list: how to use rnd-extension?

Tags:

netlogo

I have a list in NetLogo with values and a list of probabilities for each value. Now I want to draw a random value based on its probability (weighted random draw). I thought of using the Rnd extension, but I cant quite figure out how to get the weights right, please help

set values [1 2 3]
set probabilities [0.2 0.3 0.5]

set state ( rnd:weighted-one-of agentset reporter-task )
like image 230
Madelon Avatar asked Mar 24 '14 16:03

Madelon


2 Answers

If you want to use any probabilities, not just those that add up to one, you can do this without the rnd extension. For instance if you wanted to pick candidate 1, 2, or 3 based on the number of votes:

to-report weighted-rand 
  let values [1 2 3]
  ;let probabilities [0.2 0.3 0.5]
  let votes [5 7 9]

  ; calculate the cumulative probability list
  let cum reduce [
    lput (?2 + (ifelse-value (empty? ?1) [0] [last ?1])) ?1
  ] (fput [] votes)

  ; Roll a uniform random number weighted by the cumulative probability vector
  let x random-float sum votes
  let j  -1
  let found false
  while [(not found) and (j < (length cum))]
  [
    set j (j + 1)
    if (x <= item j cum) [set found true]
  ]

  report item j values
end

This is a little complex (especially the tricky use of reduce) but what it basically does is create a cumulative sum of the probabilities (votes) and then find the place in that list where the uniform random value fell. Then it returns the item from the list of values corresponding to the place it found.

like image 96
theoden Avatar answered Jan 01 '23 12:01

theoden


If you want/need to use two separate lists for your values and probabilities, the way to do it is to have the extension pick an index and use this index to access both the probability in the reporter passed to rnd:weighted-one-of and, once it is chosen, the value in your list. That's example1 in the code below.

The extension is easier to work with, however, if you can put both your values and your probabilities in the same list. This is done by building a list of "pairs" (i.e., a list of lists with two items in each sublist). When you have that, you can use the second item of the pair (item 1) in the reporter and set your state using the first item of the pair (item 0). example2 shows how to do this.

extensions [ rnd ]

to example1
  let values [1 2 3]
  let probabilities [0.2 0.3 0.5]
  let indices n-values length values [ ? ]
  let index rnd:weighted-one-of indices [ item ? probabilities ]
  let state item index values
end

to example2
  let pairs [[1 0.2] [2 0.3] [3 0.5]]
  let state item 0 rnd:weighted-one-of pairs [ item 1 ? ]
end

Edit:

As mentioned by Seth in the comments, you can construct your list of pairs from the two separate lists with (map list values probabilities). He also mentions that the code might be "clearer with first and last instead of item 0 and item 1."

example3 integrates both suggestions:

to example3
  let values [1 2 3]
  let probabilities [0.2 0.3 0.5]
  let pairs (map list values probabilities)
  let state first rnd:weighted-one-of pairs [ last ? ]
end
like image 37
Nicolas Payette Avatar answered Jan 01 '23 12:01

Nicolas Payette