Por que esse valor aleatório tem uma distribuição 25/75 em vez de 50/50?

139

Edit: Então, basicamente, o que estou tentando escrever é um hash de 1 bit double.

Quero mapear uma doublepara trueou falsecom uma chance de 50/50. Para isso, escrevi um código que seleciona alguns números aleatórios (como exemplo, quero usar isso em dados com regularidades e ainda obter um resultado 50/50) , yverifico seu último bit e incrementa se for 1 ou nse for 0

No entanto, esse código resulta constantemente em 25% ye 75% n. Por que não é 50/50? E por que uma distribuição tão estranha, mas direta (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);
    }
}

Exemplo de saída:

250167 749833
gvlasov
fonte
43
Eu realmente espero que a resposta seja algo fascinante sobre a geração aleatória de variáveis ​​de ponto flutuante, em vez de "LCG tem baixa entropia nos bits baixos".
Sneftel
4
Estou muito curioso, qual é o propósito de um "hash de 1 bit para dobro"? Eu realmente não consigo pensar em nenhuma aplicação legítima de tal exigência.
corsiKa
3
@corsiKa Em cálculos de geometria, geralmente há dois casos que procuramos escolher entre duas respostas possíveis (por exemplo, é o ponto à esquerda ou à direita da linha?) e, às vezes, apresenta o terceiro caso degenerado (o ponto é diretamente na linha), mas você só tem duas respostas disponíveis; portanto, você deve escolher pseudo-aleatoriamente uma das respostas disponíveis nesse caso. A melhor maneira de pensar é usar um hash de 1 bit de um dos valores duplos dados (lembre-se, esses são cálculos de geometria, portanto, há dobras em todo o lugar).
gvlasov
2
@corsiKa (comentário dividido em dois porque é muito longo) Poderíamos começar com algo mais simples doubleValue % 1 > 0.5, mas isso seria muito grosseiro, pois pode introduzir regularidades visíveis em alguns casos (todos os valores estão dentro do intervalo 1). Se isso é muito granular, provavelmente deveríamos tentar intervalos menores, como doubleValue % 1e-10 > 0.5e-10? Bem, sim. E tomar apenas o último pedaço como um hash de a doubleé o que acontece quando você segue essa abordagem até o fim, com o módulo menos possível.
gvlasov
1
O @kmote ainda terá o bit menos significativo e o outro não o compensa - na verdade, ele também é direcionado para zero (mas menos), pelo mesmo motivo. Portanto, a distribuição seria de cerca de 50, 12,5, 25, 12,5. (lastbit & 3) == 0iria funcionar, por mais estranho que seja.
Harold

Respostas:

165

Porque nextDouble funciona assim: ( fonte )

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

next(x)faz xbits aleatórios.

Agora, por que isso importa? Como cerca da metade dos números gerados pela primeira parte (antes da divisão) é menor 1L << 52e, portanto, seu significado não preenche inteiramente os 53 bits que ele poderia preencher, significando que o bit menos significativo do significando é sempre zero para eles.


Devido à quantidade de atenção que está recebendo, aqui estão algumas explicações extras sobre o que doublerealmente é um Java (e muitas outras linguagens) e por que isso importava nesta pergunta.

Basicamente, a doubleaparência é a seguinte: ( fonte )

layout duplo

Um detalhe muito importante que não é visível nesta figura é que os números são "normalizados" 1, de modo que a fração de 53 bits começa com 1 (escolhendo o expoente tal que é assim), que 1 é omitido. É por isso que a imagem mostra 52 bits para a fração (significando), mas existem efetivamente 53 bits nela.

A normalização significa que, se o código nextDoubledo 53º bit estiver definido, esse bit será o líder implícito 1 e desaparecerá, e os outros 52 bits serão copiados literalmente para o significando do resultado double. Se esse bit não estiver definido, no entanto, os bits restantes deverão ser deslocados para a esquerda até que sejam definidos.

Em média, metade dos números gerados se enquadra no caso em que o significando não foi alterado para a esquerda (e cerca de metade deles tem 0 como o bit menos significativo), e a outra metade é alterada em pelo menos 1 (ou é apenas completamente zero), então o bit menos significativo é sempre 0.

1: nem sempre, claramente isso não pode ser feito para zero, que não possui o mais alto 1. Esses números são chamados de números anormais ou subnormais, consulte a Wikipedia: número denormal .

