On the randomness that generates biased samples: The limited randomness approach

摘要

We introduce two new algorithms for creating an exponentially biased sample over a possibly infinite data stream. Such an algorithm exists in the literature and uses O(log n) random bits per stream element, where n is the number of elements in the sample. In this paper we present algorithms that use O(1) random bits per stream element. In essence, what we achieve is to be able to choose an element at random, out of n elements, by sparing O(1) random bits. Although in general this is not possible, the exact problem we are studying makes it possible. The needed randomness for this task is provided through a random walk. To prove the correctness of our algorithms we use a model also introduced in this paper, the limited randomness model. It is based on the fact that survival probabilities are assigned to the stream elements before they start to arrive.