Перевести "вероятность X в каждом периоде" в "следующий случай в F(случайный, X) секундах"
Для замены существующего алгоритма "каждый период 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
оригинала?
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
being-
floor(log(1-random_number)/log(probability)) + 1
Обратите внимание, что из-за конечной точности, вы ограничены максимально возможной задержкой, потому что random_number
может стать настолько маленьким из-за конечной точности. Это также в значительной степени зависит от того, насколько равномерно ваш ГСЧ.
Альтернативное решение, если вы ищете более точный ответ, который не ограничен аппаратной точностью, вы можете использовать что-то вроде следующего.
F(probability):
N = 1
while random() < probability
N += 1
return milliseconds * N
Теоретически это допускает любую длительность задержки без верхней границы.