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

Я хочу генератор случайных чисел с неравномерным распределением, а именно:

// 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 Функция возвращает независимые равномерно распределенные целые числа в заданном диапазоне.

Другие вопросы по тегам