返回一个由n个随机正数（>=0）组成的列表，使它们的总和等于total_sum，且没有偏差。

Question

返回一个由n个随机正数（>=0）组成的列表，使它们的总和等于total_sum，且没有偏差。

15

我正在寻找一种算法或建议来改进我的代码，生成一组随机数，使它们的总和等于某个任意的数字。但是我的下面的代码会有偏差，因为第一个数字往往会比较大。

是否有更有效的选择数字的方法？

#!/usr/bin/python
'''
  Generate a list of 'numbs' positive random numbers whose sum = 'limit_sum'
'''

import random


def gen_list(numbs, limit_sum):
  my_sum = []
  for index in range(0, numbs):
    if index == numbs - 1:
      my_sum.append(limit_sum - sum(my_sum))
    else:
      my_sum.append(random.uniform(0, limit_sum - sum(my_sum)))

  return my_sum

#test
import pprint
pprint.pprint(gen_list(5, 20))
pprint.pprint(gen_list(10, 200))
pprint.pprint(gen_list(0, 30))
pprint.pprint(gen_list(1, 10))

输出结果

## output

[0.10845093828525609,
 16.324799712999706,
 0.08200162072303821,
 3.4534885160590041,
 0.031259211932997744]

[133.19609626532952,
 47.464880208741029,
 8.556082341110228,
 5.7817325913462323,
 4.6342577008233716,
 0.22532341156764768,
 0.0027495225618908918,
 0.064738336208217895,
 0.028888697891734455,
 0.045250924420116689]

[]

[10]

- dassouki

“random”: 请提供更多有关您所需分布和相关性的信息。注意：由于求和属性，这些数字不是独立的。（例如，如果您知道N-1个数字，则根据定义，您就知道剩余的数字。） - Jason S

正常或接近正态分布都可以。 - dassouki

2

这里普通的没有任何资格并不太有意义。统一的更有意义 - 大概意味着“在整个允许空间内统一”。 - comingstorm

@comingstorm：说高斯分布也没有问题（变量之间会有轻微的相关性），但我同意“在整个允许空间内均匀分布”是另一个选择。 - Jason S

尽管如果变量需要大于等于0，那么“normal”就没有意义。 - Jason S

7个回答

9

以下是我的做法：

随机生成 n-1 个数字，范围都在 [0,max] 之间。
排序这些数字。
对于排序后列表中第 i 和第 i+1 个数字组成的每一对，创建一个区间 (i,i+1) 并计算它的长度。最后一个区间将以列表中的最后一个数字开始并以 max 结束，而第一个区间将从 0 开始并以列表中的第一个数字结束。

现在，这些区间的长度总和将始终等于 max，因为它们只是位于 [0,max] 内部的段。

代码（用 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)

- MAK

2

我喜欢 - 我从没想过以那种方式去做。 - neil

1

该算法也存在长尾问题。（无不敬之意，这是一种勇敢的努力） - Jason S

7

如果您正在寻找尽可能少相关性的正态分布数字，并且需要对此进行严格处理*，我建议您采取以下数学方法并将其转换为代码。

(*严格: 其他方法的问题在于您的分布中可能会出现“长尾”--换句话说，有时会出现与预期输出非常不同的异常值)

生成 N-1 个独立同分布 (IID) 的高斯随机变量 v₀, v₁, v₂, ... v_N-1，以匹配问题的 N-1 自由度。
创建列向量 V，其中 V = [0 v₀, v₁, v₂, ... v_N-1]^T
使用固定加权矩阵 W，其中 W 包含一个正交矩阵**，其顶部行为 [1 1 1 1 1 1 1 ... 1] / sqrt(N)。
您的输出向量是 WV + SU/N 的乘积，其中 S 是期望的和，U 是全为 1 的列向量。换句话说，第 i 个输出变量 = (矩阵 W 的第 i 行) 和列向量 V 的点积，再加上 S/N。

每个输出变量的标准差应为 (我相信，但无法验证) 输入随机变量的标准差乘以 sqrt(N/N-1)。

正交矩阵：这是比较困难的部分，我在math.stackexchange.com上提出了一个问题，有一个简单的矩阵W可以解决问题，并且只需要三个不同的值即可算法定义，因此你实际上不需要构造矩阵。

W是v-w的Householder反射，其中v=[sqrt(N),0,0,0,...]，w=[1 1 1 1 1 ... 1]，可以通过以下方式定义：

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))

我已经生成了100,000组N=10的矩阵X中的数字，并创建了矩阵Y，其中每一行对应于其总和相除的X行（以便Y的每一行总和为1.0）。将Y的排序值绘制出来（每列单独排序），可以得到大致相同的累积分布。

alt text

一个真正的均匀分布应该从0到最大值呈直线。你会注意到它有点类似于真正的均匀分布，除了尾部有一个长尾巴。在0.2和0.5之间生成的数字过多。对于更大的N，尾部会变得更糟，因为虽然数字的平均值下降（平均值=1/N），但最大值仍然保持在1.0：由9个0.0值和1个1.0值组成的向量是有效的，并且可以通过这种方式生成，但是极其罕见。

如果您不关心这一点，请继续使用此方法。可能有方法可以生成“几乎”均匀或“几乎”高斯分布，并具有所需的总和，这比我上面描述的方法要简单得多且更高效。但我提醒您要小心并理解您选择的算法的后果。

一种修正方案，可以使事物分布在某种程度上均匀，而不会出现长尾现象，具体如下：

生成一个向量 V，其中包含从 0.0 到 1.0 均匀分布的 N 个随机数。
找到它们的和 S 和最大值 M。
如果 S < k*M（最大值太过离群），返回步骤 1。我不确定 k 的值应该是多少，也许 k = N/2？
输出向量 V*S_desired/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,:)))

