代码之家 › 专栏 › 技术社区 › templatetypedef

这个不正确的循环平均会迭代多少次?

language-agnostic for-loop random math

9

templatetypedef · 技术社区 · 12 年前

在某些情况下,循环需要运行随机数目的迭代,其范围从 min 到 max 包含全部费用一个可行的解决方案是这样做:

int numIterations = randomInteger(min, max);
for (int i = 0; i < numIterations; i++) {
   /* ... fun and exciting things! ... */
}

许多初级程序员犯的一个常见错误是这样做:

for (int i = 0; i < randomInteger(min, max); i++) {
   /* ... fun and exciting things! ... */
}

这将重新计算每次迭代的循环上限。

我 犯罪嫌疑人 这并没有给出循环迭代次数的均匀分布,其范围从 最小值 到 最大值 ,但我不确定你到底是怎么分配的做当你做这样的事情的时候。有人知道循环迭代次数的分布是什么吗?

作为一个具体的例子:假设 最小值 =0和 最大值 = 2. 然后有以下可能性:

什么时候 i = 0 ,随机值为0。循环运行0次。
什么时候 i=0 ,随机值为非零。然后:
- 什么时候 i = 1 ,随机值为0或1。然后循环运行1次。
- 什么时候 i=1 ,随机值为2。然后循环运行2次。

第一个事件发生的概率是1/3。第二个事件的概率为2/3,在其中,第一个子类的概率为1/3,第二个则为1/3。因此,分布的平均数量为

0 × ^1. / _3. + 1 × ^2. / _3. × ^2. / _3. + 2 × ^2. / _3. × ^1. / _3.

= 0 + ^4. / ₉ + ^4. / ₉

= ^8. / ₉

注意,如果分布确实是均匀的,我们预计会得到1次循环迭代,但现在我们只得到 ^8. / ₉ 平均而言。我的问题是,是否有可能推广这个结果,以获得更精确的迭代次数值。

谢谢

4 回复 | 直到 12 年前

1

5

TooTone 12 年前

最终编辑(也许!)。我有95%的把握这不是 standard distributions that are appropriate 。我把分布放在这篇文章的底部,因为我认为给出概率的代码更可读!迭代平均次数与 max 如下所示。

enter image description here

有趣的是,迭代次数随着最大值的增加而减少。如果其他人可以用他们的代码来确认这一点,那将是一件有趣的事情。

如果我开始做这个模型,我会从 geometric distribution ,并尝试对此进行修改。本质上,我们看到的是一个离散的、有界的分布。因此,我们有零个或多个“失败”(不满足停止条件),然后是一个“成功”。与几何或泊松相比,这里的问题是成功的概率会发生变化(也像泊松一样,几何分布是无界的,但我认为在结构上几何是一个很好的基础)。假设min=0,P(X=k)的基本数学形式,0<=k<=max,其中k是循环运行的迭代次数,与几何分布一样,是k个失败项和1个成功项的乘积,对应于循环条件下的k个“假”s和1个“真”。(请注意,即使计算最后的概率也是如此,因为停止的几率是1,这显然对乘积没有影响)。

接下来,尝试在R中的代码中实现这一点,如下所示:

fx = function(k,maximum)
{
    n=maximum+1;
    failure = factorial(n-1)/factorial(n-1-k) / n^k;
    success = (k+1) / n;
    failure * success
}

这假设min=0,但推广到任意 min s并不难(见我对OP的评论)。解释代码。首先,如OP所示,所有概率都有 (min+1) 作为分母,所以我们计算分母, n 接下来,我们计算失效项的乘积。在这里 factorial(n-1)/factorial(n-1-k) 意思是,例如,对于min=2,n=3和k=2:2*1。它广义地给出(n-1) (n-2) …表示故障的总概率。成功的概率随着你进一步进入循环而增加,直到最后 k=maximum ,是1。

绘制这个分析公式可以得到与OP相同的结果,也可以得到与John Kugelman绘制的模拟相同的形状。

enter image description here

顺便说一句,实现这一点的R代码如下

plot_probability_mass_function = function(maximum)
{
    x=0:maximum;
    barplot(fx(x,max(x)), names.arg=x, main=paste("max",maximum), ylab="P(X=x)");
}

par(mfrow=c(3,1))
plot_probability_mass_function(2)
plot_probability_mass_function(10)
plot_probability_mass_function(100)

从数学上讲,如果我的数学计算正确的话,分布是:

enter image description here

简化为

enter image description here

(非常感谢 http://www.codecogs.com/latex/eqneditor.php )

后者由R函数给出

function(x,m) { factorial(m)*(x+1)/(factorial(m-x)*(m+1)^(x+1)) }

绘制平均迭代次数是这样在R中完成的

meanf = function(minimum)
{
    x = 0:minimum
    probs = f(x,minimum)
    x %*% probs
}

meanf = function(maximum)
{
    x = 0:maximum
    probs = f(x,maximum)
    x %*% probs
}

par(mfrow=c(2,1))
max_range = 1:10
plot(sapply(max_range, meanf) ~ max_range, ylab="Mean number of iterations", xlab="max")
max_range = 1:100
plot(sapply(max_range, meanf) ~ max_range, ylab="Mean number of iterations", xlab="max")

2

John Kugelman Michael Hodel 12 年前

以下是我绘制的一些具体结果 matplotlib 。X轴是数值 i 达到。Y轴是达到该值的次数。

分布显然不均匀。我不知道这是什么分发方式;我的统计学知识相当生疏。

1.最小值=10,最大值=20,迭代次数=100000

2.最小值=100,最大值=200,迭代次数=100000

3

0

Community Mohan Dere 8 年前

我相信,如果有足够数量的处决,它仍然符合 randomInteger 作用

但这可能是一个更适合问的问题 MATHEMATICS .

4

0

Jon Purdy 12 年前

我不知道它背后的数学,但我知道如何计算!在Haskell中:

import Numeric.Probability.Distribution

iterations min max = iteration 0
  where
  iteration i = do
    x <- uniform [min..max]
    if i < x
      then iteration (i + 1)
      else return i

现在 expected (iterations 0 2) 给出了~0.89的预期值。也许有必要的数学知识的人可以解释我在这里到底在做什么。因为您从0开始,所以循环将始终至少运行 min 时间。