Алгоритм генерации случайных чисел из дискретного распределения?

Question

Design быстрый алгоритм повторно генерировать число от дискретного распределения: Дан массив а [] из неотрицательных действительных чисел этой суммы до 1, цель состоит в том, чтобы вернуть индекс г с вероятностью в [I]

Я нашел этот вопрос в онлайн-книге алгоритмов «Введение в программирование на Java», глава 4.2 «Сортировка и поиск» (http://introcs.cs.princeton.edu/java/42sort/).

намек говорит:

Форма массив с [] из сумм, накопленных таким образом, что с [I] представляет собой сумму первых г элементов а []. Теперь создайте случайное вещественное число r между 0 и 1 и используйте двоичный поиск, чтобы вернуть индекс i, для которого s [i] ≤ s [i + 1].

некоторые, как я не в состоянии понять намек и, следовательно, не могу найти решение ..

Answer 1

Есть много способов, чтобы ответить на эту проблему. This article описывает многочисленные подходы, их сильные стороны, их слабые стороны и их время автономной работы. Он заканчивается алгоритмом, который берет O (n) время предварительной обработки, затем генерирует числа во времени O (1) каждый.

Особый подход, который вы ищете, описан в разделе «Выбор колесика рулетки».

Надеюсь, это поможет!

Answer 2

Это фрагмент из wakkerbot/megahal. Здесь веса (без знака) ints, а их сумма - в node-> childsum. Для максимальной скорости дети сортируются (более или менее) в порядке убывания. (Весовые коэффициенты должны иметь степенной, как распределение, лишь несколько больших весов и множество мелких)

/* 
    *   Choose a symbol at random from this context. 
    *   weighted by ->thevalue 
    */ 
    credit = urnd(node->childsum); 
    for(cidx=0; 1; cidx = (cidx+1) % node->branch) { 
     symbol = node->children[cidx].ptr->symbol; 
     if (credit < node->children[cidx].ptr->thevalue) break; 
     /* 20120203 if (node->children[cidx].ptr->thevalue == 0) credit--; */ 
     credit -= node->children[cidx].ptr->thevalue; 
    } 
done: 
    // fprintf(stderr, "{+%u}", symbol); 
    return symbol; 

Answer 3

В зависимости от степени детализации, вы можете создать индекс с 100, 1000 или 10000 элементов. Предположим, что распределение (а, б, в, г) с р = (10%, 20%, 30%, 40%), мы создаем карту:

val prob = Map ('a' -> 10, 'b' -> 20, 'c' -> 30, 'd' -> 40) 
val index = (for (e <- prob; 
    i <- (1 to e._2)) yield e._1).toList 

index: List[Char] = List(a, a, a, a, a, a, a, a, a, a, 
b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, 
c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, 
d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d) 

Теперь мы можем выбрать элемент требуемой вероятности очень быстро:

val x = index (random.nextInt (100)) 

x теперь на 40%, на 10% а и так далее. Короткая настройка, быстрый доступ.

Цифры даже не нужно подвести до 100, но вы должны рассчитать диапазон один раз, а затем:

val max = prob.map (_._2).sum 
val x = index (random.nextInt (max)) 

Answer 4

Вот алгоритм Python, который реализует Технику в «рулетке». Трудно объяснить без графики. Статья, связанная с templatetypedef, должна преуспеть для этого. Также обратите внимание, что этот алгоритм фактически не требует нормализации веса (им не нужно суммировать до 1), но это все равно будет работать.

import random 

trials = 50 
selected_indices = [] 

# weights on each index 
distrib = [0.1, 0.4, 0.2, 0.3] 

index = random.randrange(0, len(distrib) - 1) 
max_weight = max(distrib) 
B = 0 
# generate 'trials' random indices 
for i in range (trials): 

    # increase B by a factor which is 
    # guaranteed to be much larger than our largest weight 
    B = B + random.uniform(0, 2 * max_weight) 

    # continue stepping through wheel until B lands 'within' a weight 
    while(B > distrib[index]): 
     B = B - distrib[index] 
     index = (index + 1) % len(distrib) 
    selected_indices.append(index) 

print("Randomly selected indices from {0} trials".format(trials)) 
print(selected_indices)