2

只是想知道这是什么类型的算法，
或者是否有更简单/更有效的方法来解决这个问题：

假设我们有一定的概率密度，比如说

prob[] = {.1, .15, .25, .05, .45}

第 1 组 - 10%
第 2 组 - 15%
第 3 组 - 25%
第 4 组 - 5%
第 5 组 - 45%

和一个随机数 (0,1)，
ran = .853234

插入 5 个组之一

if (ran <=prob[0]) selection = 1;  
else if (ran <= prob[0]+prob[1]) selection = 2;  
...
else if (ran <= prob[0]+prob[1]+...+prob[4]) selection = 5;

我不太精通随机数生成

4

4 回答 4

2

您在这里所做的基本上是反转累积分布函数。设F为具有给定分布的随机变量的 CDF X，则定义为F(x) == P[X <= x]。

这里非常有用的是，如果你生成一个U介于 0 和 1 之间的均匀随机变量，那么

P[F^-1(U) <= x] == P[U <= F(x)] == F(x) == P[X <= x]

这意味着F^-1(U)它将具有与X!

当然，这只有在您可以反转 CDF 时才有可能，但在您的情况下F是分段函数（如楼梯），并且您的算法确定，对于给定的统一值，该值在哪一步得到满足。因此，您的算法是完全正确的。

但是，如果您要生成大量随机数，则可以改进它：首先生成 CDF 表，在您的情况下是

CDF[] = {.1, .25, .5, .55, 1.}

然后对于每个生成的介于 0 和 1 之间的统一数，只需对 CDF 表进行二分法即可检索相应的索引。

于 2011-11-03T10:41:05.333 回答
1

你的算法是正确的。但是，在您的示例中，概率加起来不等于 1。

于 2011-10-31T15:41:37.263 回答
0

该代码将起作用，除非您的概率加起来不等于 100%（因此所有 if 语句都可能不匹配）。

通过使用累积概率分布可以稍微简化该方法：

cumprob[5] = {.1, .2, .45, .50, 1.0};

这也可以让你用lsearch代替if-elif 链。

于 2011-10-31T15:41:57.647 回答
0

您的算法将随机浮点数用于离散分布，这不是实现这一点的最佳方式。您的实现可能会提供与给定分布几乎无法区分的分布，但它在科学上并不正确。

相反，找到给定概率的最小公分母（在您的示例中为 5%）并使用 [0,19] 中的随机整数来选择您的组。例子：

switch(random(19)) {
case 0:
case 1:
  selection = 1;
  break;
case 2:
case 3:
case 4:
  selection = 2;
  break;
case 5:
case 6:
case 7:
case 8:
case 9:
  selection = 3;
  break;
case 10:
  selection = 4;
  break;
case 11:
case 12:
case 13:
case 14:
case 15:
case 16:
case 17:
case 18:
case 19:
  selection = 4;
  break;
}
于 2011-11-03T08:20:44.037 回答