概率可调的随机算法

Question

我正在寻找一种算法（无论是什么编程语言，也许是伪代码？），您可以在其中获得具有不同概率的随机数。

例如：

A random Generator, which simulates a dice where the chance for a '6' is 50% and for the other 5 numbers it's 10%.

算法应该是可扩展的，因为这是我的确切问题：

I have a array (or database) of elements, from which i want to select 1 random element. But each element should have a different probability to be selected. So my idea is that every element get a number. And this number divided by the sum of all numbers results the chance for the number to be randomly selected.

有人知道解决这个问题的好的编程语言（或库）吗？最好的解决方案是一个很好的 SQL 查询，它提供 1 个随机条目。但我也会对其他编程语言的每一个提示或尝试感到满意。

Answer 1

实现它的一个简单算法是：

创建一个辅助数组，其中 sum[i] = p1 + p2 + ... + pi。这只完成一次。
画数时，画一个r在[0,sum[n])上均匀分布的数，二分查找第一个比均匀分布高的数分布式随机数。可以使用 binary search 有效地完成。

不难看出r落在一定区间[sum[i-1],sum[i])的概率的确是sum[i]-sum[i-1] = pi
（在上面，我们认为sum[-1]=0，为了完整性）

对于您的多维数据集示例：

你有：

p1=p2=....=p5 = 0.1
p6 = 0.5

首先计算sum数组：

sum[1] = 0.1
sum[2] = 0.2
sum[3] = 0.3
sum[4] = 0.4
sum[5] = 0.5
sum[6] = 1

然后，每次需要抽取一个数：在[0,1)中随机抽取一个数r，选择最接近的数，例如：

r1 = 0.45 -> element = 4
r2 = 0.8 -> element = 6
r3 = 0.1 -> element = 2
r4 = 0.09 -> element = 1

Answer 2

另一个答案。你的例子是百分比，所以设置一个有 100 个槽的数组。 6 是 50%，所以将 6 放在 50 个插槽中。 1 到 5 各占 10%，因此将 1 个放入 10 个槽中，将 2 个放入 10 个槽中，依此类推，直到填满阵列中的所有 100 个槽。现在根据您使用的语言，使用 [0, 99] 或 [1, 100] 中的均匀分布随机选择一个插槽。

所选数组槽的内容会给你想要的分配。

ETA：再想一想，您实际上并不需要数组，只需使用累积概率来模拟数组即可：

r = rand(100) // In range 0 -> 99 inclusive.

if (r < 50) return 6;  // Up to 50% returns a 6.
if (r < 60) return 1;  // Between 50% and 60% returns a 1.
if (r < 70) return 2;  // Between 60% and 70% returns a 2.
etc.

您已经知道什么号码在什么插槽中，所以只需使用累积概率来选择一个虚拟插槽：50； 50 + 10; 50 + 10 + 10； ...

注意边缘情况以及您的 RNG 是 0 -> 99 还是 1 -> 100。

概率可调的随机算法

Random Algorithm with adjustable probability

random

algorithm