无偏返回n个随机正数(>=0)的列表,以便它们的和==总和

好吧,我们要解决这个问题,假设需要生成一个长度为N的随机向量 均匀分布 在允许的空间内,重申如下:

鉴于

• 期望的总和S,

生成长度为N的随机向量V,使得随机变量V均匀地分布在其允许的空间中。

首先考虑N=3。允许值{U}的空间是垂直于向量[11 1]的平面的一部分,该向量[11 1]穿过点[1/3 1/3 1/3]并位于其分量范围在0和b之间的立方体内。这组点{U}的形状类似于六边形。

(待定:图片。我现在不能生成一个,我需要访问MATLAB或其他程序,可以做3D绘图。我的八度音阶不能。)

最好使用一个向量为[11 1]/sqrt(3)的正交加权矩阵W(见我的另一个答案)。其中一个矩阵是

octave-3.2.3:1> A=1/sqrt(3)
   A =  0.57735
octave-3.2.3:2> K=1/sqrt(3)/(sqrt(3)-1)
   K =  0.78868
octave-3.2.3:3> W = [A A A; A 1-K -K; A -K 1-K]
   W =

     0.57735   0.57735   0.57735
     0.57735   0.21132  -0.78868
     0.57735  -0.78868   0.21132

又是正交的(W*W=I)

如果考虑立方体的点[0 b]、[0 b b]、[0 b 0]、[b b 0]、[b 0 0]、[b 0 0]和[b 0 b],它们形成一个六边形,与立方体对角线的距离都是b*sqrt(2/3)。这些方法不能解决问题,但很快就有用了。其他两点[0 0]和[b b b]在立方体的对角线上。

正交加权矩阵W允许我们生成均匀分布在{U}内的点,因为正交矩阵是旋转/反射的坐标变换,不缩放或倾斜。

我们将生成在由W的3个向量定义的坐标系中均匀分布的点。第一个分量是立方体对角线的轴。U的分量之和完全取决于这个轴,而不是其他轴。因此,沿该轴的坐标被强制为1/sqrt(3),对应于点[1/3,1/3,1/3]。

另外两个分量在垂直于立方体对角线的方向上。由于到对角线的最大距离是b*sqrt(2/3),我们将生成-b*sqrt(2/3)和+b*sqrt(2/3)之间的均匀分布数(u,v)。

这给了我们一个随机变量U'=[1/sqrt(3)U v]。然后我们计算U=U'*W。一些结果点将超出允许范围(U的每个分量必须介于0和b之间),在这种情况下,我们拒绝它并重新开始。

换句话说:

1. 生成独立随机变量u和v,它们分别均匀分布在-b*sqrt(2/3)和+b*sqrt(3)之间。
2. 计算矢量U’=[1/sqrt(3)U v]
3. 计算U=U'*W。
5. 计算V=U*S。

对于更高维度(垂直于超立方体主对角线的超平面的一部分内的均匀分布点),该解是相似的:

预先计算秩N的加权矩阵W。

1. 生成独立随机变量u ,u个 _2个 , ... u型 _N-1号 均布于-b*k(N)和+b*k(N)之间。
2. 计算矢量U'=[1/N U ,u个 _{2个 N-1号} ]
3. 计算U=U'*W(有一些捷径,实际上必须构造并乘以W。)
5. 计算V=U*S。

范围k(N)是N的函数,表示边1的超立方体顶点与其主对角线的最大距离。我不确定一般公式,但它是sqrt(2/3),N=3,sqrt(6/5),N=5,可能有一个公式。

编辑:说得更清楚一点:你要N个数字和S相加吗?因此,在区间[0,1]上生成N个均匀分布的随机数,或者生成RNG生成的任意随机数。把它们加起来,它们就等于s的总和,而你要它们等于s的总和,所以把每一个数乘以s/s,我想现在这些数在[0,s/s]上是均匀随机分布的。

我会这样做:

1. 生成n-1个随机数,都在[0, max ]
3. 对于排序列表中由第i个和第(i+1)个数字组成的每一对,创建一个间隔(i,i+1)并计算其长度。最后一个间隔将从最后一个数字开始,在 最大值 第一个间隔将从0开始,在列表中的第一个数字结束。

现在,这些间隔的长度总和总是 最大值 ,因为它们只是表示[0, ].

代码(用Python编写):

#! /usr/bin/env python
import random

