Reservoir sampling: один равномерный элемент из потока
Опишите алгоритм reservoir sampling для одного элемента из потока и объясните, почему каждый увиденный элемент выбирается с одинаковой вероятностью.
Ответить самому
Сначала сформулируйте ответ как на собеседовании, затем откройте разбор и оцените себя.
Короткий ответ
Храним счетчик n и текущий sample. На n-м элементе заменяем sample новым элементом с вероятностью 1/n. После этого каждый из n увиденных элементов хранится с вероятностью 1/n.
Полный разбор
Это reservoir sampling с reservoir size = 1. Храним два состояния: сколько элементов уже увидели и текущий выбранный элемент. Первый элемент сохраняем сразу. Когда приходит n-й элемент, заменяем сохраненный элемент с вероятностью 1/n, иначе оставляем старый.
Доказательство идет по индукции. Новый n-й элемент выбран с вероятностью 1/n. Любой старый элемент после n - 1 шагов хранился с вероятностью 1/(n - 1) и переживает n-й шаг с вероятностью 1 - 1/n = (n - 1)/n. Произведение равно 1/n.
Для m samples без возвращения используется reservoir размера m: сначала заполняем первые m элементов, затем для n-го элемента выбираем случайный индекс из [1, n] и заменяем элемент reservoir, если индекс попал внутрь reservoir.
Теория
Reservoir sampling дает равномерную выборку из потока неизвестной или очень большой длины.
Типичные ошибки
- Хранить весь поток и выбирать элемент в конце.
- Использовать фиксированную вероятность замены.
- Доказать вероятность для нового элемента, но забыть проверить старые элементы.
Как отвечать на собеседовании
- Сформулируй инвариант после n увиденных элементов.
- Дай короткое индукционное доказательство.