Gewichtete Zufallszahlen

Computer: Software & Programmierung C/C++
#1

Liebes Forum!

Ich möchte gerne Zufallszahlen erzeugen, die aber nur mit einer bestimmten Wahrscheinlichkeiten auftreten dürfen. Dazu habe ich eine Tabelle mit etwa 400 Einträgen (einfache Integer und deren Wahrscheinlichkeit).

Meine bisherige Lösung ein überdimensionales Array (mehrere Milliarden Elemente) einfach zu z.B. 0.046% mit 1er zu füllen, 0.0078% mit 2er zu füllen usw. funktioniert zwar ganz gut, benötigt aber natürlich enorme Speicherkapazitäten (mehrere GB).

Ich suche eine einfache aber dennoch möglichst effiziente Lösung. Dazu stelle ich mir eine Klasse vor, der man mit der AddValue(int nVal, float fProbability) einen neuen Wert mit Wahrscheinlichkeit hinzufügen kann und dannach mit einer Funktion GetRandomValue() abhängig von den Wahrscheinlichkeiten der hinzugefügten Elemente ein Element zurückbekommt.

Wäre für jeden Ansatz dankbar!
mfg dixxi

#2

Ich möchte gerne Zufallszahlen erzeugen, die aber nur mit
einer bestimmten Wahrscheinlichkeiten auftreten dürfen.

Hallo dixxi,

  1. Lösung
    Um Speicherplatz zu sparen, könnte man wie folgt vorgehen:
    Die Integer sind sortiert (1,2,3,4) und wir haben zu jedem Integer eine Wahrscheinlichkeit (0.1, 0.6, 0.25, 0.05). Die Wahrscheinlichkeiten summieren sich zu eins.
    Jetzt würfelt man eine Zufallszahl zwischen 0 und 1 ( rand() / (double)MAX_RAND), z.B. 0.75
    Jetzt durchläuft man die Zahlen und subtrahiert die Wahrscheinlichkeiten bis die Zahl kleiner 0 wird, also 0.75 - 0.1 - 0.6 - 0.25 0.7 ist, müssen wir nach rechts ‚verzweigen‘.

Jetzt müssen wir den restlichen Array wieder in der Mitte teilen und solange verzweigen, bis genau ein Integer übrig ist.

Die Summen der Wahrscheinlichkeiten der Teilarrays sollte man vorher berechnen und sich speichern.

Dieser Ansatz heißt auch Segmentbaum / segment tree, habe leider keine gute Internet-Seite dazu gefunden.

Hoffe, der Ansatz hilft Dir weiter.

Grüße
Thorsten

#3

Hallo Dixxi

Das einfachste wäre m.E. zwei Arrays: in dem einen die Zahlen von 0…399, in dem anderen Integer, welche die Prozent (0…99) invertiert angeben, also „je groesser, desto seltener kommen sie“.

Dazu fehlt noch eine Schleife welche (jede Zahl) im zweiten Array je eins runterzählt. Sobald eine auf Null ist, wird sie zurückgegeben und beim nächsten Mal ignoriert, solange, bis alle verbraucht sind. Oder auch zurück gesetzt auf den Original-Wert, je nach Gutdünken.

Das zweite Array stellt also ein Kurve dar. Zum Beschreiben braucht es hier einen passenden Algo, je nachdem, was Deine Vorstellungen sind. Speicher dafür: 2 + 1 (uint + char), also 400 * 3 Bytes. Plus 400, um die Prozente zurück zu setzen.

lG
Martin B

#4

Hallo

Als Stichwort fällt mir da der „Metropolis Algorithmus“ ein.
Der erzeugt ufallszahlen mit einer gegebenen Wahrscheinlichkeitsdichte.

Google mal

Gruss

Ratz

#5

Herzlichen Dank für deinen Ansatz! Ich bin gerade beim Implementieren und habe noch ein paar Probleme, aber das sollte ich hinkriegen.

mfg dixxi