Numeri casuali basati su una probabilità

Question

Ho problemi a generare numeri casuali che non seguono una distribuzione uniforme discreta.

Ad esempio, supponiamo di avere 5 numeri (per mantenerlo semplice), una probabilità che il numero k generato sia k/15. (K = 1 a 5)

mia idea è di generare un numero casuale j utilizzando rand(), e se questo numero j è:

1 => quindi il numero 1 viene generato

2 o 3 => num 2

4 o 5 o 6 => num 3

7 o 8 o 9 o 10 => NUM 4

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

Ridimensiona ora a generare 1-10, 1-100, 1-1000. Funziona nel modo in cui lo intendo? Ho costruito un ciclo che fa praticamente ogni volta che un numero deve essere generato, penso che sia probabilmente inefficiente dal momento che sale fino a trovare il numero j generato in uno degli intervalli ... Quale potrebbe essere un modo migliore per fare questo?

EDIT: o forse creare un array una volta con i numeri corretti e quindi estrarre con rand() soluzione migliore?

Answer 1

Si consideri che la somma s di numeri interi da 1 a n è s = n * (n + 1)/2. Risolvere per n per ottenere n = (± sqrt(8*s + 1) - 1)/2. Possiamo ignorare la radice quadrata negativa, poiché sappiamo che n è positivo. Quindi n = (sqrt(8*s + 1) - 1)/2.

Quindi, collegare interi per s tra 1 e 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 

Se prendiamo il soffitto di ogni calcolato n (il più piccolo intero non inferiore a n), otteniamo questo:

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 

In questo modo è possibile passare dalla distribuzione uniforme alla distribuzione in spazio costante e tempo costante (nessuna iterazione e nessuna tabella precompilato):

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

N.B. Questo si basa su sqrt dando un risultato esatto per un quadrato perfetto (ad es.restituire esattamente 7 dato esattamente 49). Questo è normalmente un presupposto sicuro, perché IEEE 754 richiede l'arrotondamento esatto delle radici quadrate.

IEEE 754 doppi possono rappresentare tutti gli interi da 1 a 2^53 (e molti più grandi interi, ma non contigui dopo 2^53). Quindi questa funzione dovrebbe funzionare correttamente per tutti s da 1 a floor((2^53 - 1)/8) = 1125899906842623.

Answer 2

Si può approfittare del fatto curioso aritmetica che:

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

o semplificato:

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

Ciò consente di evitare di memorizzare la matrice.

Answer 3

ti sembra di essere sulla strada giusta, ma C++ ha già una distribuzione di numeri casuali specializzato per questo, 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"; 
    } 
} 

demo online: http://ideone.com/jU1ll