Почему rand ()% 6 смещен?

Читая, как использовать std :: rand, я нашел этот код на cppreference.com

int x = 7;
while(x > 6) 
    x = 1 + std::rand()/((RAND_MAX + 1u)/6);  // Note: 1+rand()%6 is biased

Что не так с выражением справа? Пробовал и работает отлично.

Есть две проблемы rand() % 6( 1+не влияют ни на одну из них).

Во-первых, как указывалось в нескольких ответах, если младшие биты rand()не являются должным образом однородными, результат оператора остатка также не является однородным.

Во-вторых, если количество различных значений, созданных с помощью rand(), не кратно 6, то остаток даст более низкие значения, чем высокие значения. Это верно, даже если rand()возвращает идеально распределенные значения.

В качестве крайнего примера, представьте, что rand()производит равномерно распределенные значения в диапазоне [0..6]. Если вы посмотрите на остатки для этих значений, когда rand()возвращается значение в диапазоне [0..5], остаток дает равномерно распределенные результаты в диапазоне [0..5]. Когда rand()возвращает 6, rand() % 6возвращает 0, как если rand()бы возвращал 0. Таким образом, вы получаете распределение с вдвое большим количеством 0, чем любое другое значение.

Вторая - настоящая проблема с rand() % 6.

Способ избежать этой проблемы - отбросить значения, которые могут привести к неоднородным дубликатам. Вы вычисляете наибольшее кратное 6, которое меньше или равно RAND_MAX, и всякий раз, когда rand()возвращает значение, которое больше или равно этому кратному, вы отклоняете его и снова вызываете `rand () столько раз, сколько необходимо.

Так:

int max = 6 * ((RAND_MAX + 1u) / 6)
int value = rand();
while (value >= max)
    value = rand();

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

Здесь скрытые глубины:

1. Использование малого формата uin RAND_MAX + 1u. RAND_MAXопределяется как intтип и часто является максимально возможным int. Поведение RAND_MAX + 1будет неопределенным в таких случаях, когда вы переполняете signedтип. Запись 1uприводит к преобразованию типа RAND_MAXв unsigned, чтобы избежать переполнения.

2. Использование % 6 банки (но при каждом выполнении std::randя видел не ) вводить какие - либо дополнительные статистические смещения выше и за ее пределами альтернатив представлены. Такие % 6опасные случаи - это случаи, когда генератор чисел имеет корреляционные плоскости в битах младшего разряда, например, довольно известная реализация IBM (на языке C) rand, я думаю, 1970-х годов, в которой старшие и младшие биты менялись как «окончательный процветать". Еще одно соображение заключается в том, что 6 очень мало ср. RAND_MAX, поэтому будет минимальный эффект, если RAND_MAXон не кратен 6, что, вероятно, не так.

В заключение, в наши дни из-за его управляемости я бы использовал % 6. Маловероятно, что появятся какие-либо статистические аномалии помимо тех, которые вносит сам генератор. Если вы все еще сомневаетесь, протестируйте свой генератор, чтобы узнать, обладает ли он подходящими статистическими свойствами для вашего варианта использования.

Этот пример кода демонстрирует, что std::randэто случай унаследованной чепухи из культа карго, которая должна заставлять вас поднимать брови каждый раз, когда вы ее видите.

Здесь есть несколько проблем:

Люди по контракту обычно предполагают - даже бедные несчастные души, которые не знают ничего лучшего и не думают об этом именно в этих терминах - это randобразцы из равномерного распределения целых чисел в 0, 1, 2,… RAND_MAX,, и каждый вызов дает независимый образец.

Первая проблема заключается в том, что предполагаемый контракт, независимые однородные случайные выборки в каждом вызове, на самом деле не то, о чем говорится в документации, и на практике реализации исторически не могли обеспечить даже самый простой симулякр независимости. Например, C99 §7.20.2.1 « randФункция» говорит без уточнения:

randФункция вычисляет последовательность псевдослучайных чисел в диапазоне от 0 до RAND_MAX.

Это бессмысленное предложение, потому что псевдослучайность - это свойство функции (или семейства функций ), а не целого числа, но это не мешает даже бюрократам ISO злоупотреблять языком. В конце концов, только те читатели, которых это расстроит, знают, что лучше не читать документацию из- randза страха разложения клеток своего мозга.

Типичная историческая реализация на C работает так:

static unsigned int seed = 1;

static void
srand(unsigned int s)
{
    seed = s;
}

static unsigned int
rand(void)
{
    seed = (seed*1103515245 + 12345) % ((unsigned long)RAND_MAX + 1);
    return (int)seed;
}

У этого есть досадное свойство, что даже если одна выборка может быть равномерно распределена под равномерным случайным начальным числом (которое зависит от конкретного значения RAND_MAX), она чередуется между четными и нечетными целыми числами в последовательных вызовах - после

int a = rand();
int b = rand();

это выражение (a & 1) ^ (b & 1)дает 1 со 100% вероятностью, что не относится к независимым случайным выборкам в любом распределении, поддерживаемом четными и нечетными целыми числами. Таким образом, возник культ карго, в котором нужно отбросить младшие биты, чтобы преследовать неуловимого зверя «лучшей случайности». (Предупреждение о спойлере: это не технический термин. Это знак того, чью прозу вы читаете, либо не понимает, о чем они говорят, либо думает, что вы невежественны и должны относиться к вам снисходительно.)

Вторая проблема заключается в том, что даже если бы каждый вызов производил выборку независимо от равномерного случайного распределения на 0, 1, 2,… RAND_MAX,, результат rand() % 6не был бы равномерно распределен в 0, 1, 2, 3, 4, 5, как кубик бросок, если RAND_MAXне совпадает с -1 по модулю 6. Простой контрпример: если RAND_MAX= 6, то из rand(), все исходы имеют равную вероятность 1/7, но rand() % 6исход 0 имеет вероятность 2/7, в то время как все остальные исходы имеют вероятность 1/7 .

Правильный способ сделать это - использовать выборку для отклонения: повторно возьмите независимую однородную случайную выборку sиз 0, 1, 2,… RAND_MAX, и отклоните (например) результаты 0, 1, 2,…, - ((RAND_MAX + 1) % 6) - 1если вы получите один из те, начать заново; в противном случае уступить s % 6.

unsigned int s;
while ((s = rand()) < ((unsigned long)RAND_MAX + 1) % 6)
    continue;
return s % 6;

Таким образом, набор исходов из, rand()который мы принимаем, делится без остатка на 6, и каждый возможный результат из s % 6получается таким же количеством принятых исходов из rand(), так что если rand()он распределен равномерно, то так и есть s. Количество попыток не ограничено , но ожидаемое количество меньше 2, и вероятность успеха растет экспоненциально с количеством попыток.

Выбор того, какие результаты rand()вы отклоняете, несущественен, при условии, что вы сопоставляете равное их количество с каждым целым числом меньше 6. Код на cppreference.com делает другой выбор из-за первой проблемы выше - что ничего не гарантируется относительно распределение или независимость выходных данных rand(), и на практике младшие биты демонстрируют шаблоны, которые «не выглядят достаточно случайными» (не говоря уже о том, что следующий выходной сигнал является детерминированной функцией предыдущего).

Упражнение для читателя: Докажите , что код на cppreference.com дает равномерное распределение на штампованных рулонах , если rand()дает равномерное распределение на 0, 1, 2, ..., RAND_MAX.

Упражнение для читателя: почему вы могли бы предпочесть отклонить то или иное подмножество? Какие вычисления необходимы для каждого испытания в двух случаях?

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

Вы можете пойти по причудливому изощренному маршруту и std::uniform_int_distributionклассу C ++ 11 с подходящим случайным устройством и вашим любимым случайным движком, таким как вечно популярный твистер Мерсенна, std::mt19937чтобы играть в кости со своим четырехлетним кузеном, но даже это не поможет быть пригодным для генерации материала криптографического ключа - и Твистер Мерсенна тоже ужасный мусорщик с многокилобайтным состоянием, наносящим ущерб кеш-памяти вашего процессора с неприличным временем настройки, так что это плохо даже для, например , параллельного моделирования Монте-Карло с воспроизводимые деревья подвычислений; его популярность, вероятно, обусловлена ​​броским названием. Но вы можете использовать его для катания игрушечных кубиков, как в этом примере!

Другой подход заключается в использовании простого криптографического генератора псевдослучайных чисел с небольшим состоянием, такого как простой ГПСЧ быстрого стирания ключа , или просто потокового шифра, такого как AES-CTR или ChaCha20, если вы уверены ( например , в моделировании Монте-Карло для исследования в области естественных наук), что нет никаких неблагоприятных последствий для прогнозирования прошлых результатов, если состояние когда-либо будет скомпрометировано.

Я ни в коем случае не являюсь опытным пользователем C ++, но мне было интересно узнать, верны ли другие ответы о том, std::rand()/((RAND_MAX + 1u)/6)что они менее предвзяты, чем на 1+std::rand()%6самом деле. Поэтому я написал тестовую программу, чтобы свести в таблицу результаты для обоих методов (я давно не писал C ++, пожалуйста, проверьте). Ссылка для запуска кода находится здесь . Он также воспроизводится следующим образом:

// Example program
#include <cstdlib>
#include <iostream>
#include <ctime>
#include <string>

int main()
{
    std::srand(std::time(nullptr)); // use current time as seed for random generator

    // Roll the die 6000000 times using the supposedly unbiased method and keep track of the results

    int results[6] = {0,0,0,0,0,0};

    // roll a 6-sided die 20 times
    for (int n=0; n != 6000000; ++n) {
        int x = 7;
        while(x > 6) 
            x = 1 + std::rand()/((RAND_MAX + 1u)/6);  // Note: 1+rand()%6 is biased

        results[x-1]++;
    }

    for (int n=0; n !=6; n++) {
        std::cout << results[n] << ' ';
    }

    std::cout << "\n";


    // Roll the die 6000000 times using the supposedly biased method and keep track of the results

    int results_bias[6] = {0,0,0,0,0,0};

    // roll a 6-sided die 20 times
    for (int n=0; n != 6000000; ++n) {
        int x = 7;
        while(x > 6) 
            x = 1 + std::rand()%6;

        results_bias[x-1]++;
    }

    for (int n=0; n !=6; n++) {
        std::cout << results_bias[n] << ' ';
    }
}

Затем я взял результат этого и использовал chisq.testфункцию в R для запуска теста хи-квадрат, чтобы увидеть, сильно ли отличаются результаты от ожидаемых. Этот вопрос об обмене стеками более подробно описывает использование теста хи-квадрат для проверки честности кубика: как я могу проверить, является ли кубик честным? . Вот результаты нескольких прогонов:

> ?chisq.test
> unbias <- c(100150, 99658, 100319, 99342, 100418, 100113)
> bias <- c(100049, 100040, 100091, 99966, 100188, 99666 )

> chisq.test(unbias)

Chi-squared test for given probabilities

data:  unbias
X-squared = 8.6168, df = 5, p-value = 0.1254

> chisq.test(bias)

Chi-squared test for given probabilities

data:  bias
X-squared = 1.6034, df = 5, p-value = 0.9008

> unbias <- c(998630, 1001188, 998932, 1001048, 1000968, 999234 )
> bias <- c(1000071, 1000910, 999078, 1000080, 998786, 1001075   )
> chisq.test(unbias)

Chi-squared test for given probabilities

data:  unbias
X-squared = 7.051, df = 5, p-value = 0.2169

> chisq.test(bias)

Chi-squared test for given probabilities

data:  bias
X-squared = 4.319, df = 5, p-value = 0.5045

> unbias <- c(998630, 999010, 1000736, 999142, 1000631, 1001851)
> bias <- c(999803, 998651, 1000639, 1000735, 1000064,1000108)
> chisq.test(unbias)

Chi-squared test for given probabilities

data:  unbias
X-squared = 7.9592, df = 5, p-value = 0.1585

> chisq.test(bias)

Chi-squared test for given probabilities

data:  bias
X-squared = 2.8229, df = 5, p-value = 0.7273

В трех выполненных мной прогонах значение p для обоих методов всегда было больше, чем типичные значения альфа, используемые для проверки значимости (0,05). Это означает, что мы не считаем никого из них предвзятым. Интересно, что предполагаемый беспристрастный метод имеет постоянно более низкие значения p, что указывает на то, что на самом деле он может быть более предвзятым. Предостережение в том, что я сделал только 3 пробега.

ОБНОВЛЕНИЕ: пока я писал свой ответ, Конрад Рудольф опубликовал ответ, который использует тот же подход, но дает совсем другой результат. У меня нет репутации, чтобы комментировать его ответ, поэтому я собираюсь обратиться к нему здесь. Во-первых, главное, чтобы код, который он использует, использует одно и то же начальное число для генератора случайных чисел при каждом его запуске. Если вы замените семя, вы действительно получите разные результаты. Во-вторых, если вы не измените начальное значение, а измените количество попыток, вы также получите различные результаты. Попробуйте увеличить или уменьшить на порядок, чтобы понять, что я имею в виду. В-третьих, происходит некоторое целочисленное усечение или округление, когда ожидаемые значения не совсем точны. Возможно, этого недостаточно, чтобы изменить ситуацию, но она есть.

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

Генератор случайных чисел можно представить как работающий с потоком двоичных цифр. Генератор превращает поток в числа, разбивая его на куски. Если std:randфункция работает с RAND_MAX32767, то в каждом срезе используется 15 бит.

Если взять модули числа от 0 до 32767 включительно, то окажется, что 5462 нулей и единиц, но только 5461 двойка, тройка, четверка и пятерка. Следовательно, результат необъективен. Чем больше значение RAND_MAX, тем меньше будет смещение, но оно неизбежно.

Что не является предвзятым, так это число в диапазоне [0 .. (2 ^ n) -1]. Вы можете сгенерировать (теоретически) лучшее число в диапазоне 0..5, извлекая 3 бита, преобразовывая их в целое число в диапазоне 0..7 и отклоняя 6 и 7.

Можно надеяться, что каждый бит в потоке битов имеет равные шансы быть «0» или «1» независимо от того, где он находится в потоке или от значений других битов. На практике это исключительно сложно. Множество различных реализаций программных ГПСЧ предлагают разные компромиссы между скоростью и качеством. Такой линейный конгруэнтный генератор std::randпредлагает максимальную скорость при низком качестве. Криптографический генератор обеспечивает высочайшее качество при минимальной скорости.