random - 接近零的均匀真实分布

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

主要区别在于，您的第一个定义(虽然不太正确，但很接近)支持 𝔽 ∩ [0,1)，而您的第二个定义仅支持 𝔽 ∩ ({0} ∪ [2⁻⁵³ , 1))。
您的第一个定义将以大约 2⁻¹⁰⁷⁵ 的概率返回零，这是四舍五入为零的实数的正确 Lebesgue 度量。
相反，您的第二个定义省略 (0, 2⁻⁵³) 中的所有浮点数，并以 2⁻⁵³ 的概率返回 0。
为什么这很重要？
假设您想对结果取对数(例如，在指数或拉普拉斯采样器中)，或计算任何其他具有零基本奇点的函数。

这对于您的第一个定义是安全的，没有拒绝抽样:2⁻¹⁰⁷⁵ 的概率非常小，以至于密码学家也认为它可以忽略不计。
除非您的随机位生成器严重损坏，否则您可以保证永远不会被零除或处理无穷大。

但是，虽然您不太可能在第二个定义的测试过程中被零除并产生 −∞，但 2⁻⁵³ 的概率是不可忽略的——比特币网络每秒多次以概率 2⁻⁵³ 跳过一个事件在它为无用的随机数学难题解决方案燃烧能量的永不满足的追求中。
要安全地使用第二个定义，您必须对输出进行拒绝采样以避免为零，即使在 [0,1) 上舍入为浮点数的真正均匀分布中为零的概率是不可忽略的。

类似地，[0,1) 上的真正均匀分布四舍五入为浮点数也可以产生 1。
通过从支持中省略 1，您可以排除 [0,1) 的一小部分但不可忽略的部分，并且最多有效地从 [0,1 − 2⁻⁵⁴) 而不是 [0,1) 进行采样。
但无论如何都很少有理由省略 1；例如，如果您打算使用 log1p(𝑈) 其中 𝑈 ∼ [0,1) 是均匀的，您可以通过使用 log(𝑈) where 𝑈 ∼ (0,1]) 来获得完全相同的分布，这使得更有效地利用浮点空间。
它不仅可以更有效地利用浮点空间，而且可能会产生 broken and secure differential privacy 之间的差异。 (尽管您可能还需要一个正确舍入的对数，而不仅仅是任何旧的 libm)。
(如果我想要在 [0,𝑛 上的整数采样器怎么办)，你问？
你已经有了一个统一的位采样器；鉴于此，您最好只对 ⌈lg 𝑛⌉ 位字符串进行拒绝采样，而不是通过浮点绕道而行。)
那么什么是正确的呢？
要编写 [0,1] 采样器(或 (0,1] 采样器，通过以概率 2⁻¹⁰⁷⁵ 调用 [0,1] 中的 0 事件是一个不会发生的错误)，请绘制具有几何分布的指数像你一样，然后在超过 53 位上绘制均匀分布的有效数——并无条件地设置最低有效位。
最低有效位用作一种粘滞位:在实数的真正均匀分布中，具有有限 53 位二进制扩展后跟所有 0 位的子集测量为零，因此“几乎总是”有一个 1 位，这个“粘性位”代表打破关系。
这为 [0,1] 中的每个浮点数提供了正确的权重。