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