Zufallsgenerator mit vorgegebener Häufigkeit?

[stoxx]

Hallo,

ich wollte einen Zufallsgenerator entwerfen, der mir z.b. die Zahlen von 1 bis 20 generiert, bei dem ich aber vorher festlegen kann, dass die Zahl 5 mit einer Häufigkeit von 4 Prozent vorkommen soll....
Hat jemand eine Ahnung?
besten Dank ...
stoxx

[Nikolas]

willst du denn nur die 5 häufiger haben, oder für jede Zahl etwas festlegen? Sollen nur ganzzahlige Wahrscheinlichkeiten möglich sein, oder auch andere?

Bei ganzzahligen nimmst du einfach ein array[1.100] of integer und belegst dann davon 4 Felder mit einer 5 usw. Dann muss eben die restliche Aufteilung passen.

Alternativ nimmst dir ein array[0..20] (p) und trägst jeweils die Wahrscheinlichkeiten ein. also p(0)=1, p(1)=2; p(3)=3; p(4)=4; p(5)=8; p(6)=9; p(7)=10 Dann nimmst du eine Zahl von 0 bis 100 und schaust, in welchem Intervall sie liegt. in dem Beispiel würde die 5 dann für Zufallszahlen zwischen 5 und 8 gewählt werden. Also allgemein der eintrag p(n)=p(x<=n) wenn x deine Zufallsvariable ist.
Problematisch dabei sind natürlich die vielen Vergleich, aber um die wirst du bei einer willkürlichen Verteilung nie ganz rumkommen.

[alleinherrscher]

Dann musst du Zufallszahlen mit einer Gausverteilung generieren. Moment ich such dir das grade mal raus...

[alleinherrscher]

okay, dafür müssten wir echt genauer wissen, wie deine Zufallszahlen aussehen. Also wenn du das für ganzzahlige Werte nur machen willst, gibts bestimmt ne einfachere Lösung ansonsten kann ich hier das Skript unseres Datenverarbeitungsprofessors empfehlen: Wir nehmen eine Wahrscheinlichkeitsdichte funktion, also eine funktion die praktisch angibt wie groß die Wahrscheinlichkeit ist, dass deine Zufallszahl in einem bestimmten Bereich liegt.

Dann erzeugst du dir beliebig viele Zufallszahlen mit nem normalen Random und jagst diese durch die Umkehrfunktion deiner Wahrscheinlichkeitsdichte-Funktion. Fertig ;)

Naja, steckt etwas Mathematik hinter...guck hier:

Bitte auf Seite 17 gucken

Gruß

[negaH]

Hi Rene,

interessante Frage, mal schauen.

Ich würde die Zahlen 1 bis 20 als eine Zahlengerade betrachten deren Abstände zwichen den Zahlen die prozentuale Gewichtung darstellt. Dann schaust du in welchem Bereich auf dieser Geraden du landest und nimmst die Zahl zu diesem Bereich als Resulat.

Also wenn man in Prozent rechnet dann würde die Summe der Gewichtungen der Zahlen von 1 bis 20 ja 100 ergeben. Wir ziehen nun mit Random(100) eine Zahl zwischen 0 bis 99 und schauen auf unsere Gewichtete Zahlengeraden in welchem Bereich wir liegen.

Das könnte so aussehen:

Delphi-Quellcode:

function RandomVerteilung(const Verteilung: array of Cardinal): Integer;
var
  I,J: Integer;
begin
  J := 0;
  for I := Low(Verteilung) to High(Verteilung) do
    Inc(J, Verteilung[I]);

  J := Random(J);
  I := Low(Verteilung);
  while (J > 0) and (I <= High(Verteilung)) do
  begin
    Dec(J, Verteilung[I]);
    Inc(I);
  end;
  Result := I;
end;

Angenommen wir möchten aus die Zahlen 1 bis 5 mit folgenden Wahrscheinlichkeiten haben

1 = 10%
2 = 20%
3 = 40%
4 = 10%
5 = 20%

dann benutzen wir obige Funktion so

Delphi-Quellcode:

Result := RandomVerteilung([10,20,40,10,20]) +1;

Unsere Zahlengerade sähe so aus

1 -> 0 bis 9
2 -> 10 bis 29
3 -> 30 bis 69
4 -> 70 bis 79
5 -> 80 bis 99

Gruß Hagen

[negaH]

