分布式概率随机数发生器

Question

我想根据分布式概率生成一个数字.例如,只是说每个数字都有以下几种:

Number| Count           
1    |  150                
2    |  40          
3    |  15          
4    |  3  

with a total of (150+40+15+3) = 208     
then the probability of a 1 is 150/208= 0.72    
and the probability of a 2 is 40/208 = 0.192    

如何根据此概率分布创建一个返回数字的随机数生成器？

我很高兴现在基于静态的硬编码集,但我最终希望它从数据库查询中获得概率分布.

我见过像类似的例子这一个 ,但他们都不是很普通的.有什么建议？

Answer 1

一般方法是将均匀分布的随机数从0..1间隔馈送到所需分布的累积分布函数的倒数.

因此,在您的情况下,只需从0..1(例如with Random.NextDouble())中绘制一个随机数x,并根据其值返回

• 1如果0 <= x <150/208,
• 2如果150/208 <= x <190/208,
• 3如果190/208 <= x <205/208和
• 4否则.

Answer 2

只做一次：

• 编写一个函数，计算给定 pdf 数组的 cdf 数组。在您的示例中，pdf 数组为 [150,40,15,3]，cdf 数组为 [150,190,205,208]。

每次都这样做：

• 在 [0,1) 中获取一个随机数，乘以 208，向上截断（或向下截断：我留给您考虑极端情况）您将得到 1..208 中的整数。将其命名为 r。
• 对 r 的 cdf 数组执行二分搜索。返回包含 r 的单元格的索引。

运行时间将与给定 pdf 数组大小的 log 成正比。哪个好。但是，如果您的数组大小总是很小（在您的示例中为 4），那么执行线性搜索会更容易并且性能也会更好。

Answer 3

有很多方法可以生成具有自定义分布（也称为离散分布）的随机整数。选择取决于许多因素，包括可供选择的整数数量、分布的形状以及分布是否会随时间变化。

使用自定义权重函数选择整数的最简单方法之一f(x)是拒绝采样方法。以下假设的最高可能值f是max。拒绝采样的时间复杂度平均是恒定的，但在很大程度上取决于分布的形状，最坏的情况是永远运行。要k使用拒绝采样在 [1, ] 中选择一个整数：

1. i在 [1, k] 中选择一个统一的随机整数。
2. 以概率f(i)/max，返回i。否则，转到步骤 1。

其他算法的平均采样时间不太依赖于分布（通常是常数或对数），但通常需要您在设置步骤中预先计算权重并将它们存储在数据结构中。其中一些在平均使用的随机位数量方面也是经济的。这些算法包括别名方法、Fast Loaded Dice Roller、Knuth-Yao 算法、MVN 数据结构等。有关调查，请参阅我的“带替代品的加权选择”部分。

以下 C# 代码实现了 Michael Vose 版本的别名方法，如本文所述；另见这个问题。为了您的方便，我编写了此代码并在此处提供。

public class LoadedDie {
    // Initializes a new loaded die.  Probs
    // is an array of numbers indicating the relative
    // probability of each choice relative to all the
    // others.  For example, if probs is [3,4,2], then
    // the chances are 3/9, 4/9, and 2/9, since the probabilities
    // add up to 9.
    public LoadedDie(int probs){
        this.prob=new List<long>();
        this.alias=new List<int>();
        this.total=0;
        this.n=probs;
        this.even=true;
    }
    
    Random random=new Random();
    
    List<long> prob;
    List<int> alias;
    long total;
    int n;
    bool even;

    public LoadedDie(IEnumerable<int> probs){
        // Raise an error if nil
        if(probs==null)throw new ArgumentNullException("probs");
        this.prob=new List<long>();
        this.alias=new List<int>();
        this.total=0;
        this.even=false;
        var small=new List<int>();
        var large=new List<int>();
        var tmpprobs=new List<long>();
        foreach(var p in probs){
            tmpprobs.Add(p);
        }
        this.n=tmpprobs.Count;
        // Get the max and min choice and calculate total
        long mx=-1, mn=-1;
        foreach(var p in tmpprobs){
            if(p<0)throw new ArgumentException("probs contains a negative probability.");
            mx=(mx<0 || p>mx) ? P : mx;
            mn=(mn<0 || p<mn) ? P : mn;
            this.total+=p;
        }
        // We use a shortcut if all probabilities are equal
        if(mx==mn){
            this.even=true;
            return;
        }
        // Clone the probabilities and scale them by
        // the number of probabilities
        for(var i=0;i<tmpprobs.Count;i++){
            tmpprobs[i]*=this.n;
            this.alias.Add(0);
            this.prob.Add(0);
        }
        // Use Michael Vose's alias method
        for(var i=0;i<tmpprobs.Count;i++){
            if(tmpprobs[i]<this.total)
                small.Add(i); // Smaller than probability sum
            else
                large.Add(i); // Probability sum or greater
        }
        // Calculate probabilities and aliases
        while(small.Count>0 && large.Count>0){
            var l=small[small.Count-1];small.RemoveAt(small.Count-1);
            var g=large[large.Count-1];large.RemoveAt(large.Count-1);
            this.prob[l]=tmpprobs[l];
            this.alias[l]=g;
            var newprob=(tmpprobs[g]+tmpprobs[l])-this.total;
            tmpprobs[g]=newprob;
            if(newprob<this.total)
                small.Add(g);
            else
                large.Add(g);
        }
        foreach(var g in large)
            this.prob[g]=this.total;
        foreach(var l in small)
            this.prob[l]=this.total;
    }
    
    // Returns the number of choices.
    public int Count {
        get {
            return this.n;
        }
    }
    // Chooses a choice at random, ranging from 0 to the number of choices
    // minus 1.
    public int NextValue(){
        var i=random.Next(this.n);
        return (this.even || random.Next((int)this.total)<this.prob[i]) ? I : this.alias[i];
    }
}

例子：

 var loadedDie=new LoadedDie(new int[]{150,40,15,3}); // list of probabilities for each number:
                                                      // 0 is 150, 1 is 40, and so on
 int number=loadedDie.nextValue(); // return a number from 0-3 according to given probabilities;
                                   // the number can be an index to another array, if needed

我将此代码放在公共领域。