проблема отбора проб пласта - PullRequest
Новая
       4

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

1 голос
/ 11 апреля 2010

Эта статья MSDN подтверждает правильность Алгоритм отбора проб резервуара следующим образом:

  1. Базовый случай тривиален. Для К + 1 случай, вероятность данного элемент i с положением <= k находится в R это з / к. </p>

  2. Вероятность замены i - это вероятность выбора k + 1-го элемента, умноженная на выбор i для замены: s / (k + 1) * 1 / s = 1 / (k + 1) ), и вероятность того, что я не заменен, равна 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 шагов?

Ответы [ 3 ]

1 голос
/ 12 апреля 2010

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

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

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

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

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

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

...