8

如何在 A = 1 和 B = 10 之间生成一个随机数，其中每个数字都有不同的概率？

示例：数字/概率

1 - 20%

2 - 20%

3 - 10%

4 - 5%

5 - 5%

...等等。

我知道一些硬编码的变通办法，不幸的是这些变通办法对更大的范围没有用，例如 A = 1000 和 B = 100000。

假设我们有一个

    Rand()

返回随机数 R, 0 < R < 1 的方法，任何人都可以使用正确的方法发布代码示例吗？在 c#/java/actionscript 中可取。

4

6 回答 6

7

构建一个包含 100 个整数的数组，并用 20 个 1、20 个 2、10 个 3、5 个 4、5 个 5 等填充它。然后从数组中随机选择一个项目。

int[] numbers = new int[100];
// populate the first 20 with the value '1'
for (int i = 0; i < 20; ++i)
{
    numbers[i] = 1;
}
// populate the rest of the array as desired.

// To get an item:
// Since your Rand() function returns 0 < R < 1
int ix = (int)(Rand() * 100);
int num = numbers[ix];

如果项目的数量相当少并且您的精度不是太严格，则此方法效果很好。也就是说，如果你想要 4.375% 的 7，那么你需要一个更大的数组。

于 2012-11-29T22:54:33.037 回答
5

Knuth 将一个优雅的算法归功于 AJ Walker（Electronics Letters 10, 8 (1974), 127-128；ACM Trans. Math Software 3 (1977), 253-256）。

这个想法是，如果你总共有 n 个不同颜色的 k * n 个球，那么可以将这些球分布在 n 个容器中，这样容器号就可以了。i 包含颜色 i 和最多一种其他颜色的球。证明是对 n 的归纳。对于感应步骤，选择球数最少的颜色。

在您的示例中，n = 10。将概率与合适的 m 相乘，使它们都是整数。所以，也许 m = 100，你有 20 个颜色为 0 的球，20 个颜色为 1 的球，10 个颜色为 2 的球，5 个颜色为 3 的球，等等。所以，k = 10。

现在生成一个维度为 n 的表格，其中每个条目是概率（颜色 i 与另一种颜色的球的比率）和另一种颜色。

要生成一个随机球，请在 [0, n) 范围内生成一个随机浮点数 r。令 i 为整数部分（r 的下限），x 为多余部分（r - i）。

if (x < table[i].probability) output i
else output table[i].other

该算法的优势在于，对于每个随机球，您只需进行一次比较。

让我举一个例子（与 Knuth 相同）。

考虑模拟掷一对骰子。

所以 P(2) = 1/36, P(3) = 2/36, P(4) = 3/36, P(5) = 4/36, P(6) = 5/36, P(7) = 6/36, P(8) = 5/36, P(9) = 4/36, P(10) = 3/36, P(11) = 2/36, P(12) = 1/36。

乘以 36 * 11 得到 393 个球，11 个颜色 2，22 个颜色 3，33 个颜色 4，……，11 个颜色 12。我们有 k = 393 / 11 = 36。

表[2] = (11/36, 颜色 4)

表[12] = (11/36, 颜色 10)

表[3] =（22/36，颜色 5）

表[11] = (22/36, 颜色 5)

表[4] =（8/36，颜色 9）

表[10] = (8/36, 颜色 6)

表[5] =（16/36，颜色 6）

表[9] =（16/36，颜色 8）

表[6] =（7/36，颜色 8）

表[8] =（6/36，颜色 7）

表[7] = (36/36, 颜色 7)

于 2012-11-30T00:03:39.743 回答
2

假设您有一个函数p(n)可以为您提供所需的随机数概率：

r = rand()  // a random number between 0 and 1
for i in A to B do
    if r < p(i) 
      return i
    r = r - p(i)    
done

更快的方法是创建一个 (B - A) * 100 个元素的数组，并用从 A 到 B 的数字填充它，这样数组中出现的每个项目的数量与数组大小的比率就是它的概率。然后，您可以生成一个统一的随机数以获取数组的索引并直接访问该数组以获取您的随机数。

于 2012-11-29T22:07:41.567 回答
1

根据概率将您的统一随机结果映射到所需的输出。

例如，对于您的示例：

If `0 <= Round() <= 0.2`: result = 1.
If `0.2 < Round() <= 0.4`: result = 2.
If `0.4 < Round() <= 0.5`: result = 3.
If `0.5 < Round() <= 0.55`: result = 4.
If `0.55 < Round() <= 0.65`: result = 5.
...
于 2012-11-29T22:06:58.590 回答
1

这是Knuth 算法的一个实现。正如一些答案所讨论的那样，它的工作原理是 1）创建一个总频率表 2）生成一个随机整数 3）用上限函数对其进行四舍五入 4）找到随机数落入的“总和”范围并输出原始数组实体基于它

于 2015-12-29T18:29:40.503 回答
0

逆变换

在概率论中，累积分布函数 F(x) 返回任意随机抽取的值（称为 X）<= 某个给定值 x 的概率。例如，如果我在这种情况下做 F(4)，我会得到 0.6。因为您的示例中概率的运行总和是{.2, .4, .5, .55, .6, .65, ....}. 即随机得到一个小于或等于 4 的值的概率是 0.6。然而，我真正想知道的是累积概率函数的倒数，称之为F_inv。我想知道给定累积概率的 x 值是多少。我想传入 F_inv(.6) 并返回 4。这就是为什么这被称为逆变换方法。

因此，在逆变换方法中，我们基本上是试图在累积分布中找到随机均匀 (0,1) 数落在其中的区间。这适用于 perreal 和 icepack 发布的算法。这是用累积分布函数表示它的另一种方式

Generate a random number U
for x in A .. B
   if U <= F(x) then return x

请注意，如果较小的概率出现在分布的开头，则让循环从 B 到 A 并检查 U >= F(x) 可能更有效

于 2012-11-30T05:38:42.243 回答