Geodesic
On the randomness that generates biased samples: The limited randomness approach
Computer Science and Information Systems, Tome 16 (2019) no. 1.

Voir la notice de l'article provenant de la source Computer Science and Information Systems website

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.
Keywords: Biased reservoir sampling, Markov chain, random walk 
@article{CSIS_2019_16_1_a10,
     author = {George Lagogiannis and Stavros Kontopoulos and Christos Makris},
     title = {On the randomness that generates biased samples: {The} limited randomness approach},
     journal = {Computer Science and Information Systems},
     publisher = {mathdoc},
     volume = {16},
     number = {1},
     year = {2019},
     url = {http://geodesic.mathdoc.fr/item/CSIS_2019_16_1_a10/}
}
TY  - JOUR
AU  - George Lagogiannis
AU  - Stavros Kontopoulos
AU  - Christos Makris
TI  - On the randomness that generates biased samples: The limited randomness approach
JO  - Computer Science and Information Systems
PY  - 2019
VL  - 16
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CSIS_2019_16_1_a10/
ID  - CSIS_2019_16_1_a10
ER  - 
%0 Journal Article
%A George Lagogiannis
%A Stavros Kontopoulos
%A Christos Makris
%T On the randomness that generates biased samples: The limited randomness approach
%J Computer Science and Information Systems
%D 2019
%V 16
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CSIS_2019_16_1_a10/
%F CSIS_2019_16_1_a10
George Lagogiannis; Stavros Kontopoulos; Christos Makris. On the randomness that generates biased samples: The limited randomness approach. Computer Science and Information Systems, Tome 16 (2019) no. 1. http://geodesic.mathdoc.fr/item/CSIS_2019_16_1_a10/