Reservoir Sampling не в состоянии понять вероятность

Question

Чтобы прояснить следующее вопрос:

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

Решение этой проблемы, по-видимому, является выборкой резервуаров, и это указано ниже. «Во-первых, вы хотите создать резервуар (массив) из 1000 элементов и заполнить его с помощью первых 1000 элементов в вашем потоке. Таким образом, если у вас ровно 1000 элементов, алгоритм работает. Это базовый случай.

Далее вы хотите обработать i-й элемент (начиная с i = 1,001), так что в конце обработки этого шага 1000 элементов в вашем резервуаре будут случайным образом отобраны среди элементов i, которые вы видели до сих пор. вы можете сделать это? Начните с i = 1,001. С какой вероятностью после 1001-го шага должен быть элемент 1,001 (или любой элемент в этом отношении) в наборе из 1000 элементов? Ответ прост: 1,000/1,001. "

Я не могу понять последнее предложение «Ответ прост: 1,000/1,001». Не должна быть вероятность найти 1 элемент в массиве из 1001 элементов - 1/1001, а не 1000/1001? Разве пространство образца не равно 1001, а положительное число исходов равняется 1?

Answer 1

Есть 1 001 элемент. 1000 из них находятся в образце. Один находится вне образца. Таким образом, вероятность того, что конкретный элемент является внешним, равна 1 из 1 001, а вероятность того, что она является одной из тысяч элементов внутри образца, равна 1000 из 1,001.

Answer 2

Я нахожу следующий аргумент более ясным. Пусть S - это набор первых элементов 1000; пусть e обозначает последний элемент в потоке (например, 1001-й). Существует {1001 choose 1000}=1001 возможных подмножеств размером 1000 экземпляров из набора 1001 элементов, и вы хотите, чтобы все они имели ту же вероятность хранения в структуре данных (этот инвариант должен выполняться каждый раз, когда приходит новый элемент).

Каково количество подмножеств размером-1000 из 1001 элементов, которые содержат e? Ну, так как e исправлено, у нас есть 1000 элементов, которые можно выбрать, и мы выберем 999 элементов, таким образом, есть {1000 choose 999} = 1000 таких подмножеств.

Вероятность того, что e в S должны, следовательно, быть: {1000 choose 999}/{1001 choose 1000} = 1000/1001 (то есть количество размера-1000 подмножеств, которые содержат e, разделенный на количество всех размеров-1000 подмножеств).

От {n choose k} Я обозначаю binomial coefficient.