随机抽样给出一个精确的总和

Question

我想在1000到100000之间采样140个数字,这样140个数字的总和大约是2百万(2000000):

sample(1000:100000,140)

这样:

sum(sample(1000:100000,140)) = 2000000

任何指针如何实现这一目标？

Answer 1

存在用于生成这种随机数的算法.

最初是为MATLAB创建的,它有一个R实现:

Surrogate::RandVec

来自MATLAB脚本的引文评论:

%   This generates an n by m array x, each of whose m columns
% contains n random values lying in the interval [a,b], but
% subject to the condition that their sum be equal to s.  The
% scalar value s must accordingly satisfy n*a <= s <= n*b.  The
% distribution of values is uniform in the sense that it has the
% conditional probability distribution of a uniform distribution
% over the whole n-cube, given that the sum of the x's is s.
%
%   The scalar v, if requested, returns with the total
% n-1 dimensional volume (content) of the subset satisfying
% this condition.  Consequently if v, considered as a function
% of s and divided by sqrt(n), is integrated with respect to s
% from s = a to s = b, the result would necessarily be the
% n-dimensional volume of the whole cube, namely (b-a)^n.
%
%   This algorithm does no "rejecting" on the sets of x's it
% obtains.  It is designed to generate only those that satisfy all
% the above conditions and to do so with a uniform distribution.
% It accomplishes this by decomposing the space of all possible x
% sets (columns) into n-1 dimensional simplexes.  (Line segments,
% triangles, and tetrahedra, are one-, two-, and three-dimensional
% examples of simplexes, respectively.)  It makes use of three
% different sets of 'rand' variables, one to locate values
% uniformly within each type of simplex, another to randomly
% select representatives of each different type of simplex in
% proportion to their volume, and a third to perform random
% permutations to provide an even distribution of simplex choices
% among like types.  For example, with n equal to 3 and s set at,
% say, 40% of the way from a towards b, there will be 2 different
% types of simplex, in this case triangles, each with its own
% area, and 6 different versions of each from permutations, for
% a total of 12 triangles, and these all fit together to form a
% particular planar non-regular hexagon in 3 dimensions, with v
% returned set equal to the hexagon's area.
%
% Roger Stafford - Jan. 19, 2006

例:

test <- Surrogate::RandVec(a=1000, b=100000, s=2000000, n=140, m=1, Seed=sample(1:1000, size = 1))
sum(test$RandVecOutput)
# 2000000
hist(test$RandVecOutput)

Answer 2

这是一个命中与错过的方法.基本思想是找到总数为2000000的140个数字与将1:2000000分成140个数字相同,这需要139个切点.另外,请注意,最低1000有点烦人.只需从所有问题数据中减去它,然后将其重新添加到最后:

rand.nums <- function(a,b,n,k){
  #finds n random integers in range a:b which sum to k
  while(TRUE){
    x <- sample(1:(k - n*a),n-1, replace = TRUE) #cutpoints
    x <- sort(x)
    x <- c(x,k-n*a) - c(0,x)
    if(max(x) <= b-a) return(a+x)
  }
}

然后rand.nums(1000,100000,140,2000000)计算给定范围内的140个整数,总和为2000000.对于这些参数选择,函数几乎立即返回.对于参数的其他选择,解决方案可能是不可能的,也可能是如此严格限制,以至于偶然发现一个实际上是不可能的.因此,在使用该功能时需要谨慎.它可以通过添加maxtrials参数进行修改,NA如果超出maxtrials则返回,而无需找到解决方案.

Answer 3

以下是一些接近200万的hacky方法.希望有人会发布一个更聪明的解决方案.

在这个选项中,我们使用prob参数来更小的值,我们通过反复试验来选择指数.该方法严重偏向于在OP中指定的范围内选择较低的值.

x1 = sample(1000:100000,140, prob=(1e5:1e3)^5.5)
mean(replicate(100, sum(sample(1000:100000,140, prob=(1e5:1e3)^5.5))))

[1] 2015620

在此选项中,我们从截断的法线(在给定边界处截断)进行采样.我们最初将平均值设置为2e6/140 = 14285.71.但是,如果标准偏差大到足以在下边界附近产生大量值,则截断会使平均值偏高,因此我们添加通过反复试验选择的校正.

library(truncnorm)
x2 = rtruncnorm(140, 1e3, 1e5, mean=0.82*2e6/140, sd=1e4)
mean(replicate(1000, sum(rtruncnorm(140, 1e3, 1e5, mean=0.82*2e6/140, sd=1e4))))

[1] 2008050

如果设置较小的标准偏差,则无需进行校正.但是,通过这种方式获得的数值更少.

mean(replicate(1000, sum(rtruncnorm(140, 1e3, 1e5, mean=2e6/140, sd=0.5e4))))

[1] 2008494

在任何一种情况下,sample可以通过自动搜索来选择接近的指数或截断法线的校正,其中公差与平均总和相差200万.

以下是输出的一些典型分布:

Answer 4

这是一个尝试,试图改变上层债券.这个想法是在总和越来越高时减少上限.

sup<- 100000
tir <- vector(length = 140)
for(i in 1:140){
  print(i)
  tir[i] <- sample(1000:sup,1)
  sup <- max(1001,min(sup,abs(2000000 - sum(tir,na.rm = T))/(140-i)*2))
}
sum(tir)
[1] 2001751