Каковы шансы повторения в numpy.random.rand (n) (при условии идеальной случайности)?

Question

На данный момент оставим в стороне любые проблемы, связанные с генераторами псевдослучайных чисел, и предположим, что numpy.random.rand идеально сэмплирует из дискретного распределения чисел с плавающей запятой по [0, 1).Каковы шансы получить как минимум два точно одинаковых числа с плавающей запятой в результате:

numpy.random.rand(n)

для любого заданного значения n?

Математически, я думаю, что это эквивалентносначала спрашиваем, сколько IEEE 754 одиночных или удваивается в интервале [0, 1).Тогда я думаю, что следующим шагом будет решение эквивалентной проблемы дня рождения ?Я не совсем уверен.У кого-нибудь есть понимание?

Answer 1

Вычисление, выполненное numpy.random.rand для каждого элемента, генерирует число 0.<53 random bits>, что в сумме дает 2 ^ 53 одинаково вероятных выходных данных.(Конечно, представление памяти не является фиксированной точкой 0.stuff; это все еще с плавающей запятой.) Это вычисление не в состоянии произвести большинство двоичных 64 чисел с плавающей запятой между 0 и 1;например, он не может произвести 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.Вероятно, лучше использовать приближение вместо того, чтобы вычислять это непосредственно для больших значений n.(Аппроксимация может быть даже более точной, в зависимости от того, как ошибка аппроксимации сравнивается с ошибкой округления, накопленной в прямом вычислении.)

Answer 2

Я думаю, что вы правы, это как проблема дня рождения.Но вам нужно определиться с количеством возможных вариантов.Вы делаете это, решая точность ваших чисел с плавающей точкой.Например, если вы решите иметь точность 2 числа после точки, то есть 100 вариантов (включая ноль и исключая 1).

А если у вас n чисел, то вероятность отсутствия столкновенияравно:

или при задании R возможных чисел и N точек данных вероятность отсутствия столкновения составляет:

И коллизия равна 1 - P.

Это потому, что вероятность получения любого заданного числа равна 1 / R.И в любой момент вероятность того, что точка данных не столкнется с предыдущими точками данных, равна (Ri) / R, поскольку i является индексом точки данных.Но чтобы получить вероятность того, что точки данных не столкнутся друг с другом, нам нужно умножить все вероятности точек данных, не столкнувшись с предыдущими.Применяя некоторые алгебраические операции, мы получаем приведенное выше уравнение.