栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

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

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

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

好吧,假设要求是生成长度为N的随机向量,该向量 均匀地分布 在允许的空间内,我们将解决该问题,具体如下:

给定

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

生成长度为N的随机向量V,以使随机变量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}的形状像六边形。

(TBD:图片。我现在无法生成一个图像,我需要访问MATLAB或另一个可以进行3D绘图的程序。我无法安装Octave。)

最好使用一个向量= [1 1 1] / sqrt(3)的正交加权矩阵W(请参阅我的其他答案)。一种这样的矩阵是

octave-3.2.3:1> A=1/sqrt(3)   A =  0.57735octave-3.2.3:2> K=1/sqrt(3)/(sqrt(3)-1)   K =  0.78868octave-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 0 b],[0 bb],[0 b 0],[bb 0],[b 0 0]和[b 0 b]的点,它们形成一个六边形并且都是a b *sqrt(2/3)与立方体对角线的距离。这些不能满足所讨论的问题,但是在一分钟内很有用。另外两个点[0 0 0]和[bbb]在立方体的对角线上。

正交加权矩阵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)uv]。然后,我们计算U =
U’*W。某些结果点将超出允许范围(U的每个分量必须在0到b之间),在这种情况下,我们将拒绝并重新开始。

换一种说法:

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

对于更高的尺寸(在与超立方体的主对角线垂直的超平面的一部分内均匀分布的点),解决方案相似:

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

  1. 生成独立的随机变量u 1,u 2,…,u N-1,每个变量均均匀地分布在-b * k(N)和+ b * k(N)之间。
  2. 计算向量U’= [1 / N u 1,u 2,… u N-1 ]
  3. 计算U = U’*W。(实际上是构造和乘以W的捷径。)
  4. 如果U的任何一个分量不在[0,b]范围内,则拒绝该值并返回步骤1。
  5. 计算V = U *S。

范围k(N)是N的函数,N表示侧面1的超立方体的顶点与其主对角线之间的最大距离。我不确定通用公式,但是对于N = 3是sqrt(2/3),对于N =
5是sqrt(6/5),可能在某个地方有一个公式。



转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/617697.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号