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

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

  •  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. / 9 + 4. / 9

    = 8. / 9

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

    谢谢

    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
  •  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 时间。

    推荐文章