Какова общая формула для расчета вероятности генерации повторяющегося случайного числа?

Question

Я генерирую случайные номера отслеживания заказа, которые должны быть короткими, но не должны дублироваться.

Для номера отслеживания, состоящего из 3 цифр, мы сгенерируем повторяющееся случайное число в среднем после 40 попыток.

Если мы увеличим его до 12 цифр, то в среднем потребуется 1,3 миллиона попыток сгенерировать повторяющееся случайное число.

Какова более общая формула для расчета, сколько попыток в среднем потребуется, чтобы сгенерировать повторяющееся случайное число до предопределенного предела?

Опытным путем я могу понять это, используя этот код, но я ищу более общее решение:

/**
 * 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

Средняя стоимость проб перед повторением описана на странице парадокса дня рождения Вики и

n(average) = 1 + Q(M)

где М ваш диапазон и

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

Рамануджанское приближение дает 40,3 для М =1000 и 1253314 для 10^12