Перевести "вероятность X в каждом периоде" в "следующий случай в F(случайный, X) секундах"

Question

Для замены существующего алгоритма "каждый период N сравнивает случайное число с вероятностью X", что является правильной функцией F вместо этого вычислить случайную задержку до следующего вхождения?

Я хочу переписать существующую функцию. псевдокод:

interval_step ← (N milliseconds)
Every (interval_step):
    If random() < X:
        event_occurs()

Таким образом, событие может произойти (с X вероятность) при N миллисекунды в ближайшее время. Не существует верхней границы для последних, когда событие может произойти, но большие кратные N становиться все менее вероятным.

Мои математические навыки недостаточно хороши, чтобы сказать, какая формула описывает это. Я думаю, что это геометрическая прогрессия, может быть, логарифмическая?

Вместо этого новая реализация должна производить эквивалентное распределение событий по времени, но без цикла опроса. Вместо этого я хочу установить таймер на случайный интервал, вычисленный из X, псевдокод:

interval_step = (N milliseconds)
schedule(fire_event, interval=random_interval_to_next_event())

random_interval_to_next_event():
    interval ← F(random_number=random(), probability=X)
    Return interval

fire_event():
    schedule(fire_event, interval=random_interval_to_next_event())
    event_occurs()

Это позволяет избежать цикла опроса оригинала, предварительно рассчитав каждое вхождение в течение одного случайного времени (вычисляемого функцией F) в будущем, все еще используя приращения interval_step,

Я был бы достаточно счастлив, чтобы установить произвольную верхнюю границу где-то внутри F (возможно, из-за большого количества стандартных отклонений от X) чтобы избежать потенциально бесконечного вызова функции. Я был бы так же рад избежать этого, если бы это было ненужным осложнением.

(В ответ на обсуждение) Я также рад предположить усеченную точность, чтобы эффективно ограничивать асимптотически малые вероятности в длинном хвосте. Предположим, что существует функция truncate_precision(number, precision_digits=12) это позволило бы что-то вроде:

F(random_number, probability):
    foo ← (random_number * truncate_precision(SOME_CALCULATION))
    Return foo

или т.п. Это позволяет избежать потери значимости при очень низких вероятностях.

Какова правильная реализация функции F получить эквивалентное распределение вероятностей X оригинала?

Answer 1

Вы ищете что-то подобное?

F(random_number, probability):
   return milliseconds * floor(log(1-random_number)/log(probability)) + 1

Это работает, учитывая, что ваше первоначальное решение имеет probability вероятность сна каждой итерации цикла, что в целом дает сон N * milliseconds миллисекунды для Nитерация Так спит для N * milliseconds имеет probability ** N вероятность возникновения, где ** обозначает возведение в степень.

Если мы выбрасываем случайное число один раз, мы можем найти наименьшую степень вероятности, которая все еще больше случайного числа, и это будет указывать, какую итерацию цикл нарушил бы в вашем исходном решении. Для этого решаем следующее уравнение для N, а затем слово это.

random_number = probability ** N

используя изменение базовой формулы

N = log(random_number) / log(probability)

Но большинство генераторов случайных чисел используют диапазон [0, 1)это означает, что нам, возможно, придется оценить log(0), который не определен, поэтому мы инвертируем этот диапазон в (0, 1] вычитая random_number из 1. Наконец, мы добавляем 1, так как мы всегда хотим спать по крайней мере milliseconds миллисекунды. Это дает нам окончательный результат для итераций, чтобы спать N being-

floor(log(1-random_number)/log(probability)) + 1

Обратите внимание, что из-за конечной точности, вы ограничены максимально возможной задержкой, потому что random_number может стать настолько маленьким из-за конечной точности. Это также в значительной степени зависит от того, насколько равномерно ваш ГСЧ.

Answer 2

Альтернативное решение, если вы ищете более точный ответ, который не ограничен аппаратной точностью, вы можете использовать что-то вроде следующего.

F(probability):
   N = 1
   while random() < probability
       N += 1
   return milliseconds * N

Теоретически это допускает любую длительность задержки без верхней границы.