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

139

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

Quiero mapear un doubleto trueo falsecon 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 incrementos ysi es 1, o nsi es 0.

Sin embargo, este código constantemente produce 25% yy 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
gvlasov
fuente
43
Realmente espero que la respuesta sea algo fascinante sobre la generación aleatoria de variables de punto flotante, en lugar de "LCG tiene baja entropía en los bits bajos".
Sneftel
44
Tengo mucha curiosidad, ¿cuál es el propósito de un "hash de 1 bit para doble"? En serio, no puedo pensar en una aplicación legítima de tal requisito.
corsiKa
3
@corsiKa En los cálculos de geometría, a menudo hay dos casos que buscamos para elegir entre dos posibles respuestas (por ejemplo, ¿apunta hacia la izquierda o hacia la derecha de la línea?), y a veces introduce el tercer caso degenerado (el punto es justo en la línea), pero solo tiene dos respuestas disponibles, por lo que debe elegir pseudoaleatoriamente una de las respuestas disponibles en ese caso. La mejor manera en que puedo pensar es tomar un hash de 1 bit de uno de los valores dobles dados (recuerde, esos son cálculos de geometría, por lo que hay dobles por todas partes).
gvlasov
2
@corsiKa (comentario dividido en dos porque es demasiado largo) Podríamos comenzar en algo más simple doubleValue % 1 > 0.5, pero eso sería demasiado grano ya que puede introducir regularidades visibles en algunos casos (todos los valores están dentro del rango de longitud 1). Si eso es demasiado de grano grueso, ¿deberíamos intentar rangos más pequeños, como doubleValue % 1e-10 > 0.5e-10? Bueno, sí. Y tomar solo el último bit como hash de a doublees lo que sucede cuando sigues este enfoque hasta el final, con el mínimo módulo posible.
gvlasov
1
@kmote, entonces todavía tendría el bit menos significativo fuertemente sesgado, y el otro bit no lo compensa, de hecho, también está sesgado hacia cero (pero menos), exactamente por la misma razón. Entonces la distribución sería aproximadamente 50, 12.5, 25, 12.5. (lastbit & 3) == 0funcionaría sin embargo, por extraño que sea.
Harold

Respuestas:

165

Porque nextDouble funciona así: ( fuente )

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

next(x)hace xbits al azar.

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 menores 1L << 52y, 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 doublese ve realmente un Java (y muchos otros lenguajes) y por qué importaba en esta pregunta.

Básicamente, se doubleve así: ( fuente )

doble diseño

Un detalle muy importante que no se ve en esta imagen es que los números están "normalizados" 1 de tal manera que la fracción de 53 bits comienza con un 1 (al elegir el exponente de modo 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 nextDoubleel bit 53 está establecido, ese bit es el primer 1 implícito y desaparece, y los otros 52 bits se copian literalmente al significado del resultado double. 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 el 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 por 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 más alto 1. Estos números se llaman números denormales o subnormales, vea wikipedia: número denormal .

harold
fuente
16
¡Hurra! Justo lo que esperaba.
Sneftel
3
@ Matt Presumiblemente es una optimización de velocidad. La alternativa sería generar el exponente con una distribución geométrica, y luego la mantisa por separado.
Sneftel
77
@ Matt: Definir "mejor". random.nextDouble()suele ser la "mejor" forma para lo que está destinado, pero la mayoría de las personas no intentan producir un hash de 1 bit a partir de su doble aleatorio. ¿Está buscando una distribución uniforme, resistencia al criptoanálisis o qué?
StriplingWarrior
1
Esta respuesta sugiere que si OP hubiera multiplicado el número aleatorio por 2 ^ 53 y verificara si el número entero resultante era impar, habría habido una distribución 50/50.
rici
44
@ The111 dice aquí que nextdebe devolver un int, por lo que solo puede tener hasta 32 bits de todos modos
harold
48

De los documentos :

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 nos esforzamos 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 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?

Thomas
fuente
44
Extraño. Acabo de reproducir esto en Java 8.
aioobe
1
Ahora eso es interesante, porque acabo de argumentar que el sesgo todavía se aplica al nuevo método. ¿Me equivoco?
Harold
3
@harold: No, creo que tienes razón y quien haya intentado corregir este sesgo podría haber cometido un error.
Thomas
66
@harold Hora de enviar un correo electrónico a los chicos de Java.
Daniel
8
"¿Quizás la versión fija nunca fue probada?" En realidad, al releer esto, creo que el documento fue sobre un problema diferente. Tenga en cuenta que menciona el redondeo , lo que sugiere que no consideraron el problema "tres veces más probable" como el problema, directamente, sino que esto conduce a una distribución no uniforme cuando los valores se redondean . Tenga en cuenta que en mi respuesta, los valores que enumero están distribuidos uniformemente, pero el bit de orden inferior como se representa en formato IEEE no es uniforme. Creo que el problema que solucionaron tenía que ver con la uniformidad general, no con la uniformidad del bit bajo.
ajb
33

Este resultado no me sorprende dado cómo se representan los números de punto 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 0.0000no sean representados 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 1antes 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 esto 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, ya que sus mantisias se desplazaron y causaron que 0 aparezca en el bit bajo. La situación es esencialmente la misma cuando la mantisa tiene 52 bits (sin incluir el 1 implícito) como lo doublehace.

(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).

ajb
fuente
55
Usar coma flotante para obtener bits / bytes / cualquier cosa al azar me hace estremecer de todos modos. Incluso para distribuciones aleatorias entre 0 yn, tenemos mejores alternativas (mira arc4random_uniform) que random * n ...
mirabilos