Zufallszahlen generieren

24.07.2008, 12:47

mickey

Zufallszahlen generieren

Hi leute,

ich muss für bestimmte Verteilungen Zufallszahlen generieren und habe für einige leider keinen Ansatz.
Zu einigen Verteilungen habe ich bereits mit dem Inversionsverfahren oder der Polar-Methode jeweils der Verteilung entsprechende Zufallszahlen generiert.
Beispiel:
Extremwertverteilung:
Verteilungsfunktion:
F(x) = ℮^(-z) mit z = ℮^((m - x) / s) (max.)
bzw. z = ℮^((x - m) / s) (min.)
dann ist die gesuchte Zufallszahl X mit der Inversionsmethode:

[1. Generiere eine Zufallszahl der Standard Normalverteilung mit Zufallszahl = X
2. Berechne den Wert für x, so dass F(x) = X und nenne diesen c
3. Setze c als Zufallszahl bezogen auf die Verteilung, die von F beschrieben wird]

Maximum:
X = m – s * (ln (ln (1 / y)))
Minimum:
X = s * (ln (ln (1 / y))) - m

X = F^(-1) (y)

Für die Binomialverteilung, Hypergeometrische Verteilung und der negativen Binomalverteilung weiß ich jedoch nicht welche Methode man verwendet.

Bei "Crytal Ball" wird "direct simulation" als Methode genannt... einen Algorithmus oder eine Beschreibung dafür habe ich aber bislang noch nicht gefunden

wer ne Idee hat...

vielen Dabk und lg
mickey

24.07.2008, 14:26

Duedi

Auf diesen Beitrag antworten »

Eine Idee wäre, dass du dich zur Generation von "Zufallszahlen" des quadratischen Iterators (1-z)^2 bedienst. Das bedeutet, dass du einen Startwert z (0<z<1) einsetzt und dann ein paarmal (10-20mal reicht sogar) iterierst, d. h. den Wert von (1-z)^2 wieder in z einsetzst. Die chaotischen Eigenschaften des Iterators sorgen dafür, dass die Zahlen sehr zufällig aussehen.

EDIT: Nach erneutem Durchlesen deiner Fragestellung bin ich mir nun nicht mehr sicher, ob ich dir damit weiterhelfen kann Augenzwinkern

wenn dem so ist: sry

24.07.2008, 17:43

Auf diesen Beitrag antworten »

Zitat:

Original von mickey
[1. Generiere eine Zufallszahl der Standard Normalverteilung mit Zufallszahl = X
2. Berechne den Wert für x, so dass F(x) = X und nenne diesen c
3. Setze c als Zufallszahl bezogen auf die Verteilung, die von F beschrieben wird]

Wenn wir mal Standard Normalverteilung streichen und durch stetige [0,1]-Verteilung ersetzen, dann wird ein Schuh draus - das ist dann die Inversionsmethode für stetige Zufallsgrößen.

Mit Standardnormalverteilung ist das blanker Unsinn - ich hoffe mal, das war nur ein unbedachter Schreibfehler...

Zitat:

Original von mickey
Für die Binomialverteilung, Hypergeometrische Verteilung und der negativen Binomalverteilung weiß ich jedoch nicht welche Methode man verwendet.

Auch für diskrete Zufallsgrößen ist die Inversionsmethode prinzipiell anwendbar. Allerdings bestimmt man hier für die ausgewürfelte Zahl $\begin{eqnarray*} U\in (0,1) \end{eqnarray*}$ den Wert

$\begin{eqnarray*} \min \Big\{ x_0 \Bigm| \sum_{x\leq x_0} p_x \geq U \Big\} \end{eqnarray*}$ ,

bildlich gesprochen: Man summiert solange von "links" (also $\begin{eqnarray*} -\infty \end{eqnarray*}$ ) kommend die Einzelwahrscheinlichkeiten auf, bis man Wert $\begin{eqnarray*} U \end{eqnarray*}$ erreicht (und möglicherweise gleich überschritten) hat. Die entsprechende Stelle ist dann die ausgewürfelte Zufallszahl der diskreten Verteilung.

Für gewisse diskrete Verteilungen sind natürlich auch speziell zugeschnittene Simulationsmethoden denkbar, etwa bei der Binomialverteilung:

$\begin{eqnarray*} X\sim B(n,p) \end{eqnarray*}$ lässt sich ja als Summe von $\begin{eqnarray*} n \end{eqnarray*}$ Bernoulliverteilungen $\begin{eqnarray*} Y_i\sim B(1,p) \end{eqnarray*}$ , i=1...n, darstellen.

Und genauso kann man das dann simulieren: $\begin{eqnarray*} X = \sum_{i=1}^n 1_{U_i \leq p} \end{eqnarray*}$ .

25.07.2008, 15:44

SDwarfs

Auf diesen Beitrag antworten »

Zu "Direct Simulation" hab ich Dir ein paar Infos rausgesucht (unter anderem eine Implementierung, ein Demo-Java-Applet und eine Algorithmusbeschreibung), ob Dir das aber bei Deiner Aufgabe hilft, kann ich Dir nicht sagen:

