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$).


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}}. $$

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.