java - repetir - ¿Por qué este valor aleatorio tiene una distribución 25/75 en lugar de 50/50?

numeros aleatorios en java netbeans

Question

Editar: Entonces, básicamente, lo que estoy tratando de escribir es un hash de 1 bit para el double .

Quiero asignar un double a true o false con una probabilidad de 50/50. Para eso escribí un código que selecciona algunos números aleatorios (solo como ejemplo, quiero usar esto en datos con regularidades y aún así obtener un resultado 50/50) , verifica su último bit e incrementa y si es 1, o n si es 0

Sin embargo, este código constantemente produce 25% y 75% n . ¿Por qué no es 50/50? ¿Y por qué una distribución tan extraña pero directa (1/3)?

public class DoubleToBoolean {
    @Test
    public void test() {

        int y = 0;
        int n = 0;
        Random r = new Random();
        for (int i = 0; i < 1000000; i++) {
            double randomValue = r.nextDouble();
            long lastBit = Double.doubleToLongBits(randomValue) & 1;
            if (lastBit == 1) {
                y++;
            } else {
                n++;
            }
        }
        System.out.println(y + " " + n);
    }
}

Salida de ejemplo:

250167 749833

Answer 1

De los docs :

El método nextDouble lo implementa la clase Random como si fuera:

public double nextDouble() {
  return (((long)next(26) << 27) + next(27))
      / (double)(1L << 53);
}

Pero también establece lo siguiente (énfasis mío):

[En versiones anteriores de Java, el resultado se calculaba incorrectamente como:

 return (((long)next(27) << 27) + next(27))
     / (double)(1L << 54);

Esto podría parecer equivalente, si no mejor, pero de hecho introdujo una gran no uniformidad debido al sesgo en el redondeo de los números de coma flotante: era tres veces más probable que el bit de bajo orden del significado fuera 0 que eso sería 1 ! Esta no uniformidad probablemente no importa mucho en la práctica, pero luchamos por la perfección.]

Esta nota ha estado allí desde Java 5 al menos (los documentos para Java <= 1.4 están detrás de un muro de inicio de sesión, demasiado flojo para verificar). Esto es interesante, porque el problema aparentemente todavía existe incluso en Java 8. ¿Quizás la versión "fija" nunca fue probada?

Answer 2

Este resultado no me sorprende dado cómo se representan los números de coma flotante. Supongamos que tenemos un tipo de coma flotante muy corto con solo 4 bits de precisión. Si generamos un número aleatorio entre 0 y 1, distribuido uniformemente, habría 16 valores posibles:

0.0000
0.0001
0.0010
0.0011
0.0100
...
0.1110
0.1111

Si así es como se veían en la máquina, podría probar el bit de bajo orden para obtener una distribución 50/50. Sin embargo, los flotadores IEEE se representan como una potencia de 2 veces una mantisa; Un campo en el flotador es la potencia de 2 (más un desplazamiento fijo). La potencia de 2 se selecciona de modo que la parte "mantisa" sea siempre un número> = 1.0 y <2.0. Esto significa que, en efecto, los números que no sean 0.0000 se representarían así:

0.0001 = 2^(-4) x 1.000
0.0010 = 2^(-3) x 1.000
0.0011 = 2^(-3) x 1.100
0.0100 = 2^(-2) x 1.000
... 
0.0111 = 2^(-2) x 1.110
0.1000 = 2^(-1) x 1.000
0.1001 = 2^(-1) x 1.001
...
0.1110 = 2^(-1) x 1.110
0.1111 = 2^(-1) x 1.111

(El 1 antes del punto binario es un valor implícito; para flotantes de 32 y 64 bits, en realidad no se asigna ningún bit para mantener este 1 ).

Pero mirar lo anterior debería demostrar por qué, si convierte la representación en bits y observa el bit bajo, obtendrá cero el 75% del tiempo. Esto se debe a todos los valores inferiores a 0.5 (binario 0.1000 ), que es la mitad de los valores posibles, con sus mantisias desplazadas, lo que hace que aparezca 0 en el bit bajo. La situación es esencialmente la misma cuando la mantisa tiene 52 bits (sin incluir el 1 implícito) que un double .

(En realidad, como sugirió @sneftel en un comentario, podríamos incluir más de 16 valores posibles en la distribución, generando:

0.0001000 with probability 1/128
0.0001001 with probability 1/128
...
0.0001111 with probability 1/128
0.001000  with probability 1/64
0.001001  with probability 1/64
...
0.01111   with probability 1/32 
0.1000    with probability 1/16
0.1001    with probability 1/16
...
0.1110    with probability 1/16
0.1111    with probability 1/16

Pero no estoy seguro de que sea el tipo de distribución que la mayoría de los programadores esperarían, por lo que probablemente no valga la pena. Además, no gana mucho cuando los valores se utilizan para generar enteros, como suelen ser los valores aleatorios de punto flotante).

Answer 3

Porque nextDouble funciona así: ( source )

public double nextDouble()
{
    return (((long) next(26) << 27) + next(27)) / (double) (1L << 53);
}

next(x) hace x bits aleatorios.

Ahora, ¿por qué importa esto? Debido a que aproximadamente la mitad de los números generados por la primera parte (antes de la división) son inferiores a 1L << 52 , y por lo tanto su significado no llena por completo los 53 bits que podría llenar, lo que significa que el bit menos significativo del significado es siempre cero para esos.

Debido a la cantidad de atención que está recibiendo, aquí hay una explicación adicional de cómo se ve realmente un double en Java (y muchos otros lenguajes) y por qué importaba en esta pregunta.

Básicamente, un double ve así: ( source )

Un detalle muy importante que no se ve en esta imagen es que los números están "normalizados" ^{1, de} modo que la fracción de 53 bits comienza con un 1 (al elegir el exponente tal que sea así), que luego se omite 1. Es por eso que la imagen muestra 52 bits para la fracción (significado), pero efectivamente tiene 53 bits.

La normalización significa que si en el código para nextDouble el bit 53, ese bit es el primer 1 implícito y desaparece, y los otros 52 bits se copian literalmente al significado del double resultante. Sin embargo, si ese bit no está establecido, los bits restantes deben desplazarse hacia la izquierda hasta que se establezca.

En promedio, la mitad de los números generados caen en el caso en que el significado no se desplazó a la izquierda (y aproximadamente la mitad tiene un 0 como su bit menos significativo), y la otra mitad se desplaza al menos 1 (o es simplemente completamente cero), por lo que su bit menos significativo siempre es 0.

1: no siempre, claramente no se puede hacer para cero, que no tiene el 1. más alto. Estos números se llaman números denormales o subnormales, ver wikipedia: número denormal .