Zufallszahlen basierend auf einer Wahrscheinlichkeit

Question

Ich habe Probleme beim Erzeugen von Zufallszahlen, die keiner diskreten Gleichverteilung folgen.

Also sagen wir zum Beispiel, dass ich 5 Nummern habe (um es einfach zu halten), eine Wahrscheinlichkeit, dass die Zahl k erzeugt wird, wäre k/15. (K = 1 bis 5)

Meine Idee ist, eine Zufallszahl J mit Hilfe rand() zu erzeugen, und wenn diese Zahl j ist:

1 => dann Nummer 1 erzeugt

2 oder 3 => num 2

4 oder 5 oder 6 => num 3

7 oder 8 oder 9 oder 10 => num 4

11 oder 12 oder 13 oder 14 oder 15 => num 5

Skalieren Sie dies nun auf 1-10, 1-100, 1-1000. Funktioniert das so, wie ich es mir vorstelle? Ich habe eine Schleife konstruiert, die das jedes Mal, wenn eine Zahl generiert werden muss, ziemlich genau macht. Ich denke, dass sie wahrscheinlich ineffizient ist, da sie weitergeht, bis sie die j-Nummer in einem der Bereiche findet ... Was könnte ein besserer Weg sein um dies zu tun?

EDIT: oder vielleicht ein Array einmal mit den richtigen Zahlen erstellen und dann mit Rand ziehen() bessere Lösung?

Answer 1

Bedenken Sie, dass die Summe s von ganzen Zahlen von 1 zu n ist s = n * (n + 1)/2. Lösen Sie für n, um n = (± sqrt(8*s + 1) - 1)/2 zu erhalten. Wir können die negative Quadratwurzel ignorieren, wie wir wissen n ist positiv. Also n = (sqrt(8*s + 1) - 1)/2.

Also, in ganzen Zahlen für s Verstopfen zwischen 1 und 15:

s n 
01 1.000000 
02 1.561553 
03 2.000000 
04 2.372281 
05 2.701562 
06 3.000000 
07 3.274917 
08 3.531129 
09 3.772002 
10 4.000000 
11 4.216991 
12 4.424429 
13 4.623475 
14 4.815073 
15 5.000000 

Wenn wir die Decke jeden Takes berechnet n (die kleinste ganze Zahl von nicht weniger als n), wir diese:

s n 
01 1 
02 2 
03 2 
04 3 
05 3 
06 3 
07 4 
08 4 
09 4 
10 4 
11 5 
12 5 
13 5 
14 5 
15 5 

So können Sie von der gleichmäßigen Verteilung zu Ihrer Verteilung in konstanten Raum und konstanter Zeit gehen (keine Iteration und keine vorberechneten Tabellen):

double my_distribution_from_uniform_distribution(double s) { 
    return ceil((sqrt(8*s + 1) - 1)/2); 
} 

N.B. Dies beruht auf sqrt, was ein genaues Ergebnis für ein perfektes Quadrat ergibt (z.exakt 7 zurückgegeben genau 49). Dies ist normalerweise eine sichere Annahme, da IEEE 754 eine exakte Rundung der Quadratwurzeln erfordert.

IEEE 754 doubles kann alle Ganzzahlen von 1 bis 2^53 (und viele größere Ganzzahlen, aber nicht zusammenhängend nach 2^53) darstellen. Diese Funktion sollte also für alle s von 1 bis floor((2^53 - 1)/8) = 1125899906842623 korrekt funktionieren.

Answer 2

Sie können diesen Vorteil der Neugierigen arithmetische Tatsache nehmen:

S(n) = 1 + 2 + 3 + ... + (n - 1) + n 

oder vereinfacht:

S(n) = n * (n + 1)/2 

Auf diese Weise können Sie das Array vermeiden zu speichern.

Answer 3

Sie scheinen auf dem richtigen Weg zu sein, aber C++ hat bereits eine spezielle Zufallszahlenverteilung für die, std::discrete_distribution

#include <iostream> 
#include <vector> 
#include <map> 
#include <random> 

int main() 
{ 
    std::random_device rd; 
    std::mt19937 gen(rd()); 

    // list of probabilities  
    std::vector<double> p = {0, 1.0/15, 2.0/15, 3.0/15, 4.0/15, 5.0/15}; 
    // could also be min, max, and a generating function (n/15 in your case?) 
    std::discrete_distribution<> d(p.begin(), p.end()); 

    // some statistics 
    std::map<int, int> m; 
    for(int n=0; n<10000; ++n) { 
     ++m[d(gen)]; 
    } 
    for(auto p : m) { 
     std::cout << p.first << " generated " << p.second << " times\n"; 
    } 
} 

Online-Demo: http://ideone.com/jU1ll