Números aleatorios basados ​​en una probabilidad

Question

Tengo problemas para generar números aleatorios que no siguen una distribución uniforme discreta.

Entonces, por ejemplo, supongo que tengo 5 números (para simplificar), la probabilidad de que se genere el número k sería k/15. (K = 1 a 5)

Mi idea es generar un número aleatorio j usando rand(), y si este número j es:

1 => entonces se genera número 1

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

Ahora escala esto para generar 1-10, 1-100, 1-1000. ¿Funciona esto de la forma en que lo intento? He construido un ciclo que hace esto cada vez que se necesita generar un número, creo que probablemente sea ineficiente, ya que aumenta hasta que encuentra el número j generado en uno de los rangos ... ¿Cuál podría ser una mejor manera? ¿para hacer esto?

EDITAR: o tal vez crear una matriz una vez con los números adecuados y luego sacar con rand() una mejor solución?

Answer 1

consideran que la suma s de números enteros de 1 a n es s = n * (n + 1)/2. Resuelva para n para obtener n = (± sqrt(8*s + 1) - 1)/2. Podemos ignorar la raíz cuadrada negativa, ya que sabemos que n es positivo. Por lo tanto, n = (sqrt(8*s + 1) - 1)/2.

Así, enchufar enteros para s entre 1 y 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 

Si tomamos el techo de cada calcula n (el menor entero no inferior a n), obtenemos lo siguiente:

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 

Así puede pasar de la distribución uniforme a su distribución en espacio constante y tiempo constante (sin iteración y sin tablas precalculadas):

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

N.B. Esto se basa en sqrt dando un resultado exacto para un cuadrado perfecto (p.regresando exactamente 7 dado exactamente 49). Esto normalmente es una suposición segura, porque IEEE 754 requiere un redondeo exacto de las raíces cuadradas.

Los dobles de IEEE 754 pueden representar todos los enteros de 1 a 2^53 (y muchos enteros más grandes, pero no contiguos después de 2^53). Por lo tanto, esta función debería funcionar correctamente para todos s de 1 a floor((2^53 - 1)/8) = 1125899906842623.

Answer 2

Usted puede aprovechar el hecho curioso de que la aritmética:

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

o simplificado:

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

Esto le permite evitar el almacenamiento de la matriz.

Answer 3

usted parece estar en el camino correcto, pero C++ ya tiene una distribución de números aleatorios especializado para que, 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"; 
    } 
} 

demostración en línea: http://ideone.com/jU1ll