Класс Java Random, сгенерировать повторяющееся число с использованием того же начального числа и nextBytes ()?

Предполагая, что я использую одно и то же семя, создавая экземпляр статического конечного объекта Random с помощью new 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 сгенерирует те же байты, прежде чем пройдет через все возможные числа, которые он может сгенерировать?

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


java random duplicates random-seed
person Oscar Gomez    schedule 24.06.2011    source источник

Ответы (3)


arrow_upward
5
arrow_downward

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

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

person Ted Hopp    schedule 24.06.2011
comment
Под периодом вы имеете в виду, что в конечном итоге начальное значение вернется к своему исходному значению? И затем, конечно, снова сгенерирует те же числа? Затем, если, например, я генерирую случайные числа от 1 до 1000 с помощью java.util.Random, вероятность создания данного числа может быть либо 0, либо чем-то более высоким, чем 1/1000? - person Oscar Gomez; 24.06.2011
comment
Это правильно. Числовая последовательность, сгенерированная java.util.Random, полностью детерминирована после установки начального числа; поэтому он называется псевдо случайным. Вероятность того, что данное число присутствует в следующих 1000 числах, равна 0 или 1. Уловка состоит в том, что это чрезвычайно трудно предсказать, и для статистических целей ведет себя так, как если бы числа были случайными. Если вам нужен более сильный генератор случайных чисел, обратите внимание на класс java.security.SecureRandom. - person Ted Hopp; 24.06.2011

arrow_upward
0
arrow_downward

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

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

person Steve Prentice    schedule 24.06.2011
comment
Это не правильно. java.util.Random не является истинным генератором случайных чисел. это псевдослучайный генератор линейной конгруэнции с очень длинным периодом. Он не может заполнить массив из 8 байтов одинаковыми значениями при последовательных вызовах (если начальное значение не сброшено). Это даст ему период 2, что противоречит поведению, указанному в документации. - person Ted Hopp; 24.06.2011
comment
Спасибо. Я предположил, что java.util.Random был случайным, но после прочтения документации очевидно, что это не так. - person Steve Prentice; 24.06.2011

arrow_upward
0
arrow_downward

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

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

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

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

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

Я что-то упускаю?

person Michael Kutschke    schedule 10.08.2011