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

Question

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

javarandomdoublebit-manipulationprobability

139

编辑：所以基本上我想编写的是一个针对double的1位哈希。

我想将double映射为true或false，并且有50/50的机会。为此，我编写了代码，选择一些随机数（仅作为示例，我想在具有规律性的数据上使用此代码，仍然获得50/50的结果），检查它们的最后一位，并在1时增加y，或者在0时增加n。

然而，这段代码经常导致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

- gvlasov

43

希望答案能涉及浮点数随机变量的随机生成，而不是“线性同余发生器在低位上熵值较低”的解释。 - Sneftel

4

我非常好奇，“1位哈希双精度数”有何用途？我真的想不出有任何合法的应用需要这个要求。 - corsiKa

3

在几何计算中，通常有两种情况供我们从两个可能的答案中选择（例如，点在线的左边还是右边？），有时会引入第三种退化情况（即点正好位于线上），但您只有两个可用的答案，因此在这种情况下必须伪随机地选择其中一个可用的答案。我能想到的最好方法是对其中一个给定的双精度值进行1位哈希（请记住，这些是几何计算，所以到处都有双精度值）。 - gvlasov

2

@corsiKa（评论分为两部分，因为太长了）我们可以从一些更简单的东西开始，比如 doubleValue % 1 > 0.5，但这会过于粗糙，因为它可能会在某些情况下引入可见的规律性（所有值都在长度为1的范围内）。如果这太粗糙了，那么我们应该尝试更小的范围，比如 doubleValue % 1e-10 > 0.5e-10？好的，是的。当你一直遵循这种方法到最后，使用最小的模数，只取 double 的最后一位作为哈希值。 - gvlasov

1

@kmote 那么你仍然会有严重偏向的最低有效位，而另一个位并不能弥补它 - 实际上，由于完全相同的原因，它也偏向于零（但不那么严重）。因此，分布将约为50、12.5、25、12.5。虽然很奇怪，但 (lastbit & 3) == 0 可以起作用。 - harold

显示剩余4条评论

3个回答

48

根据文档:

方法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 中，这个问题显然仍然存在。也许“修复”版本从未经过测试？

- Thomas

4

奇怪，我在Java 8上也重现了这个问题。 - aioobe

3

@harold：不，我认为你是对的，试图修正这种偏见的人可能犯了错误。 - Thomas

6

是时候给Java团队发送一封电子邮件了。 - Daniel

8

也许修复版从未经过测试？重新阅读后，我认为这份文档是关于另一个问题的。需要注意的是，文档提到了舍入，这表明他们没有直接考虑“三倍概率”是问题，而是当值被_舍入_时会导致非均匀分布。请注意，在我的答案中，我列出的值是均匀分布的，但在IEEE格式中表示的低位不是均匀的。我认为他们解决的问题与整体均匀性有关，而不是低位数的均匀性。 - ajb

1

换句话说，修复的目的从来不是为了纠正低位比特的分布。在我看来，这并不是一个值得追求的目标。 - ajb

显示剩余2条评论

33

考虑到浮点数的表示方式，这个结果并不令我惊讶。假设我们有一个非常短的浮点类型，只有4位精度。如果我们生成一个在0到1之间均匀分布的随机数，则可能会出现16个可能值：

如果它们在机器中是这样的话，您可以测试低阶位以获得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

但我不确定这是大多数程序员期望的分布类型，所以它可能不值得去尝试。另外，当这些值用于生成整数时，并不能获得太多好处，因为随机浮点值经常被使用。

- ajb

5

使用浮点数来获取随机位/字节/任何东西让我感到不安。即使对于0到n之间的随机分布，我们也有比random*n更好的选择（请看arc4random_uniform）。 - mirabilos

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- harold · Accepted Answer

因为 nextDouble 的工作方式是这样的：(source)

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

next(x) 生成 x 个随机位。

那么为什么要这样做呢？因为在第一部分生成的大约一半数字（除以常数之前）小于 1L << 52，因此它们的有效数字不完全填满可用的 53 位，这意味着对于这些数字，有效数字的最低位总是为零。

由于这受到了很多关注，这里提供一些额外的解释，说明 Java 中（以及许多其他语言中）的 double 究竟是什么样子，以及为什么在这个问题中很重要。

基本上，一个 double 长这样：(来源)

double layout

这张图片没有显示出来的一个非常重要的细节是——数字被“归一化”¹，以使得 53 位的小数部分以 1 开头（通过选择指数使其如此），然后省略掉这个 1。这就是为什么图片中显示小数部分有 52 位（有效数字）但实际上它有 53 位。

归一化意味着，如果在 nextDouble 的代码中设置了第 53 位，那么这一位就是隐含的首位 1，并且会被删除，剩下的其他 52 位直接复制到结果 double 的有效数字中。但是如果该位没有被设置，则必须将剩余位左移，直到它变为 1。

平均而言，生成的一半数字属于有效数字不需要左移的情况（其中约一半的数字最低位为 0），另一半数字至少向左移动 1 位（或者完全为零），因此它们的最低有效位总是 0。

1：并非总是如此，对于没有最高位 1 的 0（指数与尾数都为 0），无法进行归一化。这些数字被称为“非规格化”或“次正常数”，详见维基百科：非规格化数。