Равномерно распределенные случайные числа относительно просты с 2

Конкретный пример

Мне нужно сгенерировать случайное число от 0 до 2 включительно. (или выберите случайным образом между -1, 0 и 1).

Наивный подход заключался бы в том, чтобы сделать что-то вроде rand() mod 3, где rand() возвращает целое число. Этот подход не будет генерировать статистически случайные числа, если верхняя граница rand() не является относительно простой (а нижняя граница равна 0).

Например, предполагая, что rand () вернула 2 бита (от 0 до 3 включительно), модуль будет отображать:

0 -> 0
1 -> 1
2 -> 2
3 -> 0

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

Общий вопрос

Есть ли способ сгенерировать равномерно распределенное случайное число от 0 до n-1 включительно, где n относительно просто 2?


random language-agnostic discrete-mathematics
person Sufian    schedule 29.06.2009    source источник

Ответы (4)


arrow_upward
3
arrow_downward

Обычный подход - отбросить случайные значения выше последнего полного цикла и просто запросить новое случайное число.

person SingleNegationElimination    schedule 29.06.2009

arrow_upward
2
arrow_downward

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

Если невозможно уменьшить верхнюю границу, вы можете выбрать k так, чтобы k * n было как можно ближе к верхней границе rand (), и отбросить результаты выше этого числа, повторив попытку.

person Saulius Žemaitaitis    schedule 29.06.2009

arrow_upward
1
arrow_downward

См. мой ответ на аналогичный вопрос.

В общем, используйте свой ГСЧ и отбросьте все, что выше N, и попробуйте еще раз. Для оптимизации вы можете использовать мод и отбросить все, что выше n * floor (MAX / n)

person FryGuy    schedule 29.06.2009

arrow_upward
0
arrow_downward

Общий ответ: вам нужно использовать больше, чем 2 бита числа.

Мое практическое правило - генерировать значения с плавающей запятой, x, 0.0 ‹= x‹ 1.0, умножать на 3 и усекать. Это должно дать вам значения в диапазоне 0, 1 и 2, которые зависят от большего количества бит.

person S.Lott    schedule 29.06.2009
comment
Внизу вы по-прежнему демонстрируете небольшую предвзятость в том, что вы используете число с плавающей запятой (31 бит сопоставления данных с 3 уникальными значениями). - person FryGuy; 30.06.2009
comment
Меньше, чем астрономическое отклонение от попытки сопоставить 4 значения (2 бита) с 2 значениями. Поскольку большинство ГСЧ представляют собой 48 бит фактической случайности, ваше смещение должно быть микроскопическим. Как часто вы будете генерировать миллиарды чисел, необходимых для измерения смещения? - person S.Lott; 30.06.2009