numeros - Artículo 47 de Java efectivo: Conozca y use sus bibliotecas-Ejemplo de método de entero aleatorio defectuoso

random en java del 1 al 10 sin repetir

Question

En el ejemplo que Josh da del método aleatorio defectuoso que genera un número aleatorio positivo con un límite superior dado n , no entiendo los dos defectos que afirma.

El método del libro es:

private static final Random rnd = new Random();

//Common but deeply flawed
static int random(int n) {
    return Math.abs(rnd.nextInt()) % n;
}

• Él dice que si n es una potencia pequeña de 2, la secuencia de números aleatorios que se generan se repetirá después de un corto período de tiempo. ¿Por qué es este el caso? La documentación para Random.nextInt() dice Returns the next pseudorandom, uniformly distributed int value from this random number generator''s sequence. Entonces, ¿no debería ser que si n es un entero pequeño, entonces la secuencia se repetirá, por qué esto solo se aplica a potencias de 2?
• Luego dice que si n no es una potencia de 2, algunos números se devolverán en promedio con más frecuencia que otros. ¿Por qué ocurre esto si Random.nextInt() genera enteros aleatorios que se distribuyen uniformemente? (Él proporciona un fragmento de código que lo demuestra claramente, pero no entiendo por qué este es el caso, y cómo se relaciona esto con que n es una potencia de 2).

Answer 1

Pregunta 1: si n es una potencia pequeña de 2, la secuencia de números aleatorios que se generan se repetirá después de un corto período de tiempo.

Esto no es un corolario de nada de lo que Josh está diciendo; más bien, es simplemente una propiedad conocida de los generadores lineales congruentes . Wikipedia tiene lo siguiente para decir:

Un problema adicional de las LCG es que los bits de orden inferior de la secuencia generada tienen un período mucho más corto que la secuencia en su conjunto si m se establece en una potencia de 2. En general, el n-th dígito menos significativo en la base La representación b de la secuencia de salida, donde b ^k = m para algún entero k, se repite como máximo en el período b ⁿ .

Esto también se nota en el Javadoc :

Se sabe que los generadores de números pseudoaleatorios lineales congruentes, como el implementado por esta clase, tienen períodos cortos en la secuencia de valores de sus bits de orden inferior.

La otra versión de la función, Random.nextInt(int) , Random.nextInt(int) esto utilizando diferentes bits en este caso (el énfasis es mío):

El algoritmo trata el caso en el que n es una potencia de dos especialmente: devuelve el número correcto de bits de orden superior del generador de números pseudoaleatorios subyacente.

Esta es una buena razón para preferir Random.nextInt(int) sobre el uso de Random.nextInt() y hacer su propia transformación de rango.

Pregunta 2: Luego dice que si n no es una potencia de 2, algunos números se devolverán en promedio con mayor frecuencia que otros.

Hay 2 ³² números distintos que pueden ser devueltos por nextInt() . Si intenta colocarlos en n grupos utilizando % n , y n no es una potencia de 2, algunos grupos tendrán más números que otros. Esto significa que algunos resultados se producirán con más frecuencia que otros, aunque la distribución original sea uniforme.

Veamos esto usando números pequeños. Digamos que nextInt() devolvió cuatro resultados equiprobables, 0, 1, 2 y 3. Veamos qué sucede si les aplicamos % 3 :

0 maps to 0
1 maps to 1
2 maps to 2
3 maps to 0

Como puede ver, el algoritmo devolvería 0 dos veces más frecuentemente que cada uno de 1 y 2.

Esto no sucede cuando n es una potencia de dos, ya que una potencia de dos es divisible por la otra. Considere n=2 :

0 maps to 0
1 maps to 1
2 maps to 0
3 maps to 1

Aquí, 0 y 1 ocurren con la misma frecuencia.

Recursos adicionales

Aquí hay algunos recursos adicionales, aunque solo tangencialmente relevantes, relacionados con los LCG:

• Las pruebas espectrales son pruebas estadísticas que se utilizan para evaluar la calidad de los LCG. Lea más here y here .
• Una colección de generadores de números pseudoaleatorios clásicos con estructuras lineales tiene algunos diagramas de dispersión bastante (el generador utilizado en Java se llama DRAND48 ).
• Hay una discussion interesante sobre crypto.SE sobre la predicción de valores del generador de Java.

Answer 2

1) Cuando n es una potencia de 2, rnd % n es equivalente a seleccionar unos pocos bits inferiores del original. Se sabe que los bits de números más bajos generados por el tipo de generadores utilizados por Java son "menos aleatorios" que los bits más altos. Es solo la propiedad de la fórmula utilizada para generar los números.

2) Imagina que el mayor valor posible, devuelto por random() es 10, y n = 7 . Ahora haciendo n % 7 mapea los números 7, 8, 9 y 10 en 0, 1, 2, 3 respectivamente. Por lo tanto, si el número original se distribuye de manera uniforme, el resultado estará fuertemente orientado hacia los números más bajos, ya que aparecerán dos veces más a menudo que 4, 5 y 6. En este caso, esto sucede sin importar si n es una potencia de dos o no, pero si en lugar de 10 elegimos, digamos, 15 (que es 2 ^ 4-1), entonces cualquier n , es decir, una potencia de dos resultaría en una distribución uniforme, porque no habría "exceso" "los números que quedan al final del rango para causar sesgo, porque el número total de valores posibles sería exactamente divisible por el número de residuos posibles.