случайно в диапазоне, присутствует ли смещение числа для новой версии rand ()?

Что происходит, когда вы запускаете эти процедуры через набор? Вы получаете уклон
как rand ()?

Ответ таков: это зависит от соотношения между размером диапазона, возвращаемого генератором, и делителем при работе по модулю. Если делитель неравномерно делит диапазон, распределение будет искажено. Отношение смещения находится в диапазоне [1, 2], где 1 означает отсутствие смещения (как для равномерного распределения), и смещение увеличивается с делителем. относительно arcrandom4() это приводит к искаженному распределению, полученному во всех случаях, когда делитель по модулю не является четным делителем 2 ^ 32. Обоснование этого объясняется ниже.

---

Вступление. Уклон

Представьте, что мы пытаемся смоделировать равномерное распределение int на интервале [0, 99] с

int x = rand() % 100;

Оператор% делает распределение вероятности X перекошенным, потому что RAND_MAX, который является максимальным значением для rand (), может быть не равен k * 100 + 99. Это приводит к тому, что, если вы представите все части длиной 100 в диапазоне 0-RAND_MAX, то вы можете видим, что последняя часть, вероятно, не даст полный диапазон 0-99. Поэтому у вас есть больше чисел, которые генерируют 0, 1, 2 …, p, но не обязательно p + 1, …, 98, 99 (еще 1 вхождение для каждого числа в 0, 1, 2, …, p ). Неточность этого подхода увеличивается с увеличением делитель, который не делит диапазон равномерно и максимальный уклон по сравнению с равномерным распределением равен 2.

В следующих разделах ниже мы показываем, что смещение, измеренное как отношение вероятности получения числа из [0, p] к вероятности числа из [p + 1, n], равно (к + 1) / к и мы подтверждаем это 2 примерами.

---

формула

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

x = rand() % ( n + 1)

где rand() какой-то генератор и ( n + 1) делитель в операции по модулю. Картинка ниже показывает нашу точку зрения:

Мы можем видеть, как числа в диапазоне [ 0, n] делятся на те, которые повторяют k + 1 раз (числа [ 0, p]) и это повторяется k раз (числа [ p + 1, n]) в одном испытании, которое «взять число из распределения, полученного x = rand() % (n+1)«. п определяется как остаток при делении максимального числа (то есть Rand_MAX), заданного генератором, на (n + 1), которое является размером желаемого диапазона:

p = (N — 1)% (n + 1)

N — 1 = k * (n + 1) + p

и К это частное

k = (N — 1 — p) / (n + 1)

В одном испытании есть

(p + 1) * (k + 1) + (n — p) * k =

= p + 1 + k (n + 1) = N

возможные результаты. Таким образом, вероятность получения элемента, который повторяется k раз, равна k / N. Обозначим

f_0 = (k + 1) / N, вероятность для каждого элемента из [0, p]

f_1 = k / N, вероятность для каждого элемента из [p + 1, n]

Допустим, что мы будем выражать смещение выборки из этого, преобразованного распределения по равномерному распределению как отношение вероятности элемента, который принадлежит [ 0, p] к вероятности элемента из диапазона [ p + 1, n]:

смещение = f_0 / f_1 = (k + 1) / k

Итак, числа вдвое чаще?

Нет. Тот факт, что когда мы смотрим на повторяемость чисел на снимках, не подразумевает отношение 2. Это отношение является особым случаем, если диапазон генератора делится ровно на 2 поддиапазона. В общем случае отношение смещения составляет (k + 1) / k и асимптотически уменьшается, когда делитель n + 1 стремится к 1 (а k стремится к N).

---

Примеры

Теперь рассмотрим два простых примера (как предложено @dyp). Сначала мы сгенерируем 1000 * 1000 образцов из распределения, заданного

x = rand ()% m

с генератором std::uniform_int_distribution<> dist(0, 19) и делитель m = n + 1 равен 15, а следующий равен 6.

Пример 1

int x = rand() % 15; // n + 1 = 15, rand is uniform distribution over [0,19]

Тестовая программа:

#include <iostream>
#include <random>
#include <vector>

int main()
{
std::random_device rd;
std::mt19937 mt(rd());
std::uniform_int_distribution<> dist(0, 19);
std::vector<int> v(15);
const int runs = 1000 * 1000;
for (int i = 0; i < runs; ++i)
{
++v[dist(mt) % v.size()];
}

for (int i = 0; i < v.size(); ++i)
{
std::cout << i << ": " << v[i] << "\n";
}
}

код

результат:

0: 100500
1: 100016
2: 99724
3: 99871
4: 99936
5: 50008
6: 49762
7: 50023
8: 50123
9: 49963
10: 50117
11: 50049
12: 49885
13: 49760
14: 50263

Мы видим, что в этом случае числа в диапазоне [0, p] = [0, 4] появляются примерно в два раза чаще, чем остальные. Это соответствует нашей формуле смещения

смещение = f_0 / f_1 = (k + 1) / k = 2/1

Пример 2

int x = rand() % 6; // n + 1 = 6, rand is uniform distribution over [0,19]

Тестовая программа:

#include <iostream>
#include <random>
#include <vector>

int main()
{
std::random_device rd;
std::mt19937 mt(rd());
std::uniform_int_distribution<> dist(0, 19);
std::vector<int> v(6);
const int runs = 1000 * 1000;
for (int i = 0; i < runs; ++i)
{
++v[dist(mt) % v.size()];
}

for (int i = 0; i < v.size(); ++i)
{
std::cout << i << ": " << v[i] << "\n";
}
}

код

результат:

0: 199875
1: 199642
2: 149852
3: 149789
4: 150237
5: 150605

В этом случае мы видим, что числа в диапазоне [0, p] = [0, 1] появляются не вдвое чаще, чем остальные, но в соотношении примерно 20/15. На самом деле это 4/3, так как наша формула смещения в этом случае

смещение = f_0 / f_1 = (k + 1) / k = 4/3

Картинка ниже помогает понять этот результат.

полный код