Перевести «вероятность 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(probability):
   N = 1
   while random() < probability
       N += 1
   return milliseconds * N

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

Answer 2

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

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, будучи-

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

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