0

私は Reservoir Sampling アルゴリズムに精通しており、合計サイズNが与えられたらどうなるか考えています。この状況下で私たちはどのような利益を得ることができますか？その結果、アルゴリズムは次のようになります。

Let n be the total size of data
Let k be the total size of sample
for each element from data
    if random(0,1) <= k/n
        put this element into sample
        -- k
    -- n
done

一見正しいように見えますが、証明するのは難しいと感じました。このアルゴリズムを正式な方法で証明するのを手伝ってくれる人はいますか?

4

2 に答える 2

1

これがDave の fix の正しさの証明です。一般性を失うことなく、ストリームが であると仮定します1..n。ループを反復した後、サンプルがの一様なランダムな組み合わせのm in {0..n}との交点として分布することを帰納的に証明します。1..mk1..n

基本ケースm = 0は自明です: サンプルと交差の両方が常に空です。特定の の帰納的仮説が与えられたmので、 についてそれを証明しm+1ます。を反復S後の集合を表す確率変数とし、反復後の集合を表す確率変数を とします。交差点を設定しましょう。すべての-combinationについて、次のように書きますmS'm+1&kT

Pr(S' = T & {1..m+1})
    = Pr(S = T & {1..m}) Pr(S' = T & {1..m+1} | S = T & {1..m}),

S' = T & {1..m+1}であることを意味するのでS = T & {1..m}。帰納的仮説といくつかのカウントにより、

(n choose k) Pr(S = T & {1..m})
    = ((n - m) choose (k - |T & {1..m}|)).

2 つの方程式を組み合わせると、次のようになります。

(n choose k) Pr(S' = T & {1..m+1})
    = ((n - m) choose (k - |T & {1..m}|)) Pr(S' = T & {1..m+1} | S = T & {1..m}).

Dave のプログラムを調べてみると、

Pr(m+1 in S' | S) = (k - |S|) / (n - m).

現在、2つのケースがあります。最初のケースはm+1 in T.

Pr(S' = T & {1..m+1} | S = T & {1..m})
    = Pr(m+1 in S' | S = T & {1..m})
    = (k - |T & {1..m}|) / (n - m)
(n choose k) Pr(S' = T & {1..m+1})
    = ((n - m) choose (k - |T & {1..m}|)) (k - |T & {1..m}|) / (n - m)
    = (n - m - 1) choose (k - |T & {1..m}| - 1)
    = (n - (m+1)) choose (k - |T & {1..m+1}|).

2番目のケースはm+1 not in T.

Pr(S' = T & {1..m+1} | S = T & {1..m})
    = Pr(m+1 not in S' | S = T & {1..m})
    = (n - m - (k - |T & {1..m}|)) / (n - m)
(n choose k) Pr(S' = T & {1..m+1})
    = ((n - m) choose (k - |T & {1..m}|)) (n - m - (k - |T & {1..m}|)) / (n - m)
    = (n - m - 1) choose (k - |T & {1..m}|)
    = (n - (m+1)) choose (k - |T & {1..m+1}|).

Pr(S' = T & {1..m+1})どちらの場合も、が正しい値であることを証明します。

于 2014-10-07T14:56:20.077 に答える
0

正確に K 個のサンプルが必要な場合: K を目的のサンプル、k をこれまでに取得したサンプルとします。N をデータの合計サイズとし、n をこれまでにサンプリングされたセットとします。次に、random(0,1) <= (Kk)/(Nn) かどうかを確認します。

また、ストリームの (N/K) 番目の要素ごとに取得するか、ストリームを K 個のサブストリームに分割して、それぞれからランダムに 1 つの要素を取得することもできます。

于 2014-10-07T11:58:03.627 に答える