5

I'm coding my university assignment that is somewhat connected with distributions and random roll stuff. So the question is: how to get a random number with a given discrete distribution in Ruby.

To be more specific: in trivial example with normal discrete distribution like (0 with P=1/2; 1000 with P=1/2) I could write such a function:

 def chooseNumber(a,b)
  rval = Random.rand(0..1)
  return a if rval == 0
  return b
 end

First question: is there any way to write it using native Random class?

Second question: what is the best way to deal with distributions like (0 with P=1/5; 2 with P=2/5; 1000 with P=2/5) or even worse (0 with P=0,33; 2 with P=0,49; 1000 with P=0,18)?

ddnomad
  • 373
  • 3
  • 15

1 Answers1

5

I would go with something like this

def pick_with_distribution(distributions)
  r = rand
  distributions.detect{ |k, d| r -= d; r < 0 }.first
end

distributions = { 0 => 0.33, 2 => 0.49, 1000 => 0.18 }
pick_with_distribution(distributions)
#=> 0

To check if distribution is correct, I run it 10000 times, here is the result:

10000.times.inject({}) do |h, _| 
  r = pick_with_distribution(distributions)
  h[r] ||= 0
  h[r] += 1
  h
end
#=> {0=>3231, 1000=>1860, 2=>4909}
fl00r
  • 82,987
  • 33
  • 217
  • 237
  • @NeilSlater yes, it could be done even with O(1) with some preprocessing. sure. You could create probability table with extra memory and O(1) fetch. Or you could use binary search in O(log(n)) after preprocessing probability values. – fl00r Nov 04 '15 at 16:24
  • @NeilSlater for a small number of alternatives this is about as good as it gets. For larger numbers of outcomes, [alias tables](https://en.wikipedia.org/wiki/Alias_method) have constant time behavior after the initial setup. – pjs Nov 04 '15 at 16:25
  • fl00r and @pjs thanks you both :) you've made my day – ddnomad Nov 04 '15 at 16:29