Before revision:  In this paper we study the intrinsic tradeoff between the space complexity of the sketch and its estimation error in the Random Oracle model.
After revision: Estimating the cardinality (number of distinct elements) of a large multiset is a classic problem in streaming and sketching, dating back to Flajolet and Martin's classic Probabilistic Counting (PCSA) algorithm from 1983. In this paper we study the intrinsic tradeoff between the space complexity of the sketch and its estimation error in the Random Oracle model.