Cómo obtener números aleatorios con el generador equivocado

Question

Pregunta: Supongamos que tiene un generador de números aleatorios randn() que devuelve un número aleatorio distribuido uniformemente entre 0 y n-1. Dado cualquier número m, escriba un generador de números aleatorios que devuelva un número aleatorio distribuido uniformemente entre 0 y m-1.

Mi respuesta:

-(int)randm() { 
    int k=1; 
    while (k*n < m) { 
     ++k; 
    } 
    int x = 0; 
    for (int i=0; i<k; ++i) { 
     x += randn(); 
    } 
    if (x < m) { 
     return x; 
    } else { 
     return randm(); 
    } 
} 

Es esto correcto?

Answer 1

Estás cerca, pero el problema con tu respuesta es que hay más de una forma de escribir un número como suma de otros dos números.

Si m<n, entonces esto funciona porque los números 0,1,...,m-1 aparecen con la misma probabilidad, y el algoritmo termina casi seguramente.

Esta respuesta no funciona en general porque hay más de una forma de escribir un número como suma de otros dos números. Por ejemplo, solo hay una forma de obtener 0, pero hay muchas maneras de obtener m/2, por lo que las probabilidades no serán iguales.

Ejemplo: n = 2 y m=3

0 = 0+0 
1 = 1+0 or 0+1 
2 = 1+1 

por lo que la distribución de probabilidad de su método es

P(0)=1/4 
P(1)=1/2 
P(2)=1/4 

que no es uniforme.

---

Para solucionar esto, puede utilizar factorización única. Escriba m en la base n, siguiendo el mayor exponente necesario, digamos e. Luego, encuentre el mayor múltiplo de m que sea menor que n^e, llámelo k. Finalmente, genere e números con randn(), tómelos como la expansión base n de algún número x, si x < k*m, devuelva x, de lo contrario intente de nuevo.

Suponiendo que m < n^2, entonces

int randm() { 

    // find largest power of n needed to write m in base n 
    int e=0; 
    while (m > n^e) { 
     ++e; 
    } 

    // find largest multiple of m less than n^e 
    int k=1; 
    while (k*m < n^2) { 
     ++k 
    } 
    --k; // we went one too far 

    while (1) { 
     // generate a random number in base n 
     int x = 0; 
     for (int i=0; i<e; ++i) { 
      x = x*n + randn(); 
     } 
     // if x isn't too large, return it x modulo m 
     if (x < m*k) 
      return (x % m); 
    } 
} 

Answer 2

no es correcto.

Está agregando números aleatorios uniformes, lo que no produce un resultado uniformemente aleatorio. Diga n = 2 ym = 3, entonces los valores posibles para x son 0 + 0, 0 + 1, 1 + 0, 1 + 1. Por lo tanto, tiene el doble de posibilidades de obtener 1 que de obtener 0 o 2.

Lo que necesita hacer es escribir m en la base n, y luego generar 'dígitos' de la representación base-n del azar número. Cuando tenga el número completo, debe verificar si es menor que m. Si es así, entonces has terminado. Si no es así, entonces necesitas comenzar de nuevo.

Answer 3

La suma de dos generadores de números aleatorios uniformes no se genera de manera uniforme. Por ejemplo, la suma de dos dados es más probable que sea 7 que 12, porque para obtener 12 necesitas lanzar dos sixes, mientras que puedes obtener 7 como 1 + 6 o 6 + 1 o 2 + 5 o 5 + 2 o ...

Suponiendo que randn() devuelve un número entero entre 0 y n - 1, n * randn() + randn() se distribuye uniformemente entre 0 y n * n - 1, por lo que puede aumentar su rango. Si randn() devuelve un número entero entre 0 yk * m + j - 1, llámelo repetidamente hasta que obtenga un número < = k * m - 1, y luego divida el resultado por k para obtener un número uniformemente distribuido entre 0 y m -1.

Answer 4

Suponiendo que n y m son enteros positivos, ¿no funcionaría el algoritmo estándar de escalado?

return (int)((float)randn() * m/n);