平均而言,这个不正确的循环会重复多少次？

Question

在某些情况下,一个循环需要为迭代的随机数范围从运行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! ... */
}

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

我怀疑,这并没有给次循环将遍历从范围数量的均匀分布min到max,但我不知道你到底是什么分配做,当你做这样的事情搞定了.有谁知道循环迭代次数的分布是什么？

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

• 当i = 0,随机值为0.循环运行0次.
• 当i = 0,随机值非零.然后:
  • 当i = 1,随机值为0或1.然后循环运行1次.
  • 当i = 1,随机值为2.然后循环运行2次.

第一次事件的概率是1/3.第二个事件的概率为2/3,在其中,第一个子案例的概率为2/3,第二个事件的概率为1/3.因此,平均分布数是

0× ¹/₃ + 1× ²/₃ × ²/₃ + 2× ²/₃ × ¹/₃

= 0 + ⁴/₉ + ⁴/₉

= ⁸/₉

请注意,如果分配确实是一致的,我们会期望获得1次循环迭代,但现在我们只得到⁸/₉的平均水平.我的问题是,是否可以推广这个结果以获得更精确的迭代次数值.

谢谢!

Answer 1

最后编辑(也许!).我敢肯定这不是适合的标准发行版之一.我已经把这个发布的内容放在了这篇文章的底部,因为我认为提供概率的代码更具可读性!max下面给出了平均迭代次数的图.

有趣的是,当你增加最大值时,迭代次数会减少.如果其他人可以用他们的代码确认这一点会很有趣.

如果我开始对此进行建模,我将从几何分布开始,并尝试修改它.基本上我们正在寻找一个离散的,有界的分布.所以我们有零个或多个"失败"(不符合停止条件),然后是一个"成功".与几何或泊松相比,这里的捕获是成功的概率变化(同样,泊松,几何分布是无界的,但我认为结构上几何是一个很好的基础).假设min = 0,P(X = k)的基本数学形式,0 <= k <= max,其中k是循环运行的迭代次数,与几何分布一样,是k个失败项的乘积和1个成功项,对应于循环条件下的k"假"和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,但推广到任意mins并不困难(参见我对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绘制的模拟相同的形状.

顺便说一句,执行此操作的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)

在数学上,如果我的数学是正确的,则分布是:

这简化为

(非常感谢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")