Inhaltsverzeichnis dieser Seite Transformation von Bitstreams    Antwort    Inverse Wahrscheinlichkeitstransformation    Antwort    Fazit    Geometrisch begründete Transformationen neben der Box-Mueller-Transformation    Antwort

Transformation von Bitstreams

Die geläufigen PRNG Algorithmen erzeugen entweder Bits(treams) oder Ganzzahlen. Wie kann man diese numerisch sinnvoll auf eine Gleichverteilung im Bereich [0,1) transformieren?

Antwort

Das ist eigentlich schon wieder ein ganz eigenes Thema, das aber keine besonders schwierige Antwort hat. Aus einem Bitstream kann man Stücke gleicher Laenge d herausschneiden, diese als nicht vorzeichenbehaftete Zahlen betrachten, und dann durch "2 hoch d" teilen. So bis d=52 ist das eine triviale und verlustfrei mögliche Fliesskommaoperation für IEEE 754 double precision. Hat man ganze Zahlen, dann sind diese ebenfalls oft aus einer Gleichverteilung auf [0 .. 2 hoch d) gezogen. Dann gilt für diese das Gleiche. Durch Fliesskommadivision mit "2 hoch d" lassen sie sich auf das Intervall [0, 1) abbilden.

Inverse Wahrscheinlichkeitstransformation

Als Laie spricht mich besonders das Thema "inverse Wahrscheinlichkeitstranformation" an, weil es in gewissen Rahmen zu versprechen scheint, dass sich "beliebige" Verteilungen erzeugen lassen. Aber vielleicht stelle ich mir das auch zu einfach vor. Deshalb versuche ich ein Beispiel zu konstruieren.

Ich möchte eine Sinus-förmige Verteilung (für die erste Halbwelle) implementieren. Dies sollte mit Hilfe der Umkehrfunktion asin möglich sein. Also schreibe ich (ungetestet):

double RandomRetDouble_sin(void) /* 0..PI */ { double ret = asin(RandomRetDouble()); if (RandomRetUlong() & 1) { ret = M_PI - ret; } return ret; }

Ist das zumindest im Prinzip so machbar?

Jetzt habe ich mir aus Neugier die Verteilung doch qualitativ angeschaut, und da scheint

double RandomRetDouble_sin(void) /* 0..PI */ { double r = RandomRetDouble(); double ret = asin(r); if (RandomRetUlong() & 1) { ret = M_PI_2 + ret; } else { ret = M_PI_2 - ret; } return ret; }

nötig zu sein.

Antwort

Wenn sin(x) eine Verteilungsfunktion (monoton steigend, von links stetig, Infimum des Bildes ist 0, Supremum des Bildes ist 1) und für unsere Zwecke zusätzlich eine injektive Abbildung vom Wertebereich der Verteilung in das Einheitsintervall wäre, dann würde das so funktionieren.

Damit es tatsächlich funktioniert, muss eine passende Verteilungsfunktion gebildet werden. Wenn eine Verteilung angestrebt ist, deren Dichte proportional zur ersten Halbwelle des Sinus ist, muss eine geeignete Dichte gewählt werden. Die Sinusfunktion ist keine Wahrscheinlichkeitsdichte auf dem Intervall 0 bis Pi, aber f(x)=sin(x)/2 ist eine Wahrscheinlichkeitsdichte auf diesem Intervall (nicht negativ, normiert). Die passende Verteilungsfunktion ist demzufolge F(x)= (1-cos(x))/2 für x aus dem Intervall 0 bis Pi. Deren Umkehrfunktion ist schliesslich x(p)=Pi-arccos(2p - 1). Also ist X=Pi-arccos(2*U-1) eine Zufallszahl aus einer Verteilung auf dem Intervall 0 bis Pi, deren Dichte zur ersten Halbwelle der Sinusfunktion proportional ist.

double RandomRetDouble_sin(void) /* 0..PI */ { double ret; ret = M_PI - acos(2 * RandomRetDouble() - 1.0); return ret; }

Eine andere mögliche Verteilung, die aus der Sinusfunktion herleitbar wäre (und fuer die die Umkehrung mit dem arcus sinus direkt funktioniert) ist die Verteilung, die die folgende Abschnittsweise definierte Verteilungsfunktion hat: Für x kleiner 0 ist F(x) = 0, für x aus dem Intervall von 0 bis Pi/2 ist F(x) = sin(x) und für x > Pi/2 ist F(x) = 1. Diese Funktion ist eine Verteilungsfunktion (sie ist linksseitig stetig, monoton steigend und eine injektive Abbildung des Intervalls von 0 bis Pi/2 auf das Einheitsintervall). Also ist sie für eine inverse Wahrscheinlichkeitstransformation geeignet. Die mit

double RandomRetDouble_sin(void) /* 0..PI/2 */ { double ret = asin(RandomRetDouble()); return ret; }

erzeugten Pseudozufallszahlen sind aus einer Verteilung gezogen, die den Wertebereich 0 bis Pi/2 hat. Die Dichte der zugehörigen Verteilung ist in diesem Intervall f(x)=cos(x), sie hat den Erwartungswert Pi/2 - 1 und die Varianz 1/24 Pi^3 + 1/8 (2-Pi) Pi^2 + 1/2 (1 - Pi/2)^2 Pi.

Fazit

Im Prinzip kann die inverse Wahrscheinlichkeitstransformation für alle im Wertebereich der Zielverteilung injektiven Verteilungsfunktionen angewendet werden. Es ist auch kein zusätzliches Würfeln erforderlich. Das Problem ist damit darauf reduziert, die richtige Verteilungsfunktin der gewünschten Zielverteilung herzuleiten und die richtige Umkehrfunktion zu bilden. Wenn der Wertebereich der Zielverteilung kein abgeschlossenes Intervall ist, kommt noch das Problem der Behandlung der Ränder hinzu.

In der Praxis scheitert die inverse Wahrscheinlichkeitstransformation oft daran, das die Umkehrfunktion der Verteilungsfunktion zwar existiert, aber nicht geschlossen darstellbar ist. Spätestens wenn eine Inversion nur noch numerisch durch Nullstellensuche in F(x)-U möglich ist, sollte ein anderes Verfahren herangezogen werden, wenn eines bekannt ist.

Geometrisch begründete Transformationen neben der Box-Mueller-Transformation

Gibt es neben der Box-Mueller-Transformation auch andere Anwendungen des gleichen Prinzips

Antwort