分布不均匀的随机值 [英] Random values with non-uniform distribution

问题描述

我想要一个分布不均匀的随机数生成器，即:

I want a random number generator with non-uniform distribution, ie:

// 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;
    }   
}

谁能想到更好的方法?可能不需要我进行预处理吗?

Can anyone think of a better way? Possibly one that doesn't require me to do pre-processing?

推荐答案

在您的解决方案中，您将生成一个累积的概率矢量，这非常有用.

In your solution you generate an accumulated probability vector, which is very useful.

我有两个改进建议:

• 如果$probs是静态的，即每次要生成随机数时它都是相同的向量，则只需对$prob_vector进行一次预处理并将其保留.
• 您可以对$i(牛顿二分法)使用二进制搜索

• if $probs are static, i.e. it's the same vector every time you want to generate a random number, you can preprocess $prob_vector just once and keep it.
• you can use binary search for the $i (Newton bisection method)

编辑:我现在看到您要求不进行预处理的解决方案.

I now see that you ask for a solution without preprocessing.

如果不进行预处理，最终将导致线性运行时间最差(即向量长度增加一倍，运行时间也将增加一倍).

Without preprocessing, you will end up with worst case linear runtime (i.e., double the length of the vector, and your running time will double as well).

这里是不需要预处理的方法.但是，它确实需要您了解$probs中的元素的最大限制:

Here is a method that doesn't require preprocessing. It does, however, require you to know a maximum limit of the elements in $probs:

拒绝方法

• 选择一个随机索引$i和一个随机数X(均匀地)在0和max($probs)-1之间(包括两端).
• 如果X小于$probs[$i]，则说明操作完成-$i是您的随机数
• 否则，拒绝 $i(因此方法名称)并重新启动.

• Pick a random index, $i and a random number, X (uniformly) between 0 and max($probs)-1, inclusive.
• If X is less than $probs[$i], you're done - $i is your random number
• Otherwise reject $i (hence the name of the method) and restart.

这篇关于分布不均匀的随机值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！