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 /私

（=は、理解しやすくするために=の代わりに使用されます。=は、2つの別個の意味を持ち、混乱しているように見えるためです）。

この同等性は、の終わりにfalseであったか、その時点であったために、反復の最後にX[k]あったという事実によって成り立ちますが、その最後の反復では、ループに入り、次のように変更しました。 1/iの確率。イベントは相互に排他的であるため、交差点はありません。falseii-1trueX[k-1]trueX[k]

再帰の基本は、P（X k、1〜1）= 1およびP（X 2、i〜1 ）=1であるという事実です。

X[k] == true最後に、P（ ）= P（X k、k-1〜1 ）であることに注意してください。

これはかなり簡単にプログラムできます。これは、メモ化を使用する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 に答える