Доказательство взятия проб пластового резервуара

Question

Я хорошо знаком с алгоритмом выборки коллектора, и я думаю, что если общий размер 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 

Это выглядит правильно, на первый взгляд, но я нашел, что это трудно доказать. Кто-нибудь может помочь мне доказать этот алгоритм формально?

Answer 1

Вот доказательство правильности для Dave's fix. Предположим без ограничения общности, что поток равен 1..n. Мы индуктивно доказываем, что после m in {0..n} итераций через петлю образец распределяется как пересечение с 1..m равномерной случайной k-комбинацией 1..n.

Базовый корпус, m = 0, тривиальный: оба образца и пересечение всегда пусты. Учитывая индуктивную гипотезу для конкретного m, мы теперь докажем ее для m+1. Пусть S - случайная величина, представляющая набор после m итераций, и пусть S' - случайная величина, представляющая набор после m+1 итераций. Пусть & будет установлено пересечение. Для всех k -combinations T, мы пишем

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}|)). 

Объединяя два уравнения, мы получим

(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}). 

Проверяя программу Дэйва,

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

В настоящее время существует два случая. Первый случай - 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}|). 

Второй случай: 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}) имеет правильное значение.

Answer 2

Если вы хотите точно указать K образцов: пусть K - желаемый образец и k - полученный образец. Пусть N - общий размер данных, а n - набор, отобранный до сих пор. Затем проверьте, является ли случайным (0,1) < = (K-k)/(N-n).

Вы также можете взять каждый (N/K) '-й элемент потока или разделить поток на K-подпотоки и взять один элемент наугад из каждого из них.