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

Modulo bias - это проблема, которая возникает, когда наивно использует модульную операцию, чтобы получить псевдослучайные числа, меньшие, чем заданная "верхняя граница".

Поэтому в качестве программиста C я использую модифицированную версию функции 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

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

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

Ответы

Ответ 1

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

Заметим, что 7 равномерно не делит на 256

256 = 7 * 36 + 4

Это означает, что наивное использование операции modulo для получения псевдослучайных чисел, меньших 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 отклоняет числа в нижней части диапазона. В частности, интервал A будет

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

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

outcome = N % 7

В интервале [4,256] имеется 252 числа, а так как 252 кратно 7, каждый результат на интервале [0,7] имеет равную вероятность.

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

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

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

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

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