Демонстрация того, что вероятность для каждого возможного результата одинакова в конце алгоритма

Question

У меня есть память о $k$ элементы, которые вы можете себе представить, представлены массивом.Одно за другим массив получает значение, соответствующее индексу времени, например, в $t=1$ значение будет равно $1$.В какой - то момент ($t=k+1$) массив будет заполнен, и мы должны выбрать значение внутри массива для замены на новое.Цель состоит в том, чтобы найти алгоритм, который выводит однородное подмножество $k$ элементы.Например, с помощью $k=2$ и $t=3$ он с одинаковой вероятностью выдаст одно из следующих: $\{1,2\}$, $\{1,3\}$ или $\{2,3\}$.Одним из возможных алгоритмов является следующий:

1. создать массив из $k$ элементы
2. ДЛЯ $t=1,.\ldots,T$:
3. если массив не заполнен, вставьте пустое пространство
4. получение входных данных
5. отбрасывайте входные данные с вероятностью $1 тыс./т$
6. в противном случае вставьте входные данные в единое место
7. КОНЕЦ ДЛЯ
8. возвращаемый массив

Легко внедрить такую программу и убедить себя, что это действительно решение проблемы, но как мне это продемонстрировать?По сути, мне нужно продемонстрировать, что каждое подмножество имеет вероятность $1/\binom tk$ быть результатом в конце (это потому, что $\binom tk$ является числом возможных подмножеств $k$ элементы во времени $т$).

Answer 1

Доказательство производится методом индукции.Базовый вариант $t = k$ это ясно.Предположим, что утверждение верно в какой -то момент $т$.Мы докажем это на время $t+1$.

Пусть первый $t+1$ элементы должны быть $x_1,\ldots,x_{t+1}$.Согласно гипотезе индукции, во время $т$ каждый из $\бином{t}{k}$ возможный $k$-подмножества из $x_1,\ldots,x_t$ находится в массиве с равной вероятностью.Вероятность того, что на шаге $t+1$ массив остается тем же, что и раньше . $1-k/(t+1)$, следовательно , каждый из $k$-подмножества из $x_1,\ldots,x_t$ появляется во время $t+1$ с вероятностью $$ \frac{t+1-k}{t+1} \frac{1}{\binom{t}{k}} = \frac{1}{\binom{t+1}{k}}.$$ Теперь рассмотрим некоторые $k$-подмножество $S$ из $x_1,\ldots,x_{t+1}$ который содержит $x_{t+1}$.Чтобы этот набор появлялся вовремя $t+1$, должны произойти следующие два события:во время $т$, массив состоял из $S \setminus \{x_{t+1}\}$ вместе с одним из $t-(k-1)$ оставшиеся элементы;и вовремя $t+1$, этот элемент был заменен на $x_{t+1}$.В общей сложности вероятность равна $$ \frac{k}{t+1} \cdot \frac{1}{k} \cdot \frac{t-k+1}{\binom{t}{k}} = \frac{1}{\ binom{t+1}{k}}.$$