Устранение погрешности по модулю: как это достигается в функции arc4random_uniform()?

Question

Ошибка модуляции - это проблема, возникающая при наименее использовании операции modulo для получения псевдослучайных чисел, меньших заданной «верхней границы».

Поэтому в качестве программиста С я использую модифицированную версию функции arc4random_uniform() для генерации равномерно распределенных псевдослучайных чисел.

Проблема в том, что я не понимаю, как работает функция, математически.

Это пояснительный комментарий функция, за ними следуют ссылки на полный исходный код:

/* 
* Calculate a uniformly distributed random number less than upper_bound 
* avoiding "modulo bias". 
* 
* Uniformity is achieved by generating new random numbers until the one 
* returned is outside the range [0, 2**32 % upper_bound). This 
* guarantees the selected random number will be inside 
* [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound) 
* after reduction modulo upper_bound. 
*/ 

http://cvsweb.openbsd.org/cgi-bin/cvsweb/src/lib/libc/crypt/arc4random_uniform.c?rev=1.1&content-type=text/x-cvsweb-markup

Из комментария выше мы можем определить:

• [2^32 % upper_bound, 2^32) - интервал A
• [0, upper_bound) - интервал B

Для того, чтобы работать, функция опирается на тот факт, что интервал отображения А к интервалу В.

Мой вопрос: математически, как же число в интервале карте равномерно на те, в интервале B? И есть ли доказательство этого?

Answer 1

Иногда это помогает начать с легко понятного примера, а затем обобщить оттуда. Чтобы все было просто, давайте предположим, что arc4random возвращает uint8_t вместо uint32_t, поэтому выход из arc4random является номером в интервале [0,256). А давайте выберем upper_bound из 7.

Обратите внимание, что 7 не делится равномерно на 256

256 = 7 * 36 + 4 

Это означает, что по наивности с помощью операции по модулю, чтобы получить псевдослучайных чисел меньше, чем 7 приведет к следующим распределением вероятностей

37/256 for outcomes 0,1,2,3 
36/256 for outcomes 4,5,6 

Это то, что известно как смещение по модулю, результаты 0,1,2,3 более вероятны, чем исходы 4,5,6.

Чтобы избежать смещения по модулю, мы могли бы просто отклонить значения 252,253,254,255 и сгенерировать новое число до тех пор, пока результат не будет в интервале [0,252). Все числа в интервале [0,252) имеют равную вероятность (отклонение более высоких чисел не влияет на распределение младших чисел). И так 7 делит равномерно на 252, результирующее распределение вероятности равномерно

36/252 for outcomes 0,1,2,3,4,5,6,7 

Это в основном то, что arc4random_uniform делает, за исключением того, что arc4random_uniform Rejects чисел в нижней части диапазона.В частности, интервал Д будет

[2^8 % 7, 2^8) which is [4, 256) 

После генерации множества (назовем его N) в интервале [4256) окончательный расчет

outcome = N % 7 

Есть 252 номера в интервале [4256), и поскольку 252 кратно 7, каждый результат на интервале [0,7] имеет равную вероятность.

---

Вот как arc4random_uniform работы, он отклоняет/повторы на небольшом диапазоне чисел и подсчета чисел в оставшемся диапазоне является кратным upper_bound. (Так как upper_bound обычно является небольшим числом по сравнению с 2^32, вероятность иметь несколько попыток для одного результата довольно мала).

Но вы действительно заботитесь о смещении по модулю? В большинстве случаев ответ: «Нет». Рассмотрим наш пример с верхней гранью 7. распределения вероятностей для реализации наивным по модулю является

613566757/4294967296 for outcomes 0,1,2,3 
613566756/4294967296 for outcomes 4,5,6 

который является смещение по модулю меньше, чем 0,0000002%.

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