计算产生重复随机数的概率的一般公式是什么？

Question

我正在生成随机订单跟踪编号，该编号应该很短，但不应重复。

对于由3位数字组成的跟踪号，我们将在平均尝试40次后生成一个重复的随机数。

如果我们将它增加到 12 位数字，平均需要 130 万次尝试才能生成重复的随机数。

用于计算生成达到预定义限制的重复随机数平均需要多少次尝试的更通用的公式是什么？

根据经验，我可以使用这段代码解决问题，但我正在寻找更通用的解决方案：

/**
 * Calculates the average iteration at which we will generate
 * a random integer that has been generated before.
 * This numbers is much smaller than expected due to birthday paradox.
 */

// Generate random numbers up to (exclusive) this number:
const RANGE = 1000000000000;

let foundCollisions = 0;
const foundAt = [];

while(true) {
  let i = 0;
  const exists = {}

  while(true) {
    i++;

    const random = Math.floor(Math.random() * RANGE);

    if (exists[random]) {
      // We found a duplicate number:
      break;
    } else {
      exists[random] = true;
    }
  }

  foundCollisions++;
  foundAt.push(i);

  // Calculate the average iteration at which we found a duplicate number:
  const averageFoundAt = foundAt.reduce((total, num) => total + num) / foundCollisions;
  console.log(`Found ${foundCollisions} collisions, average at ${Math.round(averageFoundAt)}th iteration.`);
}

Answer 1

在 Wiki birthday paradox page 和

中描述了重复之前的试训平均值

n(average) = 1 + Q(M)

其中 M 是您的范围，

Q(M) = Sum[k=1..M](M!/(M-k)!M^k)

Ramanujan 近似给出 M=1000 的 40.3 和 10^12 的 1253314

计算产生重复随机数的概率的一般公式是什么？

What is the general formula for calculating the probability of generating a duplicate random number?

math

random

birthday-paradox