Sublinear finite-precision sampling in a stream

Question

I am looking to sample a single item from a stream such that each item in the stream has an equal probability of being selected. This is a restricted version of the reservoir sampling problem.

On a stream of length $n$, I would like to make $o(n)$ calls to my random number generator (henceforth "RNG"). Additionally, I would like to work in finite precision. Is there a data structure that supports this?

As usual with reservoir sampling, I want to preserve that:

• Each item is selected with equal probability
• The total time used is $O(n)$ with high probability. A Las Vegas algorithm would be just fine
• No more than $O(1)$ machine words and $O(1)$ stream items are stored between stream items arriving
• Only one pass is made over the stream

Results that I know about that do not meet my requirements include:

• The standard reservoir sampling data structure makes $\Omega(n)$ calls to the RNG.

• "Random sampling with a reservoir" by Jeffrey S. Vitter and "Reservoir-sampling algorithms of time complexity $O(n(1 + \log(N/n)))$" by Kim-Hung Li need only $o(n)$ calls to the RNG but use arbitrary precision arithmetic.

• "Sampling in Space Restricted Settings" by Bhattacharya et al. describes a data structure that meets the above criteria but can fail to sample an item with non-zero probability.

• Exact minwise hashing (in which each index in the stream is hashed and the reservoir holds the item at the index with the lowest hash value seen so far) would suffice, but exact minwise hashing families have size at least $e^{n - o(n)}$ according to Theorem 1 of "Min-Wise Independent Permutations" by Broder et al.. Storing a member of the family would require using at least $(\lg e)(n - o(n))$ bits of space between the arrival of stream items.

Answer 1

The strategy will be to use Vitter's algorithm, but replace the arbitrary-precision random number with online generation of the bits of that random number.

Building block: sampling without arbitrary precision arithmetic

Suppose we want to sample a discrete random variable $X$ from a distribution with cdf $F$ (i.e., $F(x) = \Pr[X \le x]$). Then one approach is to sample $y$ uniformly at random from $[0,1]$, find $x$ such that $F(x-1) < y \le F(x)$, and output $x$. This requires arbitrary precision arithmetic.

Here is a variant that avoids the need for arbitrary precision arithmetic, at the cost of making the algorithm a Las Vegas algorithm (so the worst-case running time is unbounded but the expected running time is nicely bounded). Basically, we sample the bits of $y$ one at a time, and stop as soon as we know what answer the prior method would output. At the $b$th stage, we know the first $b$ bits of $y$, i.e., we know $\tilde{y}$ such that $y \in [y, y + 1/2^b)$ and $2^b \tilde{y}$ is an integer. Now, we find $x$ such that $F(x-1) < \tilde{y} \le F(x)$. If $F(x-1) < \tilde{y}$ and $\tilde{y} + 1/2^b \le F(x)$, then we output $x$ and stop. (In this case, we don't know what the exactly value of $y$ is, but we still know it satisfies $F(x-1)< y \le F(x)$, so $x$ is certainly the right answer.) Otherwise, we output nothing and continue, sampling the next bit of $y$.

What's the running time of this procedure? The expected time until termination is $O(\lg n)$, where $n$ is the number of different possible values of $X$. (Why? Because at the $b$th stage, at most $n$ out of the $2^b$ possible values for $\tilde{y}$ will cause us to continue on to the $b+1$th stage. In particular, once $b$ exceeds $\lg n$, each stage has at least a one-half probability of terminating.) So, this gives a Las Vegas algorithm to sample from $X$, with exactly the right distribution, and with $O(\lg n)$ expected bits sampled from the RNG.

Solving your problem

Now we can solve your particular problem. We simply apply Vitter's algorithm (e.g., Algorithm Y), but instead of sampling the random value $\mathscr{S}$ using arbitrary-precision arithmetic, instead use the method described above.

How many random bits do we need? Based on the results in that paper, the expected number of times we need to sample $\mathscr{S}$ is $O(\log n)$, where $n$ is the length of the stream. Also each time we sample $\mathscr{S}$ the expected number of bits we need to sample is $O(\log n)$. Therefore, we'll need $O((\log n)^2)$ bits from the RNG, on average.

Also the total (expected) running time will be $O(n)$, if you use Vitter's efficient algorithms for sampling $\mathscr{S}$ (e.g., Algorithm Y and binary search or Newton's method).