We have a sequence of elements $D = <a_1,a_2,...a_m>$. Let $a_i$ come from $[n]$. Our goal is to estimate the number of distinct elements in $D$.

We use a simple idea. We have a set $B=${} and we pass through the sequence and add an element $a_i$ to the set $B=$ with probability $p$. And as per this lecture , $\frac{|B|}{p}$ is a good estimator for distinct elements in $D$.

I would like to prove this statement formally.

I can prove a similar estimator for the cardinality of $D$.

If $B$ was a multi-set or a tuple, i.e., repeated elements appear distinctly. Then $\frac{|B|}{p}$ is an estimator for $|D|$.

\begin{align} E[|B|] &= \sum_{i \in [m]}1 \cdot P(a_i \text{ being in B}) \\ &= |D|p \end{align} Hence,

$$|D| = \frac{E[|B|]}{p}$$

But I do not see how this argument works formally for unique elements?



You must log in to answer this question.

Browse other questions tagged .