Насколько неравномерно распределение случайных чисел при делении по модулю?

#cpp #случайные_числа #генерация_случайных_данных

В соседнем вопросе зашла речь о неравномерности распределения чисел при использовании
ГСЧ и деления по модулю. То же упоминается и в доках (rand):


  Notice though that this modulo operation does not generate uniformly distributed
random numbers in the span (since in most cases this operation makes lower numbers
slightly more likely).


Возьмем пример ГСЧ от 0 до 1000 с шагом 25:

return 25 * (rand() % 41); // Неравномерное распределение 

return int((40.0 * rand()) / (RAND_MAX + 1.0)) * 25; // Равномерное распределение


Так вот вопросы:
 - насколько неравномернее первый подход, чем второй?
 - насколько этот эффект проявляется в практических задачах?
 - стоит ли об этом беспокоиться?
 - если стоит, то начиная с какого момента?
 - какие есть варианты обхода неравномерности (кроме приведенного примера)?
    

Ответы

Ответ 1

Для реализаций, где RAND_MAX равно 32767, это может быть заметно.
Например если нам нужно получить число от 0 до 9999, при использовании

rand() % 10000


для значений до 2767 будет больше на 25% вероятности выпадения, т.к. они попадают 
в диапазоны rand: 

0..2767, 10000..12767, 20000..22767, 30000..32767


в то время как для значений 2768..9999 диапазоны rand:

2768..9999, 12768..19999, 22768..29999


Если результат используется для выбора выигрышного билета в серии, то рекомендовал
бы покупать билеты с младшими номерами.

Соответственно чем больше RAND_MAX и меньше делитель, тем равномернее распределение
при подходе с модулем.


Ответ 2

-насколько неравномернее первый подход, чем второй?


Неравномерность этих подходов проистекает из двух источников:


Мы проецируем дискретный диапазон одного размера на дискретный диапазон другого размера,
и размер первого в общем случае не кратен размеру второго. В такой проекции всегда
неизбежно будет возникать одна и та же "неравномерность" вероятности выбора одних целевых
значений перед другими. В этих двух вариантах более вероятные значения будут по-разному
размазаны по целевому диапазону, но это не принципиальное отличие. 

Как вы ни пытайтесь рассадить 7 голубей по 5 гнездам, неравномерность во всех вариантах
рассадки будет одна и та же.

То есть с этой точки зрения оба варианта совершенно одинаково неравномерны. Как вы
ни крутитесь со способами выполнения такой проекции, ничего нового достичь не удастся
- все проекции будут одинаково неравномерны. 
В первом случае мы извлекаем "случайность" из младших битов результата rand(), а
во втором - из старших. Простейшие реализации rand() как раз страдают тем, что предоставляют
неравномерное или недостаточно "случайное" распределение либо в младших, либо в старших
битах rand(). Поэтому с этой точки зрения при выборе способа выполнения проекции следует
учитывать характеристики вашей реализации rand().

Упоминание "в доках" того, что вариант с модулем якобы "хуже" - отсылка именно к
этому фактору, а совсем не к тому, что описано выше (пункт 1). Однако это не более
чем исторический курьез, элемент программистского фольклора, опирающийся на одну из
первых, плохо продуманных реализаций rand() с очень предсказуемым распределением младших
битов (см. самый первый здесь). В реальности же, не зная характеристик конкретного
rand(), невозможно сделать вывод о том, какой способ лучше в этом отношении.


Процитированное вами замечание "в доках" относится именно ко второму пункту, а ваш
вопрос, похоже, посвящен именно первому. Это существенно разные темы.


  -насколько этот эффект проявляется в практических задачах?
  -стоит ли об этом беспокоиться?
  -если стоит, то начиная с какого момента?


Зависит от практической задачи. Ясно, что качество rand() недостаточно для, скажем,
криптографических задач. В то же время его более чем достаточно, например, для генерации
случайных чисел для вероятностной структуры данных, вроде SkipList и т.п. В этом случае
ни о чем беспокоиться не нужно вообще.


  какие есть варианты обхода неравномерности (кроме приведенного примера)?


Сразу: ваш "приведенный пример" никак не обходит неравномерность, как сказано выше.

Совершенно одинаковая по своей сути неравномерность при всех способах проекции диапазонов
возникает потому, что проекция является "фиксированной", stateless: большую вероятность
выбора всегда получают одни и те же значения целевого диапазона. Тут приходит в голову
естественная мысль наделить сам процесс проекции состоянием, которое будет некоторым
образом "двигать" проекцию по целевому диапазону от вызова к вызову, т.е. дополнительно
"размазывать" неравномерность проекции по целевому диапазону. 

В самом простейшем случае можно было бы поступить так

// Вместо
return rand() % 41;

// делаем
static unsigned shift = 0;
shift = (shift + 1) % 41;
return (rand() % 41 + shift) % 41;


Но на самом деле практически того же эффекта "подавления неравномерности" достигнет
простое расширения диапазона rand() (например, путем конкатенации результатов двух
последовательных вызовов rand()).