Zufallszahlengenerator, der eine Potenzgesetzverteilung erzeugt?

StackOverflow https://stackoverflow.com/questions/918736

  •  06-09-2019
  •  | 
  •  

Frage

Ich schreibe einige Tests für eine Kommandozeile Linux App ++ C. Ich möchte eine Reihe von ganzen Zahlen mit einem Potenzgesetz / Long-Tail-Verteilung erzeugen. Bedeutung, erhalte ich einige eine Anzahl sehr häufig, aber die meisten von ihnen relativ selten.

Im Idealfall wäre es nur ein paar magische Gleichungen I mit rand () oder einer der stdlib Zufallsfunktionen nutzen könnten. Wenn nicht, ein einfaches Stück von C / C ++ wäre toll.

Danke!

War es hilfreich?

Lösung

Die Seite bei Wolfram MathWorld beschreibt, wie ein Potenzgesetz Verteilung von einer gleichmäßigen Verteilung erhalten (das ist, was die meisten Zufallszahlen-Generatoren zur Verfügung stellen).

Die kurze Antwort (Ableitung auf dem obigen Link): 

x = [(x1^(n+1) - x0^(n+1))*y + x0^(n+1)]^(1/(n+1))

, wobei y ist eine einheitliche Veränderlichen, n die Verteilungsleistung, x0 und x1 definieren den Bereich die Verteilung und x ist Ihr Potenzgesetz verteilt variate.

Andere Tipps

Wenn Sie die Verteilung wissen, dass Sie (die Wahrscheinlichkeitsverteilungsfunktion (PDF) genannt) und haben es richtig normalisiert, können Sie es integrieren können die kumulative Verteilungsfunktion (CDF) zu erhalten, dann die CDF invertieren (wenn möglich) zu erhalten die Transformation müssen Sie nicht einheitlich [0,1] Verteilung auf die gewünschte.

So können Sie durch die Definition der Verteilung Sie wollen starten. 

P = F(x)

(für x in [0,1]), dann integriert geben 

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

Wenn diese invertiert werden Sie bekommen 

y = F^{-1}(C)

So rand() nennen und das Ergebnis in als C in der letzten Zeile Plug-and-y verwenden.

Dieses Ergebnis ist der Fundamentalsatz des Sampling genannt. Dies ist ein Streit wegen der Normalisierung Bedarf und die Notwendigkeit, analytisch die Funktion invertieren.

Alternativ können Sie eine Ablehnung Technik verwenden: eine Reihe gleichmäßig im gewünschten Bereich werfen, dann eine andere Nummer werfen und an der Stelle, an der PDF vergleichen Ihren ersten Wurf indeicated. Ablehnen, wenn der zweite Wurf die PDF überschreitet. Neigt für PDF-Dateien mit viel geringer Wahrscheinlichkeit Region, wie jene mit langen Schwänzen ineffizient zu sein ...

Ein Zwischen Ansatz beinhaltet die CDF durch Brute-Force-Invertierung: Sie können die CDF speichern als Lookup-Tabelle, und machen Sie einen Reverse-Lookup das Ergebnis zu erhalten

.

Die eigentlichen Stinker hier sind, dass einfache x^-n Verteilungen sind nicht normierbare auf dem Bereich [0,1], so dass Sie nicht das Abtasttheorem verwenden können. Versuchen (x + 1) ^ - n statt ...

kann ich nicht auf die Mathematik Kommentar benötigt, um ein Potenzgesetz Verteilung (die anderen Beiträge Vorschläge) zu erzeugen, aber ich würde Sie sich mit den TR1 C ++ Standard Library Zufallszahl Einrichtungen in <random> vertraut vor. Diese bieten mehr Funktionalität als std::rand und std::srand. Das neue System gibt eine modulare API für Generatoren, Motoren und Verteilungen und liefert eine Reihe von Voreinstellungen.

Die enthaltenen Verteilungs Voreinstellungen sind:

  • uniform_int
  • bernoulli_distribution
  • geometric_distribution
  • poisson_distribution
  • binomial_distribution
  • uniform_real
  • exponential_distribution
  • normal_distribution
  • gamma_distribution

Wenn Sie Ihr Potenzgesetz Verteilung definieren, sollten Sie in der Lage sein, es mit dem bestehenden Generatoren und Motoren zu stecken. Das Buch Die C ++ Standard Library Extensions von Pete Becker hat ein großes Kapitel über <random>.

Hier ist ein Artikel darüber, wie andere Distributionen erstellen (mit Beispielen für Cauchy, Chi -squared, Student t und Snedecor F)

Ich wollte nur eine aktuelle Simulation als Ergänzung zur Durchführung der (zu Recht) akzeptierten Antwort. Obwohl in R, ist der Code so einfach wie zu sein (pseudo) -pseudo-Code.

Ein winziger Unterschied zwischen der Wolfram MathWorld Formel in der akzeptierten Antwort und andere, vielleicht mehr gemeinsam ist Gleichungen die Tatsache, dass die Potenzgesetz Exponent n (die typischerweise als alpha bezeichnet) keine explizite negatives Vorzeichen tragen. So ist der gewählte Alpha-Wert hat, negativ zu sein, und in der Regel zwischen 2 und 3.

x0 und x1 für die untere und obere Grenze der Verteilung stehen.

Also hier ist es: 

x1 = 5           # Maximum value
x0 = 0.1         # It can't be zero; otherwise X^0^(neg) is 1/0.
alpha = -2.5     # It has to be negative.
y = runif(1e5)   # Number of samples
x = ((x1^(alpha+1) - x0^(alpha+1))*y + x0^(alpha+1))^(1/(alpha+1))
hist(x, prob = T, breaks=40, ylim=c(0,10), xlim=c(0,1.2), border=F, 
col="yellowgreen", main="Power law density")
lines(density(x), col="chocolate", lwd=1)
lines(density(x, adjust=2), lty="dotted", col="darkblue", lwd=2)

oder in logarithmischem Maßstab aufgetragen: 

h = hist(x, prob=T, breaks=40, plot=F)
     plot(h$count, log="xy", type='l', lwd=1, lend=2, 
     xlab="", ylab="", main="Density in logarithmic scale")

Hier ist die Zusammenfassung der Daten: 

> summary(x)
   Min.   1st Qu.  Median    Mean   3rd Qu.    Max. 
  0.1000  0.1208  0.1584    0.2590  0.2511   4.9388
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top