проблема отбора проб коллектора

Question

У меня возникли проблемы с пониманием вероятностей, связанных с выборкой коллектора. Ниже приведен пример кода, который я видел используемый практически везде: (?)

1/* 
    2 S has items to sample, R will contain the result, K number of items to select 
    3*/ 
    4ReservoirSample(S[1..n], R[1..k]) 
    5 // fill the reservoir array 
    6 for i = 1 to k 
    7  R[i] := S[i] 
    8 
    9 // replace elements with gradually decreasing probability 
    10 for i = k+1 to n 
    11 j := random(1, i) // important: inclusive range 
    12 if j <= k 
    13  R[j] := S[i] 

Является ли мое понимание прав: Пусть мы имеем к = 3 и вход = [100, 200, 300, 400, 500] и i в настоящее время составляет 500 индексов. Вероятность 500 заменяет 300 в резервуаре (который имеет 3 размера) = вероятность выбора 300 в резервуаре * вероятность выбора 500, которая возможна только в том случае, если индекс, возвращаемый случайной функцией, меньше или равен 3 из 5 вариантов = 1/3 * 3/5 = 1/5

Answer 1

Ваше понимание не кажется правильным. Вероятность выбора 500 нигде не связана с выбором 300.

Вы должны проверить gfg link for the same. «Как это работает?» раздел, в котором говорится следующее:

Случая 1: Для последних пк элементов потока, т.е. для потока [я], где к < = я < п Для каждого такого потока элемента потока [я], мы выбираем случайный индекс от 0 до i, и если выбранный индекс является одним из первых k индексов, мы заменяем элемент на выбранном индексе на поток [i]

Для упрощения доказательства рассмотрим последний элемент. Вероятность того, что последний элемент находится в конечном резервуаре = вероятность того, что один из первых k индексов будет выбран для последнего элемента = k/n (вероятность выбора одного из k элементов из списка размера n)

Рассмотрим теперь второй последний пункт. Вероятность того, что второй последний элемент находится в конечном резервуаре [] = [Вероятность того, что один из первых k индексов выбран в итерации для потока [n-2]] X [Вероятность того, что индекс, выбранный в итерации для потока [n-1 ] не совпадает с индексом, выбранным для потока [n-2]] = [k/(n-1)] * [(n-1)/n] = k/n.

Аналогичным образом, мы можем рассматривать другие элементы для всех элементов потока из потока [n-1] в поток [k] и обобщать доказательство.

Случай 2: Для первых к элементов потока, т.е. для потока [I], где 0 < = я < к первые к элементы изначально копируются в резервуар [] и могут быть удалены позднее в итераций для потока [к ] для потока [n]. Вероятность того, что элемент из потока [0..k-1] находится в конечном массиве = Вероятность того, что элемент не выбран, когда поток элементов [k], поток [k + 1], .... поток [n-1] считаются = [k/(k + 1)] x [(k + 1)/(k + 2)] x [(k + 2)/(k + 3)] x ... x [ (п-1)/N] = K/N