1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

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.