如何在Ruby中使用给定的离散分布获取随机数

Question

我正在编写与分布和随机投掷相关的大学作业。问题是：如何在Ruby中使用给定的离散分布获取随机数字。

更具体地说，对于像（0，P=1/2）；（1000，P=1/2）这样的普通离散分布，我可以编写以下函数：

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

第一个问题：是否有使用本地Random类编写它的方法？

第二个问题：如何处理像（0，P=1/5；2，P=2/5；1000，P=2/5）或更糟糕的分布（0，P=0.33；2，P=0.49；1000，P=0.18）这样的情况最好？

- ddnomad

---

https://dev59.com/nGox5IYBdhLWcg3w74u3 - 这是JavaScript相关的问题，但你应该能够理解。 - Sergio Tulentsev

请查看 AliasTable gem，以获得高效的通用解决方案。 - pjs

@pjs 谢谢！这就是应该可以解决的。 - ddnomad

Answer 1

我会选择类似于这样的东西。

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

为了检查分布是否正确，我运行了10000次，下面是结果：

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

---

@NeilSlater 是的，即使在O(1)的情况下也可以通过一些预处理来完成。当然。您可以使用额外的内存和O(1)的提取创建概率表。或者，在预处理概率值后，您可以使用O(log(n))的二分查找。 - fl00r

对于少量的备选项，这已经是最好的了。对于更多的结果，别名表在初始设置后具有恒定的时间行为。 - pjs

fl00r和@pjs，谢谢你们两个 :) 你们让我的一天变得美好。 - ddnomad