Онлайн -поколение унифицированных образцов

Question

Источник предоставляет поток элементов $ x_1, x_2, dots $. На каждом шаге $ n $ мы хотим сэкономить случайную образец $ s_n subteq {(x_i, i) | 1 le i le n } $ size $ k $, то есть $ s_n $ должны быть равномерно выбраны Образец от всех $ tbinom {n} {k} $ возможные образцы, состоящие из видных элементов. Таким образом, на каждом шаге $ n g k $ мы должны решить, добавить ли следующий пункт в $ s $ или нет. Если это так, мы также должны решить, какой из текущих предметов удалить из $ s $.

Укажите алгоритм для проблемы. Докажите его правильность.

Answer 1

Из -за сомнительного характера вопроса я даю только подсказки.

Вы пробовали очевидное? С вероятностью $ frac {1} {n} $, добавьте новый элемент в образец. Если это добавлено, выберите один из элементов, уже в выборке, в случайном порядке и отбросьте его. Звучит о честном, не так ли?

Для доказательства вам придется продолжить индуктивно. На шаге вы предполагаете, что $ s_ {n-1} $ действительно является единой выборкой. Исходя из этого и способа выбора, следует ли включать $ x_n $, а какой элемент должен бросить, вы должны получить этот $ s_n $, также является единым образцом.

Попробуйте, если вы можете доказать правильную идею выше. Если это не так, выясните, где проблема, и исправьте ее. Видеть этот ответ к аналогичному вопросу для подробного применения этой техники.

Answer 2

Лучший алгоритм для вашей проблемы - алгоритм отбора проб водохранилища. Читать это