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

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

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

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


person AJ222    schedule 14.07.2013    source источник


Ответы (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.

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

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

person Thorsten S.    schedule 14.07.2013
comment
Отличное объяснение проблемы. Читателей также может заинтересовать общедоступная реализация: opensource.apple.com/source/Libc/Libc-825.26/gen/FreeBSD/ Это правда, что во многих приложениях предвзятость не имеет значения, но она настолько разрушительна в тех случаях, когда она имеет значение. важно, чтобы у программистов всегда была привычка использовать _uniform. - person Rob Napier; 14.07.2013
comment
Как избежать предвзятости? - person Alexei Sholik; 14.07.2013
comment
@android, сократив диапазон выбора до чего-то, кратного желаемому, а затем прокатывая случайные числа, пока вы не окажетесь внутри диапазона. Если вы хотите получить случайное число от 1 до 4 на шестигранном кубике, правильный способ его получить — бросать его до тех пор, пока число не окажется между 1 и 4. Тот же принцип. - person Rob Napier; 14.07.2013
comment
Самый простой способ — перезапустить генератор случайных чисел при входе в запрещенный диапазон. например do { result = arc4random() % 7 } while (результат › 4 294 967 292). - person Thorsten S.; 14.07.2013