Es gibt jetzt noch einige Optimeirungen

1.) man wird erstmal die Prozente einkürzen, so daß die kleinste "Prozentangabe" 1 wird und die restlichen Prozente entsprechend gekürzt werden. Dazu benötigt man den GCD -> ggT.

2.) kann man nun ein array[0..MaxProzent-1] of Integer anlegen und dort Anteilmäßig die gesuchten Zahlen eintragen

3.) sähe der Aufruf dann so aus Result := BereichArray[Random(maxProzent)]

Im Obigen Beispiel hatten wir

1 = 10%
2 = 20%
3 = 40%
4 = 10%
5 = 20%

Das lässt sich einfach einkürzen in

1 = 1
2 = 2
3 = 4
4 = 1
5 = 2

MaxProzent wäre also 10, unser BereichArray sähe so aus

BereichArray[0..9] of Integer = (1, 2, 2, 3, 3, 3, 3, 4, 5, 5);


Gruß Hagen

[Nikolas]

Genau das habe ich ja oben beschrieben. :mrgreen:

Bei deiner Implementation muss immer bis zum Treffer durchgelaufen werden, also etwa n/2 Vergleiche angestellt werden. (Wenn man nichts über die Verteilung weiss)

Wenn man jetzt wie bei meiner Beschreibung statt p(x=n) sondern p(x<=n) in die Liste schreibt, könnte man z.b. in der Mitte anfangen und sich dann in die passende Richtung fortbewegen, was dann auf n/4 Vergleiche (/pm 1) kommt.

Wann so eine Zahl häufiger gesucht ist, sollte man den Zahlenstrahl so umordnen, dass zuerst die großen Felder kommen, so dass durchschnittlich unter n/2 Vergleiche stattfinden.

// zum neuen Beitrag von Hagen:

Dabei gehst du aber aus, dass alles glatt aufgeht. Die Verteilung für 6 Zahlen und p(1)=0.12 und p(2)=...=p(6) kann man damit nicht schön modellieren.

[negaH]

Als du das schriebst habe ich mein 1. Posting verfasst ;) Die Lösung ist ja auch trivial.

Je nach Anforderung hat Rene jetzt 2 mögliche Lösungen. Entweder kompakt und universel dafür bischen langsammer was aber meisten irrelevant sein wird, oder die schnellste Methode per Table Lookup. Die Lookup Methode dürfte kaum outperformed werden durch andere Verfahren sie hat O(1) Komplexität egal wie das Array aussieht ;) Die Lookup Methode hat eben den Nachteil das sie mehr Speicher benötigt, aber das ist bei solchen Optimierungen immer der Fall.

Er brauch jetzt nur noch eine Funktion die das "Prozent-array" per GCD optimiert und daraus ein minimal Lenght Array[] für die Bereiche erzeugt.

Gruß Hagen

[Nikolas]

wie meinst du das mit Table LookUp?

Sowas wie mit dem Result := BereichArray[Random(maxProzent)] ?

Besonders wenn da kleine Wahrscheinlichkeiten vorkommen, kann es doch passieren, dass da extrem viele Einträge gemacht werden müssen, oder?

[negaH]

Jo, maximal 100 Einträge wenn wir von ganzzahligen Prozenten ausgehen und das kleinste gemeinsamme Vielfache der Prozentwerte ist 1. Sollte es aber 2 sein so halbiert sich dieses Array, bei 4 virtelt es sich in der Länge usw, bei 10 wie im obigen Beispiel ver-zehntelt sich die Array Größe, statt 100 Elemente eben nur noch 10.

Das ist eben immer ein Feature von hoch optimierten Lösungen die per Tabellen arbeiten. Sehr schnell aber oft nicht sonderlich Speichereffizient ;)

Bei großen Verteilungen und großen Zahlenbereichen würde ich entweder meinen 1. Vorschlag benutzen oder aber eine Version die die beiden Schleifen optimiert. Die 1. Schleife um den MaxProzent Betrag auszurechnen kann entfallen wenn man diesen als Parameter übergibt und hardcoded berechnet. Die 2. Schleife kann per Binärer Suche arbeiten, Komplexität ist dann O(ln N). Dh. bei 1024 Zahlenbereichen kann diese Schleife nach 10 Vergleichen das Resultat finden. Speicherbedarf ist dann N -> N = Anzahl der Bereiche.

Gruß Hagen