Simple set cardinality estimation through random sampling

Marco Bressan, Enoch Peserico, Luca Pretto

We present a simple algorithm that estimates the cardinality $n$ of a set $V$ when allowed to sample elements of $V$ uniformly and independently at random. Our algorithm with proba…