Arc4random смещено по модулю

Согласно этой документации,

arc4random_uniform() рекомендуется над конструкциями типа arc4random() % upper_bound, поскольку это позволяет избежать "смещения по модулю", когда верхняя граница не является степенью двух.

Насколько плоха предвзятость? Например, если я генерирую случайные числа с верхней границей 6, в чем разница между использованием arc4random с % и arc4random_uniform()?

1 11
objective-c random probability arc4random

1 ответ:

Arc4random () возвращает 32-разрядное целое число без знака, то есть значения находятся между 0 и 2^32-1 = 4 294 967 295.

Теперь смещение возникает из-за того, что множество подинтервалов, созданных с помощью модули не вписываются точно в диапазон случайных выходных данных. Давайте представим для ясности генератор случайных чисел, который создает числа от 0 до 198 включающий. Вам нужны числа от 0 до 99, поэтому вы вычисляете random () % 100, уступая от 0 до 99:

0 % 100 = 0
99 % 100 = 99
100 % 100 = 0
198 % 100 = 98

Вы видите, что 99-это единственное число, которое может произойти только один раз , в то время как все другие могут произойти дважды в ходе выполнения. Это означает, что вероятность для 99 ровно вдвое, что также является худшим случаем в уклоне, где по крайней мере Задействованы 2 субинтервала.
Поскольку все степени двух меньших, чем интервал диапазона, хорошо вписываются в 2^32 интервал, смещение исчезает в этом случае.

Отсюда вытекает, что чем меньше результирующий набор с модулем и выше чем больше диапазон случайного выхода, тем меньше смещение. В вашем примере 6-это ваш верхний граница (я предполагаю, что 0-это нижняя граница), поэтому вы используете % 7, в результате чего 0-3 происходит 613 566 757 раз, в то время как 4-6 происходит 613 566 756 раз.
Так что 0-3-это 613 566 757 / 613 566 756 = 1,0000000016298 раз более вероятно чем 4-6.

Хотя это кажется легким отклонить, некоторые эксперименты (особенно Монте-Карло эксперименты) были испорчены именно потому, что эти, казалось бы, невероятные маленький различия были очень важны.

Еще хуже смещение, если требуемый выходной диапазон больше , чем случайный диапазон цели. Пожалуйста, прочтите запись Fisher-Yates shuffle потому что многие покерные сайты узнали на собственном горьком опыте, что нормальная линейная конгруэнтные генераторы случайных чисел и плохие алгоритмы перетасовки привели к палубы невозможно или весьма вероятным палубы или, что еще хуже, предсказуемо.

17