numpy.random.rand(n) 中重复的几率是多少（假设完全随机）？

Question

目前，抛开与伪随机数生成器相关的任何问题，并假设 numpy.random.rand 从 [0, 1) 上浮点数的离散分布中完美采样。在以下结果中得到至少两个完全相同的浮点数的几率是多少：

numpy.random.rand(n)

对于 n 的任何给定值？

在数学上，我认为这相当于先问有多少IEEE 754 singles or doubles there are in the interval [0, 1). Then I guess the next step would be to solve the equivalent birthday problem？我不太确定。有人有一些见解吗？

Answer 1

我认为你是对的，这就像生日问题。但是您需要决定可能选项的数量。您可以通过确定浮点数的精度来做到这一点。例如，如果您决定精度为点后 2 个数字，则有 100 个选项（包括零，不包括 1）。

如果你有 n 个数字，那么没有碰撞的概率是：

或者当给定R个可能的数字和N个数据点时，没有碰撞的概率是：

而碰撞的是1-P。

这是因为得到任何给定数字的概率是 1/R。在任何时候，数据点不与先前数据点冲突的概率是 (R-i)/R，因为 i 是数据点的索引。但是为了得到没有数据点相互碰撞的概率，我们需要将所有数据点不与之前的数据点碰撞的概率相乘。应用一些代数运算，我们得到上面的等式。

Answer 2

numpy.random.rand 对每个元素执行的计算生成一个数字 0.<53 random bits>，总共 2^53 个等可能的输出。（当然，内存表示不是定点数 0.stuff；它仍然是浮点数。）这种计算无法产生大多数介于 0 和 1 之间的 binary64 浮点数；例如，它不能产生 1/2^60。你可以在numpy/random/mtrand/randomkit.c:

中看到代码

double
rk_double(rk_state *state)
{
    /* shifts : 67108864 = 0x4000000, 9007199254740992 = 0x20000000000000 */
    long a = rk_random(state) >> 5, b = rk_random(state) >> 6;
    return (a * 67108864.0 + b) / 9007199254740992.0;
}

（请注意，无论 long 的大小如何，rk_random 都会产生 32 位输出。）

假设一个完美的随机源，numpy.random.rand(n) 中重复的概率是 1-(1-0/k)(1-1/k)(1-2/k)...( 1-(n-1)/k)，其中 k=2^53。对于较大的 n 值，最好使用 approximation 而不是直接计算它。（近似值甚至可能更准确，具体取决于近似误差与直接计算中累积的舍入误差的比较情况。）

numpy.random.rand(n) 中重复的几率是多少（假设完全随机）？

What are the odds of a repeat in numpy.random.rand(n) (assuming perfect randomness)?

python

floating-point

numpy

probability

ieee-754