3

考虑以下算法。

function Rand():
    return a uniformly random real between 0.0 and 1.0

function Sieve(n):

    assert(n >= 2)

    for i = 2 to n
        X[i] = true

    for i = 2 to n
        if (X[i])
            for j = i+1 to n
                if (Rand() < 1/i)
                    X[j] = false

    return X[n]

trueSieve(k)作为 k 的函数返回的概率是多少？

4

1 回答 1

5

让我们递归地定义一系列随机变量：

令 X k,r表示指示变量，在变量取值的迭代结束时取值1iff 。X[k] == trueir

为了减少符号并且因为它对代码更直观，我们只写 X k,i这是有效的，尽管在定义中会令人困惑，因为当第一个引用变量时i取值会令人困惑i循环和后者到变量的值。

现在我们注意到：

P(X k,i ~ 0) = P(X k,i-1 ~ 0) + P(X k,i-1 ~ 1) * P(X k-1,i-1 ~ 1) * 1/一世

（~ 用于代替 = 只是为了使其易于理解，因为 = 否则将具有两个不同的含义并且看起来令人困惑）。

这种等式成立是因为要么X[k]在迭代false结束时i要么因为它在 结束时为假i-1，要么true在那个点，但在最后一次迭代X[k-1]中true，所以我们进入循环并更改X[k]为1/i 的概率。事件是互斥的，所以没有交集。

递归的基础很简单，即 P(X k,1 ~ 1) = 1 和 P(X 2,i ~ 1) = 1。

最后，我们简单地注意到 P( · X[k] == true) = P(X k,k-1 ~ 1)。

这可以很容易地编程。这是一个使用 memoisation 的 javascript 实现（如果使用嵌套索引比字典索引的字符串连接更好，您可以进行基准测试，您还可以重新设计计算以保持相同的运行时复杂性，但不会通过构建自下而上和不是自上而下）。自然地，该实现将具有运行时复杂性，O(k^2)因此对于任意大的数字是不切实际的：

function P(k) {
   if (k<2 || k!==Math.round(k)) return -1;
   var _ = {};
   function _P(n,i) {
      if(n===2) return 1;
      if(i===1) return 1;
      var $ = n+'_'+i;
      if($ in _) return _[$];
      return _[$] =  1-(1-_P(n,i-1) + _P(n,i-1)*_P(n-1,i-1)*1/i);
   }
   return _P(k,k-1);
}

P(1000); // 0.12274162882390949

更有趣的是 1/i 概率如何改变事物。即概率是否收敛到 0 或某个其他值，如果是，如何改变 1/i 对其产生影响。

当然，如果您在 mathSE 上提问，您可能会得到更好的答案——这个答案非常简单，我相信有一种方法可以操纵它来获得直接公式。

于 2012-07-15T15:45:55.017 回答