Эффективная Java-статья 47: Знание и использование ваших библиотек. Пример ошибочного случайного целочисленного метода.

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

Метод из книги:

private static final Random rnd = new Random();

//Common but deeply flawed
static int random(int n) {
    return Math.abs(rnd.nextInt()) % n;
}

Он говорит, что если n - малая степень 2, последовательность генерируемых случайных чисел будет повторяться через короткий промежуток времени. Почему это так? Документация для Random.nextInt() говорит Returns the next pseudorandom, uniformly distributed int value from this random number generator sequence. Так что не должно быть, что если n - небольшое целое число, то последовательность повторится, почему это относится только к степеням 2?
Затем он говорит, что если n не является степенью 2, некоторые числа будут возвращаться в среднем чаще, чем другие. Почему это происходит, если Random.nextInt() генерирует случайные целые числа, которые равномерно распределены? (Он предоставляет фрагмент кода, который наглядно демонстрирует это, но я не понимаю, почему это так, и как это связано с тем, что n является степенью 2).

Ответ 1

Вопрос 1:, если n - малая степень 2, последовательность генерируемых случайных чисел будет повторяться через короткий промежуток времени.

Это не является следствием всего, что говорит Джош; скорее, это просто известное свойство линейных конгруэнтных генераторов. Википедия должна сказать следующее:

Еще одна проблема LCG заключается в том, что младшие разряды сгенерированной последовательности имеют гораздо более короткий период, чем последовательность в целом, если m задано степенью 2. В общем случае n-я младшая значащая цифра в базовом b представлении выходной последовательности, где b ^k= m для некоторого целого k, повторяется с не более чем периодом b ⁿ.

Это также отмечается в Javadoc:

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

Другая версия функции Random.nextInt(int) работает вокруг этого, используя в этом случае разные биты (выделение мое):

Алгоритм рассматривает случай, когда n - это сила двух специально: он возвращает правильное количество старших бит из генератора псевдослучайных чисел.

Это хорошая причина предпочесть Random.nextInt(int) с помощью Random.nextInt() и сделать собственное преобразование диапазона.

Вопрос 2: Далее он говорит, что если n не является степенью 2, некоторые числа будут возвращаться в среднем чаще, чем другие.

Есть 2 ³² различные числа, которые могут быть возвращены nextInt(). Если вы попытаетесь поместить их в n ведер, используя % n, а n не имеет значения 2, некоторые ведра будут иметь больше чисел, чем другие. Это означает, что некоторые результаты будут происходить чаще, чем другие, хотя исходное распределение было однородным.

Посмотрите на это, используя небольшие числа. Скажем, nextInt() вернул четыре равновероятных результата: 0, 1, 2 и 3. Посмотрим, что произойдет, если мы применим к ним % 3:

0 maps to 0
1 maps to 1
2 maps to 2
3 maps to 0

Как вы можете видеть, алгоритм будет возвращать 0 в два раза чаще, чем возвращать каждый из 1 и 2.

Это не происходит, когда n является степенью двух, так как одна степень из двух делится на другую. Рассмотрим n=2:

0 maps to 0
1 maps to 1
2 maps to 0
3 maps to 1

Здесь 0 и 1 происходят с одинаковой частотой.

Дополнительные ресурсы

Вот некоторые дополнительные - если только касательно релевантные - ресурсы, связанные с LCG:

Спектральные тесты - это статистические тесты, используемые для оценки качества LCG. Подробнее здесь и здесь.
Коллекция классических генераторов псевдослучайных чисел с линейными структурами имеет несколько симпатичных диаграмм рассеяния (генератор, используемый в Java, называется DRAND48).
В crypto.SE есть интересная дискуссия о прогнозировании значений из генератора Java.

Ответ 2

1) Когда n является степенью 2, rnd % n эквивалентно выбору нескольких младших бит оригинала. Известно, что младшие биты чисел, генерируемые типом генераторов, используемых java, "менее случайны", чем более высокие бит. Это просто свойство формулы, используемой для генерации чисел.

2) Представьте себе, что наибольшее возможное значение, возвращаемое random(), равно 10 и n = 7. Теперь n % 7 отображает числа 7, 8, 9 и 10 в 0, 1, 2, 3 соответственно. Поэтому, если исходное число равномерно распределено, результат будет сильно смещен в сторону более низких чисел, поскольку они будут отображаться вдвое чаще, чем 4, 5 и 6. В этом случае это происходит независимо от того, является ли n мощность двух или нет, но если вместо 10 мы выбрали, скажем, 15 (что составляет 2 ^ 4-1), то любой n, то есть степень двух, приведет к равномерному распределению, поскольку не должно быть "лишних" чисел, оставшихся в конце диапазона, чтобы вызвать смещение, потому что общее количество возможных значений будет точно делиться на количество возможных остатков.