Информатика · объяснение и практика

Резервуарная выборка: как один слот остаётся равномерным

Резервуарная выборка одного элемента: правило замены, вероятность сохранения и разница между позицией и значением.

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Методы алгоритмов: углубление · Учебная карта

В маршруте Случайность, численные оценки и целостность · 10 тем

Главная мысль

Чтобы равномерно выбрать одну позицию из потока неизвестной длины, сохраняют первый элемент, а элемент с номером i принимает его место с вероятностью 1/i. После n шагов каждая из n позиций находится в слоте с вероятностью 1/n.

Один слот и неизвестный конец

В поток поступают карточки К, Л, М, Н. Мы не знаем заранее, после какой карточки поток закончится, и не можем хранить весь список. Первую карточку кладём в единственный слот. При второй заменяем содержимое с вероятностью 1/2, при третьей — 1/3, при четвёртой — 1/4.

Случайное решение на каждом шаге должно быть независимым и равномерным по указанному диапазону. Удобно выбирать целое от 1 до текущего номера включительно и заменять при единице. Если всегда заменять с вероятностью 1/2, поздние элементы получат преимущество: это уже другой алгоритм, несмотря на такой же маленький объём памяти.

Почему ранний элемент не обделён

Карточка Л попадает в слот на втором шаге с вероятностью 1/2. Чтобы дожить до конца четырёхэлементного потока, она должна пережить третий и четвёртый шаги. Вероятность равна (1/2)·(2/3)·(3/4)=1/4. Для К начальная вероятность равна единице, затем нужно пережить все три замены: результат тоже 1/4.

Последняя Н выбирается с вероятностью 1/4 и после этого уже не рискует быть вытесненной. Для произвольного старого элемента множители сокращаются аналогично. Это доказательство распределения, а не обещание, что в четырёх отдельных запусках каждая буква обязательно выпадет по одному разу.

Пример

Для М: вероятность попасть 1/3, пережить Н — 3/4; итог 1/4.

Более поздний приход даёт меньший шанс входа, но меньше последующих рисков. Эти факторы точно компенсируются.

Повторяющиеся значения и проверка реализации

Если поток содержит К, К, Л, равномерно выбираются три позиции. Поэтому значение К имеет вероятность 2/3, а Л — 1/3. Это не ошибка: алгоритм не обещал равномерность среди различных названий. Для выбора разных значений потребовалось бы другое условие и учёт повторов.

Тестировать удобно на коротких потоках полным перебором возможных случайных решений с их вероятностями. Одна удачная трасса проверяет только переходы. Для воспроизведения сбоя можно сохранять состояние генератора, но обычный псевдослучайный генератор учебной программы нельзя автоматически считать пригодным для защищённого розыгрыша или криптографических ключей.

От чтения к действию

А теперь — вы

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

Частые вопросы

Нужно сначала узнать длину потока?

Нет. Для одного слота достаточно счётчика увиденных позиций и текущего выбранного элемента.

Почему одинаковые значения выпадают чаще?

Каждое их вхождение — отдельная позиция. Несколько позиций с одним значением суммируют свои вероятности.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться