随机数生成算法

Question

我遇到了一个朴素的随机数生成算法，它产生的一系列数字如下：

for (int i = 0; i < MAX; i++)
   if (rand.nextInt(100) >= 100 - probability) // probability is between 0 and 100
       randomNumbersList.add(i);

我想知道是否有一种方法可以在不遍历0到MAX之间的每个数字的情况下实现统计上等效的结果。

- traveh

---

首先，这只是创建一个在 probablity 和 100 之间的（可能为空的）“随机”数字列表。其次，您并没有真正迭代 0 到 MAX 之间的每个数字，代码尝试生成数字 MAX 次。如果您想做 X 次某事，必须在某个地方有一个循环。 - Buurman

@Buurman 不是真的 - 它创建了一个严格递增的整数列表，最多包含介于0和MAX之间的MAX个整数，其中列表的平均长度由MAX *（probability / 100.0）给出。 - tucuxi

抱歉，@tucuxi，你是正确的。我错过了它将i添加到列表中。感谢您的纠正。 - Buurman

Answer 1

你的算法创建了一个最多包含MAX个元素的列表。每个元素是从0到MAX-1的整数，没有重复。由于rand.nextInt(n)返回在0和n之间均匀分布的数字x，使得0<=x=100-p始终为false（x永远不是100），如果p == 100，则始终为true（x始终大于等于0）。因此，预期的元素数量是MAX*(p/100.0)。

如果MAX很高但p很低，则可以显着改进：在大多数情况下，您会投掷加权硬币，但它会出现尾巴，并且您不会添加任何内容。浪费工作。然而，如果p很高（比如超过.5），那么您通常会生成与MAX同阶的元素；并且很难使事情变得更快（您应该期望进行O(MAX)的工作来创建O(MAX)的随机元素）。如果MAX很小，则两种方法之间几乎没有区别-所以我会坚持使用更简单的方法：你已经有的方法。

假设MAX很大，p很小

我们可以使用众所周知的二项分布来模拟列表的长度（因为您正在投掷MAX个不公平的硬币，这些硬币以概率p落在“正面”）。Java代码可在Colt库中获得。使用它们的类，应该可以实现以下功能：

 Binomial b = new Binomial(MAX, p, new MersenneTwister());
 int heads = b.nextInt();

现在我们需要生成“头部”排序整数，范围在0到MAX-1之间。假设MAX比头部要大得多。我们可以使用。

 TreeSet<Integer> chosen = new TreeSet<>();
 for (int i=0, r=0; i<heads; i++) {
     do { r = random.nextInt(MAX) } while (chosen.contains(r));
     chosen.add(r);
 }

请注意，当p很高时，这会导致性能非常糟糕，因为内部循环将被执行多次；但是对于这种情况，您的初始算法已经足够好了。

当p较低时，所提出的算法将需要与MAX成比例的时间，而不是MAX。这应该可以更好地弥补维护TreeSet排序的成本。

- tucuxi

---

谢谢您详细的回答！我确实忘记提到MAX是很大的，而且p很小（大约1%或更少）。我会进行测试并回来确认。 - traveh

Answer 2

我们将p=probability/100和q=1-p。

考虑第一个要添加的数字是什么。以概率q为0; 以概率(1-q)*q为1，以概率(1-q)^2*q为2等等。这就是几何分布。您可以使用以下方法轻松生成按几何分布分布的随机数：生成在[0,1]范围内均匀分布的随机数u并计算x=⌊ln(u)/ln(q)⌋ - 这个x将具有几何分布（参见此问题）。

所以这就是如何计算要添加的第一个数字。

现在考虑第二个数字与第一个数字之间的差异。它也将按几何分布分布（仅从1开始，而不是从0开始），因此您可以以相同的方式计算此差异，从而获得第二个数字，依此类推。

伪代码如下：

cur = -1
lnq = ln(q)
while true
    u = random(0,1)   // float!
    cur = cur + 1 + floor(ln(u)/lnq)
    if cur >= MAX
        break
    randomNumbersList.add(cur);

@traveh编写的相应Java代码

List<Integer> randomNumbersList = new LinkedList<Integer>();
int cur = -1;
double p = probability / 100;
double q = 1 - p;
double lnq = Math.log(q);
Random random = new Random();
while (true) {
    double u = random.nextDouble();
    cur = cur + 1 + (int)Math.floor(Math.log(u) / lnq);
    if (cur >= MAX)
        break;
    randomNumbersList.add(cur);
}

- Petr

---

您还可以预先计算1/ln(q)。 - tucuxi

@traveh，我认为你应该自己判断，也许进行几次实验后再决定。这个解决方案需要在每个时间步骤计算对数，因此可能比其他解决方案慢。同时，它要求每个生成的元素恰好调用一次随机函数，因此可能更快。因此，我建议尝试在真实数据上进行测试，或者根据概率值在两种方法之间切换。 - Petr

我假设通过查找自然对数的计算是相当廉价的 - 这几乎不会比TreeSet的查找慢，并且也不需要内存访问。如果这是正确的（而且看起来确实如此），那么它比我的答案要快得多。 - tucuxi

测试过了，运行得非常好 :) @tucuxi 由于时间不够，我暂时不会测试性能差异（如果我有机会的话，将来会更新）。我感谢你们所有人的努力，特别是公平竞争 - 给你们的答案点赞。你们真棒！ - traveh

附注：我正在更新答案，加上实际的Java代码，反正我已经做了... :) - traveh

Answer 3

对于每一个数字，你需要确定选择是否成功（数字被选中）。因此，在 MAX 次尝试中，你的数字基本上就是成功次数。如果你可以预先确定成功次数，那么你可以从有效范围内获得相同数量的独特随机数。并且它们在统计学上是相同的。所以你要找的是二项式分布。使用成功概率和尝试次数（MAX）从这个分布中获取一个随机数。这将给你随机数的数量。然后获取这么多个随机唯一数字，就完成了。

- Nuri Tasdemir

---

我认为“许多随机唯一数字”不会起作用，我预计（尽管没有检查过），例如，连续数字之间的差异分布将是不同的。 - Petr

我不同意，@Petr - 在0到MAX之间的任何随机整数被包含的概率与是否已经包含其他整数无关。只要保持这种独立性，差异的分布将是相同的。 - tucuxi

@tucuxi，嗯，我想我同意。 - Petr

Answer 4

Java代码为Petr的答案：

```java```

List<Integer> randomNumbersList = new LinkedList<Integer>();
int cur = -1;
double p = probability / 100;
double q = 1 - p;
double lnq = Math.log(q);
Random random = new Random();
while (true) {
    double u = random.nextDouble();
    cur = cur + 1 + (int)Math.floor(Math.log(u) / lnq);
    if (cur >= MAX)
        break;
    randomNumbersList.add(cur);
}

- traveh