Algorithmus zum Generieren von Zufallszahlen aus einer diskreten Verteilung?

Question

Entwerfen Sie ein schneller Algorithmus, um wiederholt erzeugen Zahlen aus der diskreten Verteilung: ein Array a [] von nicht negativen reellen Zahlen diese Summe auf 1 Gegeben ist das Ziel, den Index i mit Wahrscheinlichkeit ein [i] zurückzukehren

Ich fand diese Frage in einem Online-Algorithmus-Buch, Einführung in die Programmierung in Java, Kapitel 4.2: Sortieren und Suchen (http://introcs.cs.princeton.edu/java/42sort/).

der Hinweis sagt:

bilden ein Array s [] der kumulierten Summen, so daß s [i] die Summe der ersten Elemente der i a []. Erzeugen Sie nun eine zufällige reelle Zahl r zwischen 0 und 1 und verwenden Sie die binäre Suche, um den Index i zurückzugeben, für den s [i] ≤ s [i + 1] gilt.

einige, wie ich nicht in der Lage bin den Hinweis zu verstehen und daher finden kann nicht die Lösung ..

Answer 1

Es gibt viele Möglichkeiten, dieses Problem zu beantworten. This article beschreibt zahlreiche Ansätze, ihre Stärken, ihre Schwächen und ihre Laufzeiten. Es schließt mit einem Algorithmus ab, der O (n) Vorverarbeitungszeit benötigt und dann jeweils Zahlen in der Zeit O (1) erzeugt.

Der spezielle Ansatz, den Sie suchen, wird unter "Rouletteauswahl" beschrieben.

Hoffe, das hilft!

Answer 2

Dies ist ein Schnipsel von wakkerbot/megahal. Hier sind die Gewichte (vorzeichenlose) Ints und ihre Summe ist in node-> childsum. Für maximale Geschwindigkeit werden die Kinder (mehr oder weniger) in absteigender Reihenfolge sortiert. (Die Gewichte erwarten ein Potenzgesetz wie Verteilung, mit nur ein paar hochen Gewichten und vielen kleineren)

/* 
    *   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

auf der Granularität Je können Sie einen Index mit 100, 1000 oder 10000 Elementen erstellen. Es sei angenommen, eine Verteilung (a, b, c, d) mit p = (10%, 20%, 30%, 40%), schaffen wir eine Karte:

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) 

Wir haben jetzt ein Element der gewünschten Wahrscheinlichkeit auswählen können sehr schnell:

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

x ist jetzt um 40% d, um 10% und so weiter. Kurze Einrichtung, schneller Zugriff.

Die Zahlen müssen nicht einmal 100 zusammenzufassen, aber Sie haben den Bereich einmal zu berechnen, dann gilt:

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

Answer 4

Hier ist ein Python-Algorithmus, der die ‚Roulette-Rad‘ Technik implementiert. Es ist schwer zu erklären, ohne eine Grafik. Der Artikel, mit dem templatetypedef verlinkt ist, sollte dafür gut sein. Beachten Sie auch, dass für diesen Algorithmus die Gewichte nicht normalisiert werden müssen (sie müssen nicht zu 1 summieren), aber das funktioniert trotzdem.

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)