为什么这个随机值有25/75分布而不是50/50？

Question

编辑:所以基本上我要写的是1位哈希值double.

我想映射double到50/50 true或false50/50的机会.为此,我编写了一些选择随机数的代码(仅作为一个例子,我希望在有规律的数据上使用它并仍然得到50/50的结果),检查它们的最后一位并y在它为1时递增,或者n如果它是0.

但是,此代码不断导致25%y和75%n.为什么不是50/50？为什么这么奇怪,但直截了当(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);
    }
}

示例输出:

250167 749833

Answer 1

因为nextDouble的工作原理如下:( 来源)

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

next(x)使得x随机位.

现在为什么这很重要？因为第一部分(在除法之前)生成的数字的大约一半小于1L << 52,因此它们的有效数并不完全填充它可以填充的53位,这意味着有效数的最低有效位对于那些总是为零.

由于受到了很多关注,这里有一些额外的解释,说明doubleJava(以及许多其他语言)的真实外观以及它在这个问题中的重要性.

基本上,double看起来像这样:( 来源)

在该图中不可见的非常重要的细节是数字被"标准化" ¹,使得53位部分以1开始(通过选择指数使得它是如此),然后省略1.这就是为什么图片显示分数(有效数字)的52位,但实际上有53位.

归一化意味着如果在nextDouble设置第53位的代码中,该位是隐式前导1并且它消失,而其他52位被字面复制到结果的有效位double.但是,如果未设置该位,则必须向左移位剩余的位,直到它置位.

平均而言,生成数字的一半落入有效数据根本没有向左移位的情况下(大约一半数字的最低有效位为0),另一半移动至少1(或者只是完全移位)零)因此它们的最低有效位始终为0.

1:并非总是如此,显然它不能为零做,没有最高1.这些数字称为非正规数或次正规数,见维基百科:非正规数.

Answer 2

来自文档:

方法nextDouble由Random类实现,如下所示:

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

但它也说明了以下内容(强调我的):

[在Java的早期版本中,结果被错误地计算为:

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

这似乎是等价的,如果不是更好的话,但实际上它引入了一个很大的不均匀性,因为浮点数的舍入有偏差:有效数的低位有可能是0的三倍.而不是1!这种不均匀性在实践中可能并不重要,但我们力求完美.]

自从Java 5以来,这个注释已经存在(Java <= 1.4的文档是在登录墙后面,懒得检查).这很有趣,因为即使在Java 8中问题显然仍然存在.也许"固定"版本从未经过测试？

Answer 3

考虑到如何表示浮点数,这个结果并不让我感到惊讶.假设我们有一个非常短的浮点类型,只有4位精度.如果我们要生成0到1之间的随机数,均匀分布,则会有16个可能的值:

0.0000
0.0001
0.0010
0.0011
0.0100
...
0.1110
0.1111

如果这就是他们在机器中的样子,你可以测试低阶位以获得50/50的分布.但是,IEEE浮点数表示为尾数的2倍; 浮点中的一个字段是2的幂(加上固定的偏移量).选择2的幂,使得"尾数"部分总是> = 1.0且<2.0.这意味着,实际上,除此之外的数字0.0000将表示如下:

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

(1二进制点之前是隐含值;对于32位和64位浮点数,实际上没有分配任何位来保存它1.)

但是看看上面的内容应该说明为什么,如果你将表示转换为位并查看低位,你将在75%的时间内得到零.这是由于所有小于0.5(二进制0.1000)的值,这是可能值的一半,其尾数被移位,导致0出现在低位.当尾数具有52位(不包括隐含的1)时,情况基本相同double.

(实际上,正如@sneftel在评论中所建议的那样,我们可以在分布中包含超过16个可能的值,方法是:

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

但我不确定这是大多数程序员所期望的那种分布,所以它可能不值得.此外,当值用于生成整数时,它不会获得太多收益,因为随机浮点值通常是.)