harold
fonte
16
Viva! Apenas o que eu estava esperando.
Sneftel
3
@Matt Presumivelmente, é uma otimização de velocidade. A alternativa seria gerar o expoente com uma distribuição geométrica e depois a mantissa separadamente.
Sneftel
7
@ Matt: Defina "melhor". random.nextDouble()normalmente é o "melhor" caminho para o que se destina, mas a maioria das pessoas não está tentando produzir um hash de 1 bit a partir do dobro aleatório. Você está procurando distribuição uniforme, resistência à criptoanálise ou o quê?
precisa
1
Essa resposta sugere que, se OP tivesse multiplicado o número aleatório por 2 ^ 53 e verificado se o número inteiro resultante era ímpar, haveria uma distribuição 50/50.
rici
4
@ The111 diz aqui que nextdeve retornar um int, para que possa ter apenas até 32 bits de qualquer maneira #
harold
48

Dos documentos :

O método nextDouble é implementado pela classe Random como se por:

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

Mas também afirma o seguinte (ênfase minha):

[Nas versões anteriores do Java, o resultado era calculado incorretamente como:

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

Isso pode parecer equivalente, se não melhor, mas, de fato, introduziu uma grande não uniformidade devido ao viés no arredondamento dos números de ponto flutuante: era três vezes mais provável que o bit de ordem inferior do significando fosse 0. do que isso seria 1 ! Essa não uniformidade provavelmente não importa muito na prática, mas buscamos a perfeição.]

Esta observação existe desde o Java 5 pelo menos (os documentos para Java <= 1.4 estão atrás de uma parede de login, com preguiça de verificar). Isso é interessante, porque o problema aparentemente ainda existe até no Java 8. Talvez a versão "fixa" nunca tenha sido testada?

Thomas
fonte
4
Estranho. Acabei de reproduzir isso no Java 8. #
aioobe 23/12/14
1
Agora isso é interessante, porque acabei de argumentar que o viés ainda se aplica ao novo método. Estou errado?
Harold
3
@harold: Não, acho que você está certo e quem tentou corrigir esse viés pode ter cometido um erro.
Thomas
6
@harold Hora de enviar um email para os caras do Java.
Daniel
8
"Talvez a versão fixa nunca tenha sido testada?" Na verdade, ao reler isso, acho que o documento tratava de um problema diferente. Observe que ele menciona o arredondamento , o que sugere que eles não consideraram o problema "três vezes mais provável" diretamente, mas sim que isso leva a uma distribuição não uniforme quando os valores são arredondados . Observe que, na minha resposta, os valores que listo são distribuídos uniformemente, mas o bit de ordem inferior, representado no formato IEEE, não é uniforme. Eu acho que o problema que eles resolveram tinha a ver com a uniformidade geral, não com a uniformidade do bit baixo.
ajb
33

Esse resultado não me surpreende, dado que os números de ponto flutuante são representados. Suponhamos que tivéssemos um tipo de ponto flutuante muito curto, com apenas 4 bits de precisão. Se gerássemos um número aleatório entre 0 e 1, distribuído uniformemente, haveria 16 valores possíveis:

0.0000
0.0001
0.0010
0.0011
0.0100
...
0.1110
0.1111

Se era assim que pareciam na máquina, você poderia testar o bit de ordem baixa para obter uma distribuição 50/50. No entanto, os flutuadores IEEE são representados como uma potência de 2 vezes uma mantissa; um campo no flutuador é a potência de 2 (mais um deslocamento fixo). A potência de 2 é selecionada para que a parte "mantissa" seja sempre um número> = 1.0 e <2.0. Isso significa que, na verdade, outros números que 0.0000não seriam representados assim:

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

( 1Antes do ponto binário é um valor implícito; para flutuações de 32 e 64 bits, nenhum bit é realmente alocado para reter isso 1.)

Mas observar o acima exposto deve demonstrar por que, se você converter a representação em bits e observar o bit baixo, receberá zero 75% do tempo. Isso ocorre devido a todos os valores menores que 0,5 (binários 0.1000), que são metade dos valores possíveis, com as mantissas deslocadas, fazendo com que 0 apareça no bit mais baixo. A situação é essencialmente a mesma quando a mantissa possui 52 bits (não incluindo o 1 implícito) como doublefaz.

(Na verdade, como @sneftel sugeriu em um comentário, poderíamos incluir mais de 16 valores possíveis na distribuição, gerando:

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

Mas não tenho certeza de que seja o tipo de distribuição que a maioria dos programadores esperaria, por isso provavelmente não vale a pena. Além disso, não ganha muito quando os valores são usados ​​para gerar números inteiros, como costumam ser os valores aleatórios de ponto flutuante.)

ajb
fonte
5
Usar ponto flutuante para obter bits aleatórios / bytes / qualquer coisa me faz estremecer de qualquer maneira. Mesmo para distribuições aleatórias entre 0 e n, temos melhores alternativas (veja arc4random_uniform) do que random * n…
mirabilos