webentwicklung-frage-antwort-db.com.de

Pseudozufallszahlengenerator - Exponentialverteilung

Ich möchte einige Pseudozufallszahlen generieren und war bis jetzt sehr zufrieden mit der Funktion Random.Next(int min, int max) der .Net-Bibliothek. PRNGs dieser Art sollen angeblich eine Gleichverteilung verwenden, aber ich würde sehr gerne einige Zahlen mit einer Exponentialverteilung generieren .

Ich programmiere in C #, obwohl ich Pseudocode oder C++, Java oder ähnliches akzeptieren werde.

Irgendwelche Vorschläge/Code-Schnipsel/Algorithmen/Gedanken?

57
Charlie Salts

Da Sie Zugriff auf einen einheitlichen Zufallszahlengenerator haben, können Sie mit der Inversionsmethode leicht eine Zufallszahl generieren, die mit einer anderen Distribution verteilt wird, deren CDF Sie kennen.

Also generiere eine einheitliche Zufallszahl, u, in [0,1) Und berechne x durch:

x = log(1-u)/(− λ ),

wobei λ der Geschwindigkeitsparameter der Exponentialverteilung ist. Nun ist x eine Zufallszahl mit einer Exponentialverteilung. Beachten Sie, dass log oben ln ist, der natürliche Logarithmus.

98
Alok Singhal

Der Grundsatz des Samplings besagt, dass Sie frei Haus sind, wenn Sie die gewünschte Verteilung normalisieren, integrieren und invertieren können.

Wenn Sie eine gewünschte Verteilung haben, wird F(x) auf [a,b] Normalisiert. Sie rechnen

C(y) = \int_a^y F(x) dx

invertiere das, um C^{-1} zu erhalten, wirf z gleichmäßig auf [0,1) und finde

x_i = C^{-1}(z_i)

welches die gewünschte Verteilung haben wird.


In Ihrem Fall: F(x) = ke^{-kx} und ich gehe davon aus, dass Sie [0,infinity] Wollen. Wir bekommen :

C(y) = 1 - e^{-ky}

das ist invertierbar zu geben

x = -1/k  ln(1 - z)

für z gleichmäßig auf [0,1) geworfen.


Aber ehrlich gesagt ist die Verwendung einer gut debuggten Bibliothek intelligenter, es sei denn, Sie tun dies zu Ihrer eigenen Erbauung.

13
dmckee

Wenn Sie gute Zufallszahlen wollen, ziehen Sie eine Verknüpfung mit den gsl-Routinen in Betracht: http://www.gnu.org/software/gsl/ . Sie haben die Routine gsl_ran_exponential. Wenn Sie Zufallszahlen mit einem eingebauten Generator mit einer gleichmäßigen Verteilung auf [0, 1] erzeugen möchten (z. B. u = Random.Next (0, N-1)/N, für einige große N), verwenden Sie einfach:

-mu * log (1-u)

Siehe randist/exponential.c in der gsl-Quelle.

EDIT: nur zum Vergleich mit späteren Antworten - dies entspricht mu = 1/Lambda. mu hier ist der Mittelwert der Verteilung, auch Skalierungsparameter auf der Wikipedia-Seite genannt, mit der das OP verknüpft ist, und Lambda ist der Ratenparameter.

6
Ramashalanka

Eine interessante Eigenschaft der Exponentialverteilung: Betrachten Sie einen Ankunftsprozess mit exponentiellen Interarrival-Zeiten. Nehmen Sie einen beliebigen Zeitraum (t1, t2) und die Ankünfte in diesem Zeitraum. Diese Ankünfte sind EINHEITLICH zwischen t1 und t2 verteilt. (Sheldon Ross, Stochastic Processes).

Wenn ich einen Pseudozufallszahlengenerator habe und aus irgendeinem Grund (z. B. meine Software kann keine Protokolle berechnen), möchten Sie die obige Transformation nicht durchführen, sondern eine exponentielle r.v. mit Mittelwert von 1,0.

Du kannst :

1) Erstellen Sie 1001 U (0,1) Zufallsvariablen.

2) Nach Reihenfolge sortieren

3) Subtrahiere die Sekunde von der ersten, die Dritte von der zweiten, ... um 1000 Differenzen zu erhalten.

4) Diese Differenzen sind Exponential-RVs mit einer Verteilung mit einem Mittelwert von 1,0.

Weniger effizient, denke ich, aber ein Mittel zum gleichen Zweck.

4
Grembo

Die Open-Source-Bibliothek ncommons Maths library von Dan Dyer bietet Zufallszahlengeneratoren, Wahrscheinlichkeitsverteilungen, Kombinatoren und Statistiken für Java.

ExponentialGenerator hat unter anderem die von @Alok Singhal erläuterte Idee im Wesentlichen umgesetzt. In seinem Tutorial-Blog wird ein Code-Snippet angegeben, um ein zufälliges Ereignis zu simulieren, das durchschnittlich 10-mal pro Minute passiert ist:

final long oneMinute = 60000;
Random rng = new MersenneTwisterRNG();

// Generate events at an average rate of 10 per minute.
ExponentialGenerator gen = new ExponentialGenerator(10, rng);
boolean running = true;
while (true)
{
    long interval = Math.round(gen.nextValue() * oneMinute);
    Thread.sleep(interval);

    // Fire event here.
}

Wenn Sie die Zeiteinheit per second Bevorzugen (anstelle von a minute Hier), müssen Sie nur final long oneMinute = 1000 Einstellen.

Wenn Sie tiefer in das Quellcode der Methode nextValue() von ExponentialGenerator gehen, finden Sie das sogenannte Inverse Transformation Sampling beschrieben in Generating_exponential_variates [wiki] :

public Double nextValue()
{
    double u;
    do
    {
        // Get a uniformly-distributed random double between
        // zero (inclusive) and 1 (exclusive)
        u = rng.nextDouble();
    } while (u == 0d); // Reject zero, u must be positive for this to work.
    return (-Math.log(u)) / rate.nextValue();
}  

P.S.: Vor kurzem benutze ich die Uncommons Maths-Bibliothek. Vielen Dank, Dan Dyer.

1
hengxin

Wenn ich Ihr Problem verstehe und Sie eine endliche Anzahl von PRNGs akzeptieren können, können Sie einen Ansatz verfolgen wie:

  • Erstellen Sie ein Array, in dem sich jedes Element in Ihrer Exponentialverteilung befindet
  • Generieren Sie einen PRNG, der ein ganzzahliger Index im Array ist. Geben Sie das Element im Array an diesem Index zurück.
0
GreenMatt