Eratosthenes的概率筛

Question

考虑以下算法.

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]

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

Answer 1

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

设X _K,R表示指示变量,以值1当且仅当X[k] == true由其中所述可变迭代结束i了值r.

为了获得更少的符号,并且因为它使代码更直观,我们只会写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如何影响该概率.

当然,如果你问数学,你可能会得到一个更好的答案 - 这个答案非常简单,我确信有一种方法可以操纵它来获得一个直接的公式.