Liczby losowe na podstawie prawdopodobieństwa

Question

Mam problemy z generowaniem liczb losowych, które nie są zgodne z jednolitą dystrybucją dyskretną.

Załóżmy na przykład, że mam 5 liczb (aby zachować prostotę), prawdopodobieństwo wygenerowania liczby k będzie k/15. (K = 1 do 5)

Mój pomysł jest generowanie liczb losowych j użyciem rand(), a jeżeli ta liczba j jest:

1 => następnie numer 1 jest generowany

2 lub 3 => Num 2

4 lub 5 lub 6 => Num 3

7 lub 8 lub 9 lub 10 => Nr 4

11 lub 12 lub 13 lub 14 lub 15 => ilość 5

Teraz zmień skalę, aby wygenerować 1-10, 1-100, 1-1000. Czy to działa tak, jak zamierzam? Skonstruowałem pętlę, która robi to prawie za każdym razem, gdy trzeba wygenerować liczbę, myślę, że to prawdopodobnie nieefektywne, ponieważ rośnie aż do znalezienia liczby j wygenerowanej w jednym z zakresów ... Jaki mógłby być lepszy sposób to zrobić?

EDYCJA: A może po prostu utworzyć tablicę z odpowiednimi numerami, a następnie wyciągnąć z lepszego rozwiązania rand()?

Answer 1

Uważają, że suma s liczb całkowitych od 1 to n to s = n * (n + 1)/2. Rozwiąż dla n, aby uzyskać n = (± sqrt(8*s + 1) - 1)/2. Możemy zignorować ujemny pierwiastek kwadratowy, ponieważ wiemy, że n jest dodatnie. Tak więc n = (sqrt(8*s + 1) - 1)/2.

Więc podłączając liczb dla s między 1 i 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 

Jeżeli weźmiemy pod uwagę pułap każdy obliczane n (najmniejszą liczbę całkowitą nie mniejszą niż n), otrzymujemy w ten sposób:

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 

W ten sposób można przejść z rozkładu jednolitego do dystrybucji w stałej przestrzeni i stałym czasie (bez iteracji i bez wstępnie obliczonych tabel):

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

N.B. To opiera się na sqrt, dając dokładny wynik dla idealnego kwadratu (np.zwracając dokładnie 7 podanych dokładnie 49). Jest to zwykle bezpieczne założenie, ponieważ IEEE 754 wymaga dokładnego zaokrąglenia pierwiastków kwadratowych.

Podsumowania IEEE 754 mogą reprezentować wszystkie liczby całkowite od 1 do 2^53 (i wiele większych liczb całkowitych, ale nie sąsiednie po 2^53). Tak więc ta funkcja powinna działać poprawnie dla wszystkich s od 1 do floor((2^53 - 1)/8) = 1125899906842623.

Answer 2

Można skorzystać z faktu, że ciekawy arytmetycznej:

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

lub uproszczonej:

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

Pozwala to uniknąć przechowywania tablicę.

Answer 3

Wydajesz się być na dobrej drodze, ale C++ ma już wyspecjalizowany losowy rozkład liczb na to, 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 on-line: http://ideone.com/jU1ll