Java случайный класс, сгенерировать дублирующееся число, используя то же самое семя и nextBytes ()?

Question

Предполагая, что я использую то же начальное число путем создания экземпляра статического конечного объекта Random с помощью нового метода Random (), возможно ли получить одно и то же число дважды, вызвав nextBytes в одном и том же экземпляре?

Я знаючто для любого заданного семени могут быть определены все возможные «случайные» числа, и это действительно больше похоже на последовательность:

  synchronized protected int next(int bits) {
     seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
     return (int)(seed >>> (48 - bits));
}

Так что, в принципе, если у меня есть этот код:

private static final Random random = new Random();

 public void doSomething() {
   for (int i=0; i < 1000000000; i++) {
      byte byteArray[] = new byte[8];
      random.nextBytes(byteArray)
   }
 }

Насколько вероятно, что nextBytes сгенерирует те же байты до того, как пройдет все возможные числа, которые он может сгенерировать?

Будет ли возвращено то же значение, прежде чем будут возвращены все возможные комбинации для заданных битов?,Я предполагаю, да, но как часто это происходит?

Answer 1

Класс Random использует генератор линейной конгруэнции с очень большим периодом. Он не повторяет значение int в течение очень долгого времени. Вызов nextBytes с 8-байтовым массивом генерирует два значения типа int и разбивает каждое на четыре 8-битных значения для заполнения массива.

Я считаю, что для последовательных вызовов nextBytes невозможно сгенерировать одинаковые значения. Это будет означать, что генератор случайных чисел будет иметь период 2. В docs указано конкретное поведение для next, которое делает это невозможным. (Подкласс Random, конечно, может иметь любой тип патологического поведения, который вам нравится, но экземпляр java.util.Random будет вести себя хорошо.)

Answer 2

Ответы выше, предполагающие, что повторяющиеся одинаковые значения не могут возникнуть, похоже, забывают о том, что Java.Random имеет длину периода 2 ^ 48. Из-за этого вполне возможно, что nextInt () сгенерирует точно такие же целые числа ДО того, как один прошел все значения в периоде ГСЧ. На самом деле 2 ^ 16 раз.

Кроме того, поскольку целые числа разделены на четыре, одни и те же байты могут (будут) появляться, даже если бы нам пришлось пройти через все целые числа. На самом деле, если бы это было так, каждое значение байта появилось бы 2 ^ 24 раза, прежде чем мы прошли все целочисленные значения. Однако я знаю, что первоначальный вопрос касался байтового массива, состоящего из восьми байтов. В этом случае мы получили бы тот же массив после 2 ^ 31 (2 ^ 47 для Java-случайного) вызовов nextByte (потому что нам нужно два целых числа).

Нам не нужно проходить через все целые числа, как я уже говорил.

Это, как говорится, если мы предполагаем равномерное распределение значений, возвращаемых nextInt (), то вероятность получения точно таких же целых чисел в серии из n выборок приблизительно 1 - ((2 ^ 32 -1) / 2 ^ 32) ^ (n (n-1) / 2). Смотри http://en.wikipedia.org/wiki/Birthday_problem

Число выборок, которые нам нужно нарисовать, чтобы иметь вероятность, превышающую 50%, чтобы иметь два совпадающих целых числа, составляет всего лишь немногим более 77000. Если теперь мы предположим, что вместо этого равномерно рисуем число 2 ^ 64 или два 2 ^ 32 целых числа (для восьми байтов), то мы получим ту же вероятность после 5 * 10 ^ 9 выборок, что составляет около 2 ^ 32. Обратите внимание, что даже если бы к тому времени мы могли видеть все целые числа, это все равно значительно короче, чем период Рэндома. Правда, вероятно, где-то посередине. Во всяком случае, вероятность очень низкая, но не совсем нулевая, как показано в постах выше.

Я что-то упустил?

Answer 3

Вероятность того, что nextBytes вернет то же значение, которое оно вернуло в предыдущей итерации, точно равна вероятности того, что nextBytes вернет любые конкретные восемь случайных байтов.

Хороший генератор случайных чисел не дает никаких гарантийо битах, которые будут возвращены, кроме факта, что биты будут случайными.Иногда желательно, чтобы генератор возвращал все возможные значения в случайном порядке, но обычно это не цель генератора случайных чисел.