Random.nextInt(int) [слегка] смещен

А именно, он никогда не будет генерировать более 16 четных чисел в строке с некоторыми конкретными параметрами upperBound:

Random random = new Random();

int c = 0;
int max = 17;
int upperBound = 18;

while (c <= max) {
    int nextInt = random.nextInt(upperBound);
    boolean even = nextInt % 2 == 0;
    if (even) {
        c++;
    } else {
        c = 0;
    }
}

В этом примере код будет циклическим навсегда, тогда как upperBound, например, 16, он быстро завершается.

Что может быть причиной такого поведения? В методе javadoc есть некоторые примечания, но я их не понял.

UPD1: код, кажется, заканчивается с нечетными верхними границами, но может зависеть даже от четных

UPD2: Я изменил код, чтобы зафиксировать статистику c, как это предложено в комментариях:

Random random = new Random();

int c = 0;
long trials = 1 << 58;
int max = 20;
int[] stat = new int[max + 1];

while (trials > 0) {
    while (c <= max && trials > 0) {
        int nextInt = random.nextInt(18);
        boolean even = nextInt % 2 == 0;
        if (even) {
            c++;
        } else {
            stat[c] = stat[c] + 1;
            c = 0;
        }
        trials--;
    }
}

System.out.println(Arrays.toString(stat));

Теперь он пытается достичь 20 evens в строке - чтобы получить лучшую статистику, а upperBound по-прежнему 18.

Результаты оказались более чем удивительными:

[16776448, 8386560, 4195328, 2104576, 1044736, 
 518144, 264704, 132096, 68864, 29952, 15104, 
 12032, 1792, 3072, 256, 512, 0, 256, 0, 0]

Сначала он уменьшается, как ожидалось, в 2 раза, но обратите внимание на последнюю строку! Здесь он сходит с ума, и захваченная статистика кажется совершенно странной.

Вот график штриховки в шкале журнала:

c statistics

Как c получает значение 17 256 раз - еще одна загадка

Ответы

Ответ 1

http://docs.oracle.com/javase/6/docs/api/java/util/Random.html:

Экземпляр этого класса используется для создания потока псевдослучайные числа. Класс использует 48-битное семя, которое модифицировано используя линейную конгруэнтную формулу. (См. Дональд Кнут, Искусство Компьютерное программирование, том 3, раздел 3.2.1.)

Если два экземпляра Random созданы с одним и тем же семенем, а для каждой из них выполняется одна и та же последовательность вызовов методов, они будут генерировать и возвращать идентичные последовательности чисел. [...]

Это генератор псевдослучайных чисел. Это означает, что вы фактически не катитесь с кубиками, а скорее используете формулу для вычисления следующего "случайного" значения на основе текущего случайного значения. Для создания используется иллюзия рандомизации a seed. Семя - это первое значение, используемое с формулой для генерации случайного значения.

По-видимому, случайная реализация javas ( "формула" ) не генерирует более 16 четных чисел в строке.

Это поведение является причиной того, что seed обычно инициализируется временем. Когда вы начнете свою программу, вы получите разные результаты.

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

Для истинных случайных чисел некоторые операционные системы предоставляют специальные устройства, которые генерируют "случайность" из внешних событий, таких как mousemovements или сетевой трафик. Однако я не знаю, как использовать те, у кого есть java.

Из документа Java для secureRandom:

Многие реализации SecureRandom представлены в виде псевдослучайных (PRNG), что означает, что они используют детерминированный алгоритм для получения псевдослучайной последовательности из истинного случайного семени. Другие реализации могут создавать истинные случайные числа, а другие может использовать комбинацию обоих методов.

Обратите внимание, что secureRandom делает НЕ гарантию истинных случайных чисел.

Почему изменение семени не помогает

Предположим, что случайные числа будут иметь только диапазон 0-7. Теперь мы используем следующую формулу для генерации следующего "случайного" числа:

 next = (current + 3) % 8

последовательность становится 0 3 6 1 4 7 2 5.

Если вы теперь возьмете семя 3, все, что вы делаете, это изменить начальную точку.

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

например. представьте себе последовательность 0 3 6 1 3 4 7 2 5. Цифры 0,4,7,2 and 5 никогда не будут генерироваться более одного раза (углубление на семя, которое они могут быть сгенерированы никогда), так как после циклов последовательности 3,6,1,3,6,1,....

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

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

Ответ 2

Реализация Случайности использует простую линейную конгруэнтную формулу. Такие формулы имеют естественную периодичность и всевозможные неслучайные шаблоны в последовательности, которую они генерируют.

То, что вы видите, является артефактом одного из этих паттернов... ничего преднамеренного. Это не пример предвзятости. Скорее это пример автокорреляции.

Если вам нужны лучшие (более "случайные" ) номера, вам нужно использовать SecureRandom, а не Random.

И ответ на вопрос "почему он был реализован так:"... производительность. Вызов Random.nextInt может выполняться в десятки или сотни тактовых циклов. Вызов SecureRandom скорее всего будет на 2 порядка медленнее, возможно, больше.

Ответ 3

Для переносимости Java указывает, что реализации должны использовать метод нижнего LCG для java.util.Random. Этот метод совершенно неприемлем для любого серьезного использования случайных чисел, таких как комплексное моделирование или методы Монте-Карло. Используйте дополнительную библиотеку с лучшим алгоритмом PRNG, например Marsaglia MWC или KISS. Mersenne Twister и отложенные генераторы Фибоначчи часто также хорошо.

Я уверен, что для этих алгоритмов существуют библиотеки Java. У меня есть библиотека C с привязками Java, если это сработает для вас: ojrandlib.