отбор проб из коллектора понимание вероятности

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

    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]

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


random algorithm probability probability-theory reservoir-sampling
person noman pouigt    schedule 10.02.2016    source источник
comment
en.wikipedia.org/wiki/Reservoir_sampling   -  person Karoly Horvath    schedule 11.02.2016
comment
@KarolyHorvath: ок? Я прошел по этой ссылке, и этот код взят оттуда, но я просто хотел проверить свое понимание этого материала.   -  person noman pouigt    schedule 11.02.2016

Ответы (1)


arrow_upward
-1
arrow_downward

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

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

Случай 1: для последних nk элементов потока, т. Е. Для потока [i], где k ‹= i‹ n Для каждого такого элемента потока stream [i] мы выбираем случайный индекс от 0 до i, и если выбранный индекс является одним из первые k индексов, мы заменяем элемент по выбранному индексу на stream [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: Для первых k элементов потока, т. Е. Для потока [i], где 0 ‹= i‹ k Первые k элементов изначально копируются в резервуар [] и могут быть удалены позже в итерациях для потока [k] в поток [n ]. Вероятность того, что элемент из потока [0..k-1] находится в конечном массиве = Вероятность того, что элемент не выбран, когда элементы stream [k], stream [k + 1],…. поток [n-1] считается = [k / (k + 1)] x [(k + 1) / (k + 2)] x [(k + 2) / (k + 3)] x… x [ (n-1) / n] = k / n

person Swati Garg    schedule 03.09.2017