在具有常数和的范围内生成N个随机数

Question

我想生成从[a,b]之间的特定分布(例如,均匀随机)中抽取的N个随机数,它们总和为常数C.我尝试了几种我能想到的解决方案,有些提议在类似的线程但是他们中的大多数要么是为有限形式的问题工作,要么我无法证明结果仍然遵循预期的分布.

我尝试过:生成N个随机数,将它们全部除以它们的总和并乘以所需的常数.这似乎有效,但结果并不遵循数字应在[a:b]范围内的规则.

Generage N-1随机数加0和期望的常数C并对它们进行排序.然后计算每两个连续nubmers之间的差异,结果是差异.这再次总结为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

如果您希望样本遵循均匀分布,则问题会减少以生成具有sum = 1的N个随机数.这反过来是Dirichlet分布的特殊情况,但也可以使用指数分布更容易地计算.方法如下:

1. 取均匀样本v ₁ ... v _N,所有v _i在0和1之间.
2. 对于所有i,1 <= i <= N,定义u _i:= -ln v _i(注意u _i > 0).
3. 归一化ü _我为p _我:= U _我/s其中s是器和U ₁ + ... + U _Ñ.

p ₁ ..p _N均匀分布(在dim N-1的单形中)并且它们的和为1.

你现在可以将这些p _i乘以你想要的常数C,然后通过将这样的其他常数A相加来转换它们

q _i:= A + p _i*C.

编辑3

为了解决评论中提出的一些问题,请允许我添加以下内容:

• 为了确保最终随机序列落在区间[a,b]中,选择上面的常数A和C为A:= a和C:= ba,即取q _i = a + p _i*(ba).由于p _i在范围(0,1)内,所以q _i将在[a,b]范围内.
• 如果v _i恰好为0,则不能取(负)对数-ln(v _i),因为ln()未定义为0.这种事件的概率极低.但是,为了确保没有错误信号,上面第₁项中的v ₁ ... v _N的生成必须以特殊方式威胁任何0的出现:将-ln(0)视为+无穷大(记住:ln( x) - > -infinity当x-> 0).因此,总和s = +无穷大,这意味着p _i = 1而所有其他p _j = 0.没有这种约定,序列(0 ... 1 ... 0)将永远不会生成(非常感谢@Severin Pappadeux这个有趣的评论.)
• 正如@Neil Slater 在问题所附的第4条评论中所解释的那样,逻辑上不可能满足原始框架的所有要求.因此,任何解决方案都必须将约束放宽到原始约束的适当子集.@Behrooz的其他评论似乎证实在这种情况下这就足够了.

编辑2

评论中还提出了另一个问题:

为什么重新定制均匀样品是不够的？

换句话说,我为什么要费心去采取负对数？

原因是如果我们只是重新缩放,那么得到的样本将不会在整个片段(0,1)上均匀分布(或者[a,b]用于最终样本.)

为了想象这个,让我们想想2D,即让我们考虑N = 2的情况.均匀样本(v ₁,v ₂)对应于具有原点(0,0)和角(1,1)的正方形中的随机点.现在,当我们将这个点除以s和v ₁ + v ₂这一点进行归一化时,我们正在做的是将点投影到对角线上,如图所示(请记住,对角线是线x + y = 1):

但是,由于从(0,0)到(1,1)更接近主对角线的绿线比靠近轴x和y的橙色长,所以投影倾向于在投影线的中心(蓝色),缩放样本存在的位置.这表明简单的缩放不会在所描绘的对角线上产生均匀的样本.另一方面,可以在数学上证明负对数确实产生所需的均匀性.因此,我会邀请每个人实施这两种算法,并检查结果图的行为与此答案所描述的一样,而不是复制数学证明.

(注意: 这是一篇关于这个有趣主题的博客文章,其中有一个应用于石油和天然气行业)

Answer 2

让我们尝试简化问题。通过减去下界，我们可以将其简化为在[0,ba]中找到N 个数字，使得它们的总和为C-Na。

重命名参数，我们可以在[0,m]中查找总和为S的N 个数字。

现在的问题类似于将长度为S的段划分为N 个长度为[0,m]的不同子段。

我认为这个问题根本无法解决。

如果 S=1、N=1000 且 m 大于 0，则唯一可能的重新分配是 1 个 1 和 999 个 0，这与随机分布完全不同。

N、m和S之间存在相关性，即使随机取值也不会使其消失。

对于最均匀的重新分配，子段的长度将遵循平均值为S/N的高斯曲线。

如果你以不同的方式调整你的随机数，你最终会得到任何偏差，但最终你永远不会同时拥有统一的 [a,b] 重新分配和 C 的总长度，除非你的 [a,b] 的长度间隔恰好是2C/Na。