Вчера у меня был этот вопрос интервью, на который я не мог полностью ответить:
Для функции f() = 0 or 1 с идеальным распределением 1:1 создайте функцию f(n) = 0, 1, 2, ..., n-1 с вероятностью 1/n
Я мог бы найти решение, если n - естественная степень 2, т.е. используйте f() для генерации битов двоичного числа k=ln_2 n. Но это, очевидно, не сработало бы, скажем, n = 5, поскольку это создало бы f(5) = 5,6,7, которое мы не хотим.
Кто-нибудь знает решение?
Вы можете построить rng для наименьшей мощности, превышающей n, как вы описали. Затем, когда этот алгоритм генерирует число, большее, чем n-1, отбросьте это число и повторите попытку. Это называется методом отклонения.
Добавление
Алгоритм
Let m = 2^k >= n where k is is as small as possible.
do
Let r = random number in 0 .. m-1 generated by k coin flips
while r >= n
return r
Вероятность того, что этот цикл остановится не более чем с i итерациями, ограничена 1 - (1/2)^i. Это очень быстро: цикл все еще работает после 30 итераций с вероятностью менее одной миллиардной.
Вы можете уменьшить ожидаемое количество итераций со слегка измененным алгоритмом:
Choose p >= 1
Let m = 2^k >= p n where k is is as small as possible.
do
Let r = random number in 0 .. m-1 generated by k coin flips
while r >= p n
return floor(r / p)
Например, если мы пытаемся сгенерировать 0.. 4 (n = 5) с более простым алгоритмом, мы отклоним 5, 6 и 7, что составляет 3/8 результатов. Если p = 3 (например), pn = 15, у нас будет m = 16 и будет отклонять только 15 или 1/16 результатов. Цена требует четырех флагов монетки, а не 3 и деления op. Вы можете продолжать увеличивать p и добавлять флагами монет, чтобы уменьшить отклонения, насколько вам угодно.
Еще одно интересное решение может быть получено с помощью метода Марковской цепи Монте-Карло, алгоритма Метрополиса-Гастингса. Это было бы значительно более эффективно, если бы требовалось большое количество образцов, но оно ограничивалось бы только равномерным распределением.
initialize: x[0] arbitrarily
for i=1,2,...,N
if (f() == 1) x[i] = (x[i-1]++) % n
else x[i] = (x[i-1]-- + n) % n
При больших N вектор x будет содержать равномерно распределенные числа между 0 и n. Кроме того, добавляя на этапе принятия/отклонения, мы можем имитировать из произвольного распределения, но вам нужно будет моделировать равномерные случайные числа на [0,1] в качестве подпроцедуры.
def gen(a, b):
min_possible = a
max_possible = b
while True:
floor_min_possible = floor(min_possible)
floor_max_possible = floor(max_possible)
if max_possible.is_integer():
floor_max_possible -= 1
if floor_max_possible == floor_min_possible:
return floor_max_possible
mid = (min_possible + max_possible)/2
if coin_flip():
min_possible = mid
else:
max_possible = mid
My #RandomNumberGenerator #RNG
/w any f(x) that gives rand ints from 1 to x, we can get rand ints from 1 to k, for any k:
get ints p & q, so p^q is smallest possible, while p is a factor of x, & p^q >= k;
Lbl A
i=0 & s=1; while i < q {
s+= ((f(x) mod p) - 1) * p^i;
i++;
}
if s > k, goto A, else return s
//** about notation/terms:
rand = random
int = integer
mod is (from) modulo arithmetic
Lbl is a "Label", from the Basic language, & serves as a coordinates for executing code. After the while loop, if s > k, then "goto A" means return to the point of code where it says "Lbl A", & resume. If you return to Lbl A & process the code again, it resets the values of i to 0 & s to 1.
i is an iterator for powers of p, & s is a sum.
"s+= foo" means "let s now equal what it used to be + foo".
"i++" means "let i now equal what it used to be + 1".
f(x) returns random integers from 1 to x. **//
I figured out/invented/solved it on my own, around 2008. The method is discussed as common knowledge here. Does anyone know since when the random number generator rejection method has been common knowledge? RSVP.