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

Question

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

numpy.random.rand(n)

n 的任意给定值？

在数学上，我认为这相当于先问有多少IEEE 754 singles或 doubles在区间 [0, 1) 中。那么我想下一步将是解决等效的 birthday problem ？我不太确定。任何人都有一些见解？

Answer 1

由 numpy.random.rand 执行的计算为每个元素生成一个数字 0.<53 random bits> ，总共有 2^53 个同样可能的输出。 (当然，内存表示不是定点 0.stuff ；它仍然是 float 。)这种计算无法产生大多数介于 0 和 1 之间的 binary64 float ；例如，它不能产生 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;
}

(请注意 rk_random 产生 32 位输出，无论 long 的大小如何。)

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