c++ - 在一个具有恒定总和的范围内生成N个随机数

Question

我想生成一个从[a，b]之间的规范分布(例如均匀随机)得出的N个随机数，它们求和为一个常数C。我尝试了一些我可以想到的解决方案，其中一些在相似的线程上提出，但他们中的大多数要么只解决有限形式的问题，要么无法证明结果仍然符合期望的分布。

我尝试过的是:
生成N个随机数，将所有数除以它们的总和，然后乘以所需的常数。这似乎可行，但结果未遵循数字应在[a:b]之内的规则。

生成N-1个随机数，将0和所需的常数C相加并对其进行排序。然后计算每两个连续数字之间的差异，然后得出差异。这再次合计为C，但存在与上一个方法相同的问题(范围可以大于[a:b]。

我还尝试生成随机数，并始终保持最小值和最大值的方式保持所需的总和和范围，并提供以下代码:

bool generate(function<int(int,int)> randomGenerator,int min,int max,int len,int sum,std::vector<int> &output){
    /**
    * Not possible to produce such a sequence
    */
if(min*len > sum)
    return false;
if(max*len < sum)
    return false;

int curSum = 0;
int left = sum - curSum;
int leftIndexes = len-1;
int curMax = left - leftIndexes*min;
int curMin = left - leftIndexes*max;

for(int i=0;i<len;i++){
    int num = randomGenerator((curMin< min)?min:curMin,(curMax>max)?max:curMax);
    output.push_back(num);
    curSum += num;
    left = sum - curSum;
    leftIndexes--;
    curMax = left - leftIndexes*min;
    curMin = left - leftIndexes*max;
}

return true;
}

这似乎可行，但是结果有时会非常不正确，我不认为它遵循原始分布(例如统一)。例如:

//10 numbers within [1:10] which sum to 50:
generate(uniform,1,10,10,50,output);
//result:
2,7,2,5,2,10,5,8,4,5 => sum=50
//This looks reasonable for uniform, but let's change to 
//10 numbers within [1:25] which sum to 50:
generate(uniform,1,25,10,50,output);
//result:
24,12,6,2,1,1,1,1,1,1 => sum= 50

注意输出中存在多少个。这听起来合理，因为范围更大。但是它们确实看起来不像是一个统一的分布。
我不确定即使可以实现我想要的目标，也可能是制约因素使问题无法解决。

Answer 1

如果您希望样本遵循均匀分布，则问题会减少，以生成总和= 1的N个随机数。这又是Dirichlet分布的特例，但也可以使用指数分布更轻松地计算。方法如下:

取所有vi在0和1之间的统一样本v1…vN。

对于所有1 <= i <= N的i，定义ui:= -ln vi(注意ui> 0)。

将ui标准化为pi:= ui/s，其中s是u1 + ... + uN之和。

p1..pN是均匀分布的(在Dim N-1的单纯形中)，它们的和为1。

现在，您可以将这些pi与所需的常数C相乘，并通过将其他常数A相加来转换它们

qi:= A + pi * C。

编辑3

为了解决注释中提出的一些问题，让我添加以下内容:

为了确保最终的随机序列落在区间[a，b]中，请选择上面的常数A和C作为A:= a和C:= b-a，即qi = a + pi *(b-a)。由于pi在(0,1)范围内，因此所有qi都将在[a，b]范围内。

如果vi恰好为0，则不能采用(负)对数-ln(vi)，因为ln()未定义为0。此类事件的可能性极低。但是，为了确保没有错误发生，上述第1条中的v1 ... vN的生成必须以特殊方式威胁到任何出现0的情况:将-ln(0)视为+ infinity(记住:ln(x) ->-无穷大(x-> 0时)。因此，总和s = +无穷大，这意味着pi = 1而所有其他pj =0。如果没有这种约定，就永远不会生成序列(0 ... 1 ... 0)(这要感谢@Severin Pappadeux的帮助)有趣的话。)

正如@Neil Slater在问题所附的第4条评论中所解释的，从逻辑上讲，不可能满足原始框架的所有要求。因此，任何解决方案都必须将约束放宽到原始约束的适当子集。 @Behrooz的其他评论似乎证实，在这种情况下，这足够了。

编辑2

评论中又提出了一个问题:

为什么重新缩放均匀样本不足以满足要求？

换句话说，为什么我还要打个负对数呢？

原因是，如果我们只是重新缩放比例，那么结果样本将不会在(0,1)段(或最终样本的[a，b])中均匀分布。

为了可视化，让我们考虑2D，即，考虑N = 2的情况。均匀样本(v1，v2)对应于正方形中具有原点(0,0)和角(1,1)的随机点。现在，当我们将这样的点归一化为总和s = v1 + v2时，我们正在做的就是将点投影到对角线上，如图所示(请注意，对角线是x + y = 1的线) :

但是，鉴于从(0,0)到(1,1)更接近主对角线的绿线比接近于x和y轴的橙色线长，因此投影趋向于在投影线的中心(蓝色)，缩放后的样本所在的位置。这表明简单的缩放不会在所示的对角线上产生均匀的样本。另一方面，可以在数学上证明负对数确实产生所需的均匀性。因此，我将邀请所有人实现两种算法，并检查结果图是否按此答案所描述的那样运行，而不是复制数学证明。

( 注: here是有关此有趣主题的博客文章，并应用于石油和天然气行业)