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

Question

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

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

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

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

ислучайное число, (0,1),
run = .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

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

Вместо этого найдите наименьший общий знаменатель из ваших заданных вероятностей (в вашем примере 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;
}

Answer 4

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

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

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

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