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

[Nikolas]

Wenn du später aber die Binäre Suche einsetzen willst, brauchst du eine andere Liste, mit p(x<=n) in den Einträgen.

[negaH]

Jo das stimmt. Das "Verteilung" Array enthält dann nicht die absoluten Prozentwert für jeden Bereich sondern die kummulierten Prozente, also so

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

[10,30,70,80,100]

Das vereinfacht einiges, 1. Schleife ist nun unnötig, 2. Schleife begint in der Mitte des Arrays[] und vergleicht J mit diesem Element. Sollte es kleiner sein nimmt man die untere Hälfte des Arrays[] und ansonsten die obere Hälfte. Simple binäre Suche halt.

Gruß Hagen

[stoxx]

Also das mit dem Array und eine zweite Zuordnung habe ich mir auch schon überlegt, nur ist das dann noch eine echte Zufallszahl?
Wahrscheinlich reicht das aber für meinen Zweck aus.
ich denke, ich werde es einfach über ein Array lösen, und mit hilfe einer gleichverteilten Zufallsvariable einfach die neue Zahl über diese "Funktion" zuweisen ..
vielen Dank!

[negaH]

Naja, echter Zufall kann es nie sein, da wir ja nur Random() benutzen und das eine Pseudo-Zufalls-Funktion ist, eben kein echter Zufall.

Aber statistisch betrachtet ist es exakt so zufällig wie du die Verteilung vorgibst. Bei zwei Zahlen zb. 1 und 2 die mit einer Wahrscheinlichkeit von 10% zu 90% vorkommen sollen, wird

1.) die Reihenfolge welche der Zahlen gezogen wird statistisch exakt so gleichverteilt sein wie Random(), als benutze Zufallsfunktion
2.) die statistische Häufung der beiden Zahlen jeweils 10% zu 90% sein. Die zweite Zahl kommt also 9 mal häufiger vor als die 1. Zahl

Das verhältnis der Häufigkeiten ist also nicht im geringsten zufällig, ist ja auch so von uns gewollt. Die Reihenfolge der gezogenen Zahlen ist aber sehr wohl noch pseudozufällig. Wird statt Random() ein echter Zufallsgenerator benutzt dann ist die Reihenfolge auch zufällig.

Sieh es mal so. Wir ziehen mit einem echten Zufallsgenerator Zahlen im Berewich 1 bis 100. Wie wird die Häufigkeitsverteilung dieser 100 Zahlen nach einer gewissen Zeit sein ? Zufällig oder exakt berechnenbar ?

Natürlich beträgt die Wahrscheinlichkeit dann exakt 1/100'tel für die Häufigkeiten der gezogenen Zahlen. Bei 100 Zahlen also 1 Prozent pro Zahl. Logisch da ein Zufallsgenerator statistisch die Häufigkeiten auf den kompletten Zahlenbereich gleichmäßig verteilt. Das ist ja auch die Grundlage dafür das man mit den vorherigen Lösungsvorschlägen aus einer statistischen Gleichverteilung eine vorgegebene Ungleichverteilung erreichen kann. Wir gehen davon aus das Random() immer gleichverteilte Häufigkeiten erzeugt, skalieren unsere Vorgabehäufigkeiten entsprechend um eine ungleichverteilte Häufigkeit zu erreichen.

Also selbst mit echten Zufall wären die Häufigkeiten welche Zahlen man zieht nicht zufällig, sondern statistisch gleichverteilt wenn man gegen unendlich viele Zahlen gezogen hat.

Die statistische Verteilung der Zahlen ist also fast immer gleichverteilt, egal mit welchem Verfahren man diese Zahlen erzeugt (guter RNG vorrsausgesetzt).

In der Physik gibts aber sehr viele Phenomäne die keine Gleichverteilung der Wahrscheinlichkeiten der gezogenen Zahlen aufweisen. Zb. Gaussche Verteilung -> Glockenkurve.

Anderst ausgedrückt: Zufällig ist nicht die Häufigkeit sondern nur der Zeitpunkt wann man welche Zahl zieht. Zufall bestimmt also den Zeitpunkt wann was eintritt aber nicht wie oft es als ein Ereignis unter vielen anderen vorkommt. Die Frage nach dem "oft", also dem Vorkommen eines Ereignisses wird immer statistisch berechenbar sein. Dazu benötigt man die Periode und die Art des Zufallsgenerators. Kennt man das beides bestimmt nur noch die Größe der gezogenenen Ereignisse inwieweit wir die statistische Häufigkeit berechnen können.

Es ist sehr wichtig das zu begreifen um zu verstehen was Zufall ist.

Gruß Hagen