alt text

- Jason S

这更接近我想要的 :) 我会试一试并让你知道更新。 - dassouki

所述需求中的数值是否需要全为正数？ - pjs

6

好的，我们假设要求是生成一个长度为N的随机向量，其在允许空间内均匀分布，重新陈述如下：

给定

- 所需长度L， - 所需总和S， - 每个标量值的允许范围[0,B]，

生成一个随机向量V，其长度为N，使得随机变量V在其允许空间内均匀分布。

我们可以通过注意到可以计算V = U * S来简化问题，其中U是具有所需总和1和允许值范围[0,b]的类似随机向量，其中b = B / S。值b必须介于1 / N和1之间。

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

最好使用正交加权矩阵W（请参见我的其他答案），其中一个向量= [1 1 1] / sqrt（3）。其中一个这样的矩阵是：

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*W=I）

如果你考虑立方体上的点[0 0 b]、[0 b b]、[0 b 0]、[b b 0]、[b 0 0]和[b 0 b]，它们形成了一个六边形，距离立方体对角线的距离都是b*sqrt(2/3)。这些点并不满足问题要求，但在接下来的步骤中非常有用。另外两个点[0 0 0]和[b b b]在立方体的对角线上。

正交加权矩阵W使我们能够生成均匀分布在{U}内的点，因为正交矩阵是坐标变换，旋转/反射而不是缩放或扭曲。

我们将生成在W的三个向量定义的坐标系中均匀分布的点。第一个分量是立方体对角线的轴。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之间），在这种情况下，我们将拒绝该值并重新开始。

换句话说：

生成独立的随机变量u和v，它们分别在-b*sqrt(2/3)和+b*sqrt(3)之间均匀分布。
计算向量U'=[1/sqrt(3) u v]
计算U=U'*W。
如果U的任何分量超出了范围[0,b]，则拒绝该值并返回步骤1。
计算V=U*S。

对于更高维度的问题（在垂直于超立方体主对角线的超平面内均匀分布的点）解决方法类似：

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

生成独立的随机变量u₁, u₂, ... u_N-1，它们都在-b*k(N)和+b*k(N)之间均匀分布。
计算向量U' = [1/N u₁, u₂, ... u_N-1]
计算U = U' * W。 (有快捷方式可以避免实际构建并乘以W。)
如果U中的任何一个分量在[0,b]范围之外，则拒绝该值并返回到步骤1。
计算V = U * S。

范围k(N)是N的一个函数，表示边长为1的超立方体顶点与其主对角线的最大距离。我不确定一般公式，但是当N=3时为sqrt(2/3)，当N=5时为sqrt(6/5)，可能有某个公式适用于所有情况。

- Jason S

从概念上讲，这个解决方案与此链接中给出的解决方案是否相同：https://dev59.com/iWsz5IYBdhLWcg3wNE1q#8068956？ - Eddified

2

我遇到了这个问题，需要使用整数。一个解决方法是使用多项式。

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

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

根据多项式分布文档的解释，您已经掷了一个公正的六面骰子二十次。 v 包含六个数字，表示骰子每一面出现的次数。自然地，v 的元素必须加起来等于二十。在这里，六是 n，而二十是 total_sum。

使用多项式分布，您也可以模拟不公正的骰子，在某些情况下非常有用。

- Ahmed Fasih

1

以下内容非常简单，可以返回统一的结果：

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:])]

这个想法很简单，如果你需要在0到20之间得到5个数字，你可以在0到20之间放置4个“限制”，然后你就得到了（0，20）区间的一个分区。你想要的随机数就是排序列表[0，random1，random2，random3，random4，20]中5个间隔的长度。

附注：哎呀！看起来这和MAK的回答是一样的想法，尽管没有使用索引编码！

- Eric O. Lebigot

0

你可以保持一个运行总数，而不必重复调用sum(my_sum)。

- a'r

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- High Performance Mark · Accepted Answer

12

为什么不直接生成正确数量的均匀分布的随机数，将它们加起来并进行缩放？

编辑：更清晰地说：你想要N个数字，它们的总和为S？那么在区间[0,1)或您的随机数生成器生成N个均匀分布的随机数。将它们相加，它们将总和为s（假设），而您想要它们总和为S，所以将每个数字乘以S/s。现在这些数字在[0，S/s）上均匀随机分布。

- High Performance Mark

5

因为总数是由个别随机数的函数决定的。假设有10个数字，期望的总和是100，你生成了10个均匀分布于0.0到1.0之间的数字。这些数字的和的期望值是5，标准差=sqrt(10/12)，所以大多数情况下，总和将在2到8之间，因此缩放因子通常将在12.5到50之间。因此，很少会出现缩放后的输出数字在50到100之间的情况：你需要一个小的基本总和，并且其中一个数字比其他数字要大得多。 - Jason S

大多数情况下，总和将在2到8之间：这是距离平均值3.3倍标准差，或者大约0.1％的时间它将超出该范围。 - Jason S

4

@马克：我感到很抱歉因为听起来很消极；你做出了一个尝试清晰简单回答的合理努力。不幸的是，它有一些统计缺陷。 - Jason S

2

@Jason S：这里的工作日结束了，我要去喝一杯帮助自己摆脱不好的情绪。建议你也这样做。 - High Performance Mark

1

这个答案对为什么缩放会破坏均匀性做了非常详细的解释：https://dev59.com/iWsz5IYBdhLWcg3wNE1q#8068956 - Engin Kurutepe

显示剩余4条评论