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

George Lagogiannis1, Stavros Kontopoulos2 and Christos Makris3

  1. Department of Agricultural Economics and Rural Development, Agricultural University of Athens
    Iera odos 75, 11855, Athens, Greece
    lagogian@aua.gr
  2. Department of Computer Engineering and Informatics, University of Patras
    26500 Patras, Greece
    kontopou@ceid.upatras.gr
  3. Department of Computer Engineering and Informatics, University of Patras
    26500 Patras, Greece
    makri@ceid.upatras.gr

Abstract

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 correct ness 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.

Key words

Biased reservoir sampling, Markov chain, random walk

Digital Object Identifier (DOI)

https://doi.org/10.2298/CSIS180310015L

Publication information

Volume 16, Issue 1 (January 2019)
Year of Publication: 2019
ISSN: 2406-1018 (Online)
Publisher: ComSIS Consortium

Full text

DownloadAvailable in PDF
Portable Document Format

How to cite

Lagogiannis, G., Kontopoulos, S., Makris, C.: On the randomness that generates biased samples: The limited randomness approach. Computer Science and Information Systems, Vol. 16, No. 1, 205-225. (2019), https://doi.org/10.2298/CSIS180310015L