Случайные значения с неравномерным распределением
Я хочу генератор случайных чисел с неравномерным распределением, а именно:
// prints 0 with 0.1 probability, and 1 with 0.9 probability
echo probRandom(array(10, 90));
Вот что у меня сейчас:
/**
* method to generated a *not uniformly* random index
*
* @param array $probs int array with weights
* @return int a random index in $probs
*/
function probRandom($probs) {
$size = count($probs);
// construct probability vector
$prob_vector = array();
$ptr = 0;
for ($i=0; $i<$size; $i++) {
$ptr += $probs[$i];
$prob_vector[$i] = $ptr;
}
// get a random number
$rand = rand(0, $ptr);
for ($i=0, $ret = false; $ret === false; $i++) {
if ($rand <= $prob_vector[$i])
return $i;
}
}
Кто-нибудь может придумать лучший способ? Возможно, тот, который не требует от меня предварительной обработки?
2 ответа
В своем решении вы генерируете накопленный вектор вероятности, что очень полезно.
У меня есть два предложения по улучшению:
- если
$probs
статичны, то есть это один и тот же вектор, каждый раз, когда вы хотите сгенерировать случайное число, вы можете предварительно обработать$prob_vector
только один раз и держи его. - Вы можете использовать бинарный поиск для
$i
(Метод деления Ньютона)
РЕДАКТИРОВАТЬ: Теперь я вижу, что вы просите решение без предварительной обработки.
Без предварительной обработки вы получите худшее линейное время выполнения (т. Е. Удвоение длины вектора, и ваше время выполнения также удвоится).
Вот метод, который не требует предварительной обработки. Это, однако, требует, чтобы вы знали максимальный предел элементов в $probs
:
Метод отклонения
- Выбрать случайный индекс,
$i
и случайное число,X
(равномерно) между0
а такжеmax($probs)-1
включительно. - Если
X
меньше чем$probs[$i]
, вы сделали -$i
ваше случайное число - В противном случае отклонить
$i
(отсюда и название метода) и перезапустите.
Если вы знаете сумму всех элементов в $probs
Вы можете сделать это без предварительной обработки.
Вот так:
$max = sum($probs);
$r = rand(0,$max-1);
$tot = 0;
for ($i = 0; $i < length($probs); $i++) {
$tot += $probs[$i];
if ($r < $tot) {
return $i;
}
}
Это будет делать то, что вы хотите во время O(N), где N - длина массива. Это жесткая нижняя граница для алгоритмического времени выполнения такого алгоритма, поскольку каждый элемент на входе должен быть рассмотрен.
Вероятность данного индекса $i
выбран $probs[$i]/sum($probs)
учитывая, что rand
Функция возвращает независимые равномерно распределенные целые числа в заданном диапазоне.