接近零的均匀真实分布

Question

是否有人要求对连续均匀分布进行浮点近似与（似乎更受欢迎的）离散均匀分布形成对比？

为了产生量化为浮点类型的任意精度随机值，我希望有以下几点：

double rand0to1(void)
{
    int exp = -53;
    while (random_bit() == 0) exp--;
    return ldexp((double)((1L << 52) | random_52bits()), exp);
}

看起来很常见的是：

double rand0to1(void)            
{
    return ldexp((double)random_53bits(), -53);
}

显然，前者是不可能实现的近似值，这是一个很大的问题，但我想知道是否在某些情况下，如果结果碰巧很小，尾数总是完全随机的保证会变得有用。

如果我正在实现我自己的通用统一实随机数生成器库，那么偏离惯例并保持尾数对于小值完全随机化会造成什么危害？

我最好的猜测是，在随后的算术之后，额外的精度可能会强制一个舍入条件，这会偏置低位。然而，我的直觉是，这通常也会发生在离散分布的算术上。

Answer 1

主要区别在于，您的第一个定义 \xe2\x80\x94 不太正确，但在 \xe2\x88\xa9 [0,1) 上支持 close\xe2\x80\x94，而仅支持您的第二个定义在 \xe2\x88\xa9 ({0} \xe2\x88\xaa [2\xe2\x81\xbb\xe2\x81\xb5\xc2\xb3, 1)) 上。

\n

您的第一个定义将返回零，概率约为 2\xe2\x81\xbb\xc2\xb9\xe2\x81\xb0\xe2\x81\xb7\xe2\x81\xb5，这是实数的正确勒贝格度量四舍五入到零。

\n

相反，您的第二个定义省略 (0, 2\xe2\x81\xbb\xe2\x81\xb5\xc2\xb3) 中的所有浮点数，并以 2\xe2\x81\xbb\xe2 的概率返回 0 \x81\xb5\xc2\xb3。

\n

为什么这很重要？

\n

假设您想要取结果的对数（例如，在指数或拉普拉斯采样器中），或者计算本质奇点为零的任何其他函数。

\n

\n

• 这对于您的第一个定义是安全的，没有拒绝采样： 2\xe2\x81\xbb\xc2\xb9\xe2\x81\xb0\xe2\x81\xb7\xe2\x81\xb5 的概率非常小，甚至密码学家认为它可以忽略不计。 \n保证您永远不会被零除或处理无穷大，除非您的随机位生成器严重损坏。

  \n
\n

• 但是，虽然在使用第二个定义进行测试期间不太可能被零除并产生 \xe2\x88\x92\xe2\x88\x9e，但概率为 2\xe2\x81\xbb\xe2\x81\ xb5\xc2\xb3 不可忽略\xe2\x80\x94比特币网络每秒会以 2\xe2\x81\xbb\xe2\x81\xb5\xc2\xb3 的概率多次触发某个事件，以求消耗能量对于无用的随机数学难题解决方案。\n为了安全地使用第二个定义，您必须对输出进行拒绝采样以避免零，即使在 [0,1) 上四舍五入到浮点数的真正均匀分布中零的概率是超出可以忽略不计的程度。

  \n
\n

\n

类似地，[0,1) 上的真实均匀分布四舍五入到浮点数也可以产生 1。\n通过从支持中省略 1，您可以排除 [0,1) 的一个小但不可忽略的分数，并且最好从 [0,1 \xe2\x88\x92 2\xe2\x81\xbb\xe2\x81\xb5\xe2\x81\xb4) 而不是 [0,1) 有效采样。

\n

但无论如何，很少有理由省略 1；例如，如果您要使用 log1p()，其中 \xe2\x88\xbc [0,1) 是均匀的，则可以通过使用 log() 来获得完全相同的分布，其中 \xe2\x88\xbc (0 ,1]，这可以更有效地利用浮点空间。

\n

它不仅可以更有效地利用浮点空间，而且可能会区分破坏的差分隐私和安全的差分隐私（尽管您可能还需要正确舍入的对数，而不仅仅是任何旧的 libm）。

\n

（如果我想要[0,） 上的整数采样器，你会问？\n你已经有一个统一的位采样器；鉴于此，您最好只对 \xe2\x8c\x88lg \xe2\x8c\x89 位字符串进行拒绝采样，而不是通过浮点进行迂回绕行。）

\n

那么什么是正确的呢？\n编写一个 [0,1] 采样器（或 (0,1] 采样器，通过以概率 2\xe2\x81\xbb\ 调用 [0,1] 中 0 的事件xc2\xb9\xe2\x81\xb0\xe2\x81\xb7\xe2\x81\xb5 一个不会发生的错误），像你一样绘制几何分布的指数，然后绘制均匀分布的有效数超过53 位\xe2\x80\x94 并无条件设置最低有效位。

\n

最低有效位充当一种粘性位：在实数的真正均匀分布中，具有有限 53 位二进制展开式且后跟所有 0 位的子集的测量值为零，因此 \xe2\x80\x9cal 最总是\xe2\x80\x9d 一个 1 位，这个 \xe2\x80\x9c 粘性位\xe2\x80\x9d 表示打破平局。\n这为 [0,1] 中的每个浮点数提供了正确的权重。

\n