Demonstrating that probability for every possible result is uniform at the end of an algorithm

Question

I have memory of $k$ elements that you can imagine being represented by an array. One by one, the array receives a value corresponding to the time index, for example at $t=1$ the value will be $1$. At some point ($t=k+1$) the array will be full and we must choose a value inside the array to replace with the new one. The objective is to find an algorithm that outputs a uniform subset of $k$ elements. For example, with $k=2$ and $t=3$ it will output with uniform probability one of the following: $\{1,2\}$, $\{1,3\}$ or $\{2,3\}$. One possible algorithm is the following:

1. create array of $k$ elements
2. FOR $t=1,.\ldots,T$:
3. if array is not full insert an empty space
4. receive an input
5. discard the input with probability $1 - k/t$
6. else insert the input at a uniform location
7. END FOR
8. return array

It's easy to implement such a program and convince yourself that this is indeed a solution to the problem but how do I demonstrate it? Essentially I need to demonstrate that each subset has probability $1/\binom tk$ to be the result at the end (that's because $\binom tk$ is the number of possible subsets of $k$ elements at time $t$).

Answer 1

The proof is by induction. The base case $t = k$ is clear. Suppose that the claim is true at some time $t$. We will prove it for time $t+1$.

Let the first $t+1$ elements be $x_1,\ldots,x_{t+1}$. By the induction hypothesis, at time $t$ each of the $\binom{t}{k}$ possible $k$-subsets of $x_1,\ldots,x_t$ is found in the array with equal probability. The probability that at step $t+1$ the array remains the same is $1-k/(t+1)$, hence each of the $k$-subsets of $x_1,\ldots,x_t$ appears at time $t+1$ with probability $$ \frac{t+1-k}{t+1} \frac{1}{\binom{t}{k}} = \frac{1}{\binom{t+1}{k}}. $$ Now consider some $k$-subset $S$ of $x_1,\ldots,x_{t+1}$ that contains $x_{t+1}$. For this set to be appear at time $t+1$, the following two events need to happen: at time $t$, the array consisted of $S \setminus \{x_{t+1}\}$ together with one of the $t-(k-1)$ remaining elements; and at time $t+1$, this element was replaced by $x_{t+1}$. In total, the probability is $$ \frac{k}{t+1} \cdot \frac{1}{k} \cdot \frac{t-k+1}{\binom{t}{k}} = \frac{1}{\binom{t+1}{k}}. $$