Как я могу сделать случайный выбор из обратно-взвешенного списка?

Question

Дан список целых чисел, например, 1, 2, 3, 4, я знаю, как выбирать предметы в зависимости от их веса. Примеры элементов будут иметь вероятности 10%, 20%, 30% и 40% соответственно.

Существует ли такой же простой метод выбора предметов, основанный на обратном весе? При использовании этого метода список примеров будет равен взвешенному списку 1, 1/2, 1/3, 1/4 (48%, 24%, 16%, 12%), но я хочу избежать преобразования и использования арифметики с плавающей точкой. (Предположим, что все целые числа являются положительными и отличными от нуля.)

Answer 1

Вы можете разделить числа ' наименьшее общее кратное на каждое число и получить целые пропорции.

Для [1, 2, 3, 4] это 12. Ваш вес 12/1 = 12, 12/2 = 6, 12/3 = 4, 12/4 = 3.

Вы также можете умножить их все вместе и не беспокоиться о LCM. Числа будут выше, но пропорции будут одинаковыми: 24/1 = 24, 24/2 = 12, 24/3 = 8, 24/4 = 6.

Answer 2

Сначала получите сумму весов, назовите ее S (например, 1 + 1/2 + 1/3 + 1/4 = 2.083). Затем, чтобы найти вероятность веса w_i, вы делите w_i на S (например, 1/2.083 = 48%.

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

Сумма весов гармонических чисел . Для больших n сумма сходится к ln(n)+gamma, где гамма - это постоянная Эйлера-Маскерони (~ 0,577). Так что для больших n вы можете использовать эту формулу для аппроксимации суммы.

РЕДАКТИРОВАТЬ: Есть способы уменьшить ошибки с плавающей запятой. Одним из таких способов является вычисление суммы от наименьшего слагаемого до наибольшего слагаемого (например, 1/n + 1/(n-1) + ... + 1). Это позволяет промежуточным вычислениям максимизировать количество битов точности. При этом проблемы округления не должны быть проблемой.