从集合中进行概率选择

Question

假设我想随机选择0到30之间的数字n,其中分布是任意的,而不是统一的.每个数字具有相应的权重P(n):P(0)= 5,P(1)= 1,P(2)= 30,P(3)= 25,依此类推.如何从该集合中随机选择,以便选择数字的概率与其权重成正比？

什么是这种随机选择甚至被称为？

我可以看到实现它的一种方法:

1. 制作查找表V,其中V(n)= V(n-1)+ P(n); 基本情况V(0)= P(0).
2. 生成一个随机数X,其均匀分布在0和最大值V之间.
3. 找到n的最小值,使得V(n)> X.

这样的东西已经在库中实现了吗？(使用Perl.)

Answer 1

这实际上是一个非常受欢迎的问题,称为加权随机选择(或有时加权随机选择).这是一篇关于它的完整文章.