math - 平均而言，此错误循环将迭代多少次？

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次循环迭代，但是现在平均只能得到8/9。我的问题是，是否有可能将这一结果推广到更准确的迭代次数上。

谢谢!

Answer 1

最终编辑(也许!)。我有95％的肯定这不是standard distributions that are appropriate之一。我把分布的内容放在了这篇文章的底部，因为我认为给出概率的代码更具可读性!下面给出了针对max的平均迭代次数图。

有趣的是，随着最大数量的增加，迭代次数逐渐减少。如果其他人可以用他们的代码确认这一点，那将很有趣。

如果要开始对此建模，我将从geometric distribution开始，然后尝试对其进行修改。本质上，我们正在看离散的，有界的分布。因此，我们有零个或多个“失败”(不满足停止条件)，然后是一个“成功”。与几何或泊松相比，这里的问题在于成功的概率发生了变化(也像泊松一样，几何分布是无限的，但从结构上讲，我认为几何是一个很好的基础)。假设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，但是将其推广到任意 min并不困难(请参阅我对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")