# Probability that two specific elements are in uniformly random sample

Consider the sampling algorithm as described here section 2.2 specifically Algorithm 2.4.

Essentially we are given a stream of $$N$$ elements and wish to maintain a uniformly random sample, $$S$$, of size $$k$$. Initially we put $$k$$ elements into $$S$$ and then for each iteration, $$i \in [k+1, N]$$ we choose a random number $$x \in [1,i]$$ and if $$x \leq k$$ we replace the $$x$$'th element from $$S$$ with the element seen at iteration $$i$$.

I see answers online e.g. here that after iteration $$N$$ each element from the stream has probability $$k/N$$ to be in the sample $$S$$. However what is the probability that two elements $$x_l$$ and $$x_j$$ where $$l \neq j$$ are both in the sample after iteration $$N$$? As i understand it the event that $$x_l$$ is sampled is not independent from the event that $$x_j$$ is sampled since we would have fewer slots to choose from when including $$x_j$$ assuming it occurs later than $$x_l$$ in the stream.

## 2 Answers

Let us study the event that $$x_a$$ and $$x_b$$ are both in the reservoir at the end of the algorithm, where $$k < a < b$$.

In order for this to occur four things must happen:

1. On the $$a$$th iteration the random number must be $$\leq k$$.
2. Between the $$a$$th and $$b$$th iteration $$x_a$$ must not be replaced.
3. On the $$b$$th iteration the random number generator must be $$\leq k$$ but also not equal the location of $$x_a$$. WLOG we say that the random number must be $$\leq k-1$$.
4. For the remaining iterations neither $$x_a$$ or $$x_b$$ must be replaced.

This gives us the equation

$$p = \frac{k}{a} \cdot \prod_{i=a+1}^{b-1}(1 - 1/i)\cdot \frac{k-1}{b}\cdot \prod_{i=b+1}^n(1-2/i).$$

Left as an exercise to the reader, this solves to $$p = \frac{k}{a} \cdot \frac{a}{b-1}\cdot \frac{k-1}{b}\cdot \frac{(b-1)b}{(n-1)n},$$ $$p = \frac{(k-1)k}{(n-1)n}.$$

Thus the probability that $$x_a, x_b$$ are both in the sample is independent of $$a, b$$ when $$k < a < b$$. The case where $$k \geq a$$ is once again left as an exercise.

More generally, we can show that at any given time, the current sample is a random sample of $$k$$ elements out of all elements seen so far. The proof is by induction on $$n$$, the number of elements seen so far. The base case $$n = k$$ is clear.

Now suppose that we know the claim for $$n$$. Thus after seeing $$n$$ elements, we have a random sample $$S$$ of $$k$$ elements out of these $$n$$ elements. Now we are seeing a new element $$x$$. With probability $$k/(n+1)$$, we remove a random element from $$S$$ and replace it with $$x$$.

The probability that the chosen sample is a specific subset of $$k$$ elements out of the first $$n$$ elements is thus $$\frac{1}{\binom{n}{k}} \cdot \frac{n+1-k}{n+1} = \frac{1}{\binom{n+1}{k}}.$$ Now suppose $$T$$ is a subset of $$k$$ elements out of the first $$n+1$$ elements which contains the new element $$x$$. There are $$n-(k-1)$$ choices for $$S$$, resulting from adding an element $$y$$ to $$T - x$$. The probability that $$x$$ replaced $$y$$ rather than some other element is $$1/(n+1)$$, and altogether the probability that $$T$$ is the chosen sample is $$\frac{n-k+1}{\binom{n}{k}} \cdot \frac{1}{n+1} = \frac{1}{\binom{n+1}{k}}.$$ (In fact, this calculation must come out to be $$1/\binom{n+1}{k}$$, since all sets $$T$$ are equiprobable; but it is still instructive to see it.)