我想从[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
注意输出中有多少个1,这听起来很合理,因为范围更大,但它们看起来并不像是均匀分布的,我不确定是否有可能达到我想要的,也许是约束使问题无法解决。
5条答案
按热度按时间wkyowqbh1#
如果您希望样本遵循均匀分布,则问题简化为生成N个sum = 1的随机数。反过来,这是狄利克雷分布的特例,但使用指数分布也可以更轻松地计算。
1.取所有vi均在0和1之间的均匀样本v1...vN。
1.对于所有i,1〈=i〈=N,定义ui:= -ln vi(注意ui〉0)。
1.将ui归一化为pi:= ui/s,其中s为u1+...+uN之和。
p1..pN是均匀分布的(在dim N-1的单纯形中),并且它们的和是1。
现在你可以把这些pi乘以你想要的常数C,然后把它们转换成另一个常数A的和,就像这样
齐:= A + π *C。
编辑3
为了解决评论中提出的一些问题,请允许我补充如下:
编辑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轴,投影线的中心附近的投影倾向于聚集更多(蓝色),缩放后的样本位于其中。这表明简单的缩放不会在所示对角线上生成均匀的样本。另一方面,可以从数学上证明负对数确实能产生理想的均匀性。2因此,我不想复制粘贴数学证明,而是邀请每个人实现这两种算法,并检查得到的曲线是否如这个答案所描述的那样。
(**注:**这里有一篇关于这个有趣主题的博客文章,并应用于石油和天然气行业)
5sxhfpxr2#
让我们试着简化这个问题,通过减去下界,我们可以把它简化为在**[0,b-a]中寻找N个数,使得它们的和为C-Na**。
重命名参数,我们可以在**[0,m]中查找N个数字,它们的和为S**。
现在,该问题类似于将长度为S的段划分为长度为**[0,m]的N**个不同子段。
我认为这个问题根本无法解决。
如果S=1,N=1000并且m大于0,则唯一可能的重新划分是一个1和999个0,这与随机散布完全不同。
N、m和S之间存在相关性,即使选取随机值也不会使其消失。
对于最均匀的再分配,子段的长度将遵循平均值为S/N的高斯曲线。
如果你对随机数做不同的调整,你最终会得到任何偏差,但最终你永远不会同时得到均匀的[a,b]重划分和总长度C,除非你的[a,b]区间的长度恰好是2C/N-a。
dgiusagp3#
对于我的答案,我将假设我们有一个均匀分布。
因为我们有一个均匀分布,所以
C
的每个元组都有相同的出现概率。例如,对于a = 2, b = 2, C = 12, N = 5
,我们有15
个可能的元组。从10
开始,2
。4
从3
开始,1
从4
开始。这给出了从1
到15
中选择一个随机数来选择第一个元素的想法。从1
到10
中,我们选择2
。从11
到14
,我们选择3
,对于15
,我们选择4
。可能结果:
这个算法对于大的
N
来说不能很好地扩展,因为在计算组合时会溢出(除非我们使用一个大的整数库),计算所需的时间以及需要任意大的随机数。hgqdbh6s4#
那么,对于n=10000,我们不能有一个小的数,不是随机的吗?
可能生成序列直到
sum > C-max
达到,然后只放入一个简单的数字来求和。万分之一更像是系统中非常小的噪音。
f4t66c6m5#
虽然这是一个老主题,但我想我有一个想法。考虑我们想要N个随机数,其总和为C,每个随机数在a和b之间。为了解决问题,我们创建N个洞,并准备C个球,每次我们问每个洞“你想要另一个球吗?"。如果否,我们传递到下一个洞,否则,我们把一个球放进洞。每个洞有一个上限值:b-a.如果某个孔达到上限值,则总是传递到下一个孔。
示例:
0和2之间的3个随机数,其和为5。
模拟结果:
第1次运行:-+-
第2次运行:++-
第3次运行:---
第4次运行:+*+
最终:221
+:接受焊球