def random_numbers(n,sum_to):
    values=[0]+[random.randint(0,sum_to) for i in xrange(n-1)]+[sum_to]
    values.sort()
    intervals=[values[i+1]-values[i] for i in xrange(len(values)-1)]
    return intervals

if __name__=='__main__':
    print random_numbers(5,100)

如果你要找的是正态分布的数字,相关性越小越好,而且需要严格要求,我建议你采用以下数学方法并翻译成代码。

(*严格性:其他方法的问题是,您可以在分布中得到“长尾巴”——换句话说,很少有异常值,但可能有与预期输出非常不同的异常值)

• _0个 ,五 _1个 ,五 _2个 , ... 五 _N-1号
• 创建列向量V,其中V=[0 V ,五 _1个 ,五 _{2个 N-1号} ] ^T型
• 输出向量是W V+S U/N的乘积,其中S是所需的和,U是1的列向量。换句话说,第i个输出变量=(矩阵W的行i)和列向量V的点积,添加到序列号中。

**正交矩阵:这是最难的部分,我放进去了 a question at math.stackexchange.com 这里有一个简单的矩阵W,可以用3个不同的值来定义,这样你就不需要构造矩阵了。

W(1,i) = W(i,1) = 1/sqrt(N)
W(i,i) = 1 - K   for i >= 2 
W(i,j) = -K      for i,j >= 2, i != j
K = 1/sqrt(N)/(sqrt(N)-1)

马克方法的问题是:

如果你这样做,你会得到一个“长尾”分布。下面是MATLAB中的一个例子:

 >> X = rand(100000,10);
 >> Y = X ./ repmat(sum(X,2),1,10);
 >> plot(sort(Y))

我在矩阵X中生成了100000组N=10的数字,并创建了矩阵Y,其中Y的每一行是X的对应行除以其和(这样Y的每一行和为1.0)

绘制Y的排序值(每列分别排序)得到大致相同的累积分布:

真正的均匀分布会产生一条从0到最大值的直线。你会注意到它有点像一个真正的均匀分布,除了在末端有一个长尾。在0.2到0.5之间产生了一个多余的数字。N值越大,尾部就越差,因为尽管数字的平均值下降(平均值=1/N),但最大值保持在1.0:由9个0.0值和1个1.0值组成的向量是有效的,可以通过这种方式生成,但在病理上是罕见的。

如果你不在乎,那就用这个方法吧。而且可能有一些方法可以生成具有期望和的“几乎”均匀或“几乎”高斯分布,这些方法比我上面描述的方法简单得多,效率也更高。但我提醒你要小心,并理解你选择的算法的后果。

一种固定方法是,不留长尾,使事物均匀分布,如下所示:

1. 从0.0到1.0生成向量V=N均匀分布的随机数。
2. 求它们的和S和它们的最大值M。
3. 如果S<k*M(最大值太离群),请返回步骤1。我不确定k的值是多少,也许k=N/2?
4. 输出矢量V*S /S公司

N=10时的MATLAB示例:

 >> X = rand(100000,10);
 >> Y = X ./ repmat(sum(X,2),1,10);
 >> i = sum(X,2)>(10/2)*max(X,[],2);
 >> plot(sort(Y(i,:)))

我遇到了这个问题,特别需要整数。答案是使用多项式。

import numpy.random, numpy
total_sum = 20
n = 6

v = numpy.random.multinomial(total_sum, numpy.ones(n)/n)

multinomial documentation 解释说,你已经掷了20次公平的六面骰子。 v 五 必须加到二十。这里,六个是 n 二十是 total_sum .

用多项式,你也可以模拟不公平的骰子,这在某些情况下非常有用。

以下操作非常简单,并返回统一的结果:

def gen_list(numbs, limit_sum):
    limits = sorted([random.uniform(0, limit_sum) for _ in xrange(numbs-1)])
    limits = [0] + limits + [limit_sum]
    return [x1-x0 for (x0, x1) in zip(limits[:-1], limits[1:])]

这个想法很简单,如果你需要,比如说,5个介于0和20之间的数字,你可以简单地把4个“限制”放在0和20之间,然后得到(0,20)区间的一个分区。您需要的随机数只是排序列表中5个间隔的长度[0,random1,random2,random3,random4,20]。

你可以保持一个连续的总数而不必打电话 sum(my_sum) 反复。