резервуара проблема отбора проб

Question

This MSDN article доказывает правильность Reservoir Sampling algorithm следующим образом:

---

1. Базовый случай тривиален. Для случая k + 1 вероятность a задана элемент i с положением < = k находится в R is s/k.

2. . Вероятность i заменяется на вероятность выбора k + 1-го элемента, умноженного на i, который выбирается для замены: s/(k + 1) * 1/s = 1/(k + 1) , и вероятность того, что i не заменена, равна k/k + 1.

3. Таким образом, любая вероятность существования данного элемента после k + 1 раундов: (выбрана в k шагах и не удалена по k шагам) = s/k * k/(k + 1), которая равна s/(к + 1).

4. Итак, когда k + 1 = n, любой элемент присутствует с вероятностью s/n.

---

о шаге 3:

• Каковы k+1 rounds упоминается?

• Что такое chosen in k steps, and not removed in k steps?

• Почему мы вычисляем эту вероятность только для элементов, которые уже были в R после первых шагов s?

Answer 1

Мы отбираем элементы s из потока элементов k (где k очень велико, поэтому мы обрабатываем элемент потока по позиции).

Обработка каждого элемента из потока называется «круглым».

Во время раунда мы, возможно, заменим один из элементов, уже представленных новым элементом.

«Выбрано в k шагах» означает, что во время раунда, где элемент появился в потоке, мы решили заменить его другим (t.i. мы его не игнорировали). «Не удалено в k шагах» означает, что с этого момента мы не решили заменить этот элемент новым элементом из потока.

Answer 2

• «к + 1 раундов» означает «после того, как (к + 1) -го элемента из входной последовательности была рассмотрена»
• S/K есть вероятность того, что данный элемент будет находиться в резервуаре после k шагов (по индукции), k/(k + 1) - вероятность того, что элемент не будет заменен на (k + 1) -ом шаге
• Мы хотим, чтобы каждый элемент ввода оставался в резервуаре с той же вероятностью. поэтому в наших расчетах нас интересуют только предметы, которые остаются в резервуаре на каждом шаге.

Answer 3

Вы знакомы с proof by induction?k - это всего лишь промежуточный шаг алгоритма, доказывающий, что инвариант истинен во всем, в этом случае вероятность того, что значение k-th будет иметь значение s/k для всех k.