java - 随机数生成算法

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 之间的每个数字的情况下获得统计上等效的结果。

Answer 1

让我们用 p=probability/100 和 q=1-p 表示。

考虑要添加的第一个数字是什么。概率 q 为 0； (1-q)*q 的概率为 1，(1-q)^2*q 的概率为 2，依此类推。这是 geometric distribution .您可以使用以下方法轻松生成按几何分布分布的随机数:生成均匀分布在 [0,1] 中的随机数 u 并计算 x=⌊ln(u)/ln(q)⌋ — 此 x 将具有几何分布(参见 this question )。

这就是您计算要添加的第一个数字的方法。

现在考虑第二个和第一个数字之间的差异。它也会按几何分布(只从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);
}