http://en.wikipedia.org/wiki/Direct_simulation_Monte_Carlo
http://homepage.univie.ac.at/franz.vesel...c8hd_s4dsm.html
http://www.uq.edu.au/~e4mmacro/dsmcpg/rnp.htm
http://www.simba.us/misc/dsmc/dsmca.html
http://de.wikipedia.org/wiki/Monte-Carlo-Simulation (( nur allgemeine Infos zu Monte Carlo Algorithmen, Direct Simulation ist etwas spezieller, aber zum Aneignen von Vorwissen ist es vielleicht gut))

Soweit ich verstanden hab, willst/sollst Du aber eher "Zufallszahlen" durch eine Verteilungsfunktion errechnen...

Solltest Du Zufallszahlen berechnen wollen, die einer bestimmten Verteilung folgen, kann ich Dir folgendes Verfahren anbieten, das ich mir selbst erarbeitet habe und öfter verwende... also das hat keinen Namen oder keinen den ich vergeben habe:

1. Du brauchst einen Zufallsgenerator, der Dir gleichverteilte Zufallszahlen liefert. Jede Programmiersprache hat dafür normalerweise ein paar Routinen, die mehr oder minder gut geeignet sind. Je nachdem welche Art von Ergebnissen die Funktion liefert, rechnest Du die Werte zuerst in eine Fliesskommzahl im Bereich von 0-1 um (einfach durch die Obergrenze des Wertebereichs teilen). Dabei müssen die Zufallswerte ausreichend groß sein können, sonst erreichst du keine gute Verteilung. Sagen wir Werte zwischen 0 und 999'999 wären "OK", aber besser ist wenn es Werte zwischen 0 und ca. 4 Milliarden (2^32) oder sowas sind... Wenn Du zu kleine maximale Werte hast rechne Dir zwei Zufallswerte zu einem Wert zusammen: x = x1 * (max_x1+1) + x2
2. Du benötigst die Verteilungsfunktion deiner Zufallszahl. Die muss (wie das bei Verteilungsfunktionen nunmal so ist): für [0,1] komplett definiert sein und in diesem Bereich monoton steigend sein.
3. Um eine Zufallszahl nach Deiner Verteilung zu errechnen, ermittelst Du eine Zufallszahl wie in 1 beschrieben. Das ist dein y-Wert für die Verteilungsfunktion, für den du jetzt den x-Wert berechnen musst. Dazu berechnest Du am Besten die Umkehrfunktion (evtl. ist das auch mit Inversionsverfahren gemeint?) und setzt den y Wert für "x" ein und bekommst so das gesuchte x... Das ist dann ein Zufallswert, der der angegebenen Verteilungsfunktion folgt. Je sauberer der Zufallsgenerator der Gleichverteilung (also alle Ergebniswerte gleich häufig) folgt und je "zufälliger" (d.h. kein nachvollziehbares Muster in den Werten), desto besser.
Solltest Du keine Umkehrfunktion berechnen können, kannst Du auch durch "gezieltes Probieren" vorgehen. Du kennst sicher das Spiel "Zahlenraten", bei dem sich einer eine Zahl zwischen 1 und 100 ausdenkt und der andere rät, aber nur erfährt ob die Zahl kleiner oder größer ist. Genauso kannst Du hier vorgehen. Wenn das F(x) für dein geratenes x zu groß ist, ist dein x zu groß. Ist das F(x) für dein x zu klein, ist das x zu klein. Wobei F(x) die Verteilungsfunktion ist... Dieses Vorgehen ist aber ziemlich Rechenaufwändig und ist ein Näherungsverfahren. D.h. du kannst dich dem Wert immer weiter annähern, wirst aber im Normalfall nie das Optimum erreichen (also musst Du bei einer zu definierenden "Abweichung" abbrechen).

Ich hoffe das hilft Dir weiter.

LG,
Stefan

25.07.2008, 16:00

SDwarfs

Auf diesen Beitrag antworten »

Hier hast Du eine Erklärung zur Inversionsmethode (inkl. Beweis):
http://www.mathematik.uni-ulm.de/stochas...ipt/node29.html

PS: Solltest Du keinen Zufallszahlengenerator (also rand()-Funktion) zur Verfügung haben, kannst Du Dir einen einfachen programmieren...

Für deine Anwendung sollte ein normaler Pseudozufallszahlengenerator reichen. Es sei denn Du brauchst kryptographische Sicherheit oder extrem zufällige Zufallszahlen.

Ein einfacher Zufallsgenerator ist z.B.:

$\begin{eqnarray*} n_{0} = Startwert... \end{eqnarray*}$
$\begin{eqnarray*} n_{k} = (a * n_{k-1} + c) mod (m) \end{eqnarray*}$

Du kannst Dir das "mod m" auch sparen, wenn Du eine Programmiersprache mit einem vorzeichenlosen(!!!) ganzzahligen Datentyp mit begrenzter Bitlänge verwendest. Das Ergebnis ist dann automatisch "mod m" mit m = 2^(Anzahl Bit).
Für a und c wählst du irgendwelche möglichst großen Werte, am besten Primzahlen, wobei a ungleich c sein sollte.

Neue Frage »

Antworten »

Zufallszahlen generieren

Verwandte Themen