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

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

0 голосов
/ 29 ноября 2018

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

Для номера отслеживания, состоящего из 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.`);
}

1 Ответ

0 голосов
/ 29 ноября 2018

Среднее значение попыток до дублирования описано на Странице парадокса дня рождения вики и 

n(average) = 1 + Q(M)

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

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

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

...