Случайные числа с неоднородными дискретными плотностями

Question

Просто интересно, что это за алгоритм,
или если есть более простой / более эффективный способ сделать это:

Скажем, нам дана определенная плотность вероятности, скажем,

prob[] = {.1, .15, .25, .05, .45}

1 группа - 10%
Группа 2 - 15%
Группа 3 - 25%
Группа 4 - 5%
5 группа - 45%

и случайное число, (0,1),
побежал = .853234

Вставьте в одну из 5 групп

if (ran <=prob[0]) selection = 1;  
else if (ran <= prob[0]+prob[1]) selection = 2;  
...
else if (ran <= prob[0]+prob[1]+...+prob[4]) selection = 5;  

Я не очень хорошо разбираюсь в генерации случайных чисел

Answer 1

То, что вы в основном делаете здесь, это инвертирование накопительной функции распределения. Позволять F быть CDF случайной величины X с данным распределением, то он определяется как F(x) == P[X <= x],

Здесь очень полезно то, что если вы генерируете случайную переменную U между 0 и 1, затем

P[F^-1(U) <= x] == P[U <= F(x)] == F(x) == P[X <= x]

Который означает, что F^-1(U) будет иметь такое же распределение, как X!

Конечно, это возможно только если вы можете инвертировать CDF, но в вашем случае Fявляется кусочной функцией (например, лестница), и ваш алгоритм определяет, для данного равномерного значения, на каком шаге это значение встречается. Ваш алгоритм поэтому совершенно правильно.

Однако вы можете улучшить его, если у вас есть много случайных чисел для генерации: сначала сгенерируйте таблицу CDF, которая в вашем случае будет

CDF[] = {.1, .25, .5, .55, 1.}

затем для каждого сгенерированного равномерного числа от 0 до 1 просто выполните дихотомию для таблицы CDF, чтобы повторно получить соответствующий индекс.

Answer 2

Ваш алгоритм правильный. В вашем примере, однако, вероятности не складываются до 1.

Answer 3

Этот код будет работать, за исключением того, что ваши вероятности не прибавляют до 100% (так что ни один из операторов if может не совпадать).

Подход можно немного упростить, используя кумулятивное распределение вероятностей:

cumprob[5] = {.1, .2, .45, .50, 1.0};

Это также позволяет вам заменить lsearch на цепочку if-elif.

Answer 4

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

Вместо этого найдите наименьший общий знаменатель из заданных вами вероятностей (в вашем примере 5%) и используйте случайное целое число в [0,19], чтобы выбрать свою группу. Пример:

switch(random(19)) {
case 0:
case 1:
  selection = 1;
  break;
case 2:
case 3:
case 4:
  selection = 2;
  break;
case 5:
case 6:
case 7:
case 8:
case 9:
  selection = 3;
  break;
case 10:
  selection = 4;
  break;
case 11:
case 12:
case 13:
case 14:
case 15:
case 16:
case 17:
case 18:
case 19:
  selection = 4;
  break;
}