# Estimating the number of distinct elements

Need to understand "intuition" part. It does not make sense to me why $log(d)$ is a good approximation.

We have a stream $\sigma = \{a_1, ..., a_n\}$, with each $n \in [n]$, and this implicitly defines a frequency vector $F = {f_1, ..., f_n}$. Let $d = |\{j : f_j > 0$}| be the number of distinct elements that appear in $\sigma$.

For an integer $p > 0$, let $zeros(p)$ denote the number of zeros that the binary representation of $p$ ends with. Formally,

$zeros(p) = max\{i : 2^{i}$ divides $p\}$

Algorithm:

Initialize:

1. Choose a random hash function $h$: $[n] \mapsto [n]$ from a 2-universal family;

2. z $\leftarrow$ 0;

Process $j$: 3. if $zeros(h(j)) > z$ then $z \leftarrow zeros(h(j))$

Output: $2^{z+\frac{1}{2}}$

The basic intuition here is that we expect $1$ out of $d$ distinct tokens to hit $zeros(h(j)) \geq log(d)$, and we don't expect any tokens to hit $zeros(h(j)) >> log(d)$. Thus the max value of $zeros(h(j))$ over the stream - which is what we maintain in $z$ - should give us a good approximation to $log(d)$.

• We expect references to fulfill the minimal scholarly requirements and be as robust over time as possible. Please take some time to improve your post in this regard. We have collected some advice here. – Raphael Mar 8 '16 at 14:15
• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! – Raphael Mar 8 '16 at 14:15
• 1. Please attribute your sources. You give a very long quotation. Is that a quote from some source? If so, where? Copying without attribution amounts to plagiarism, which isn't cool. 2. What is your question? I don't see any question here, merely a list of declarative statements. Can you articulate a specific, answerable question? – D.W. Mar 9 '16 at 4:58

The idea is that the hash function $h$ maps elements to random elements. Now think about the likelihood that the last $k$ digits of a random number are $0$. There's a 50/50 chance that the number ends with $0$, but it becomes more and more unlikely as you increase the number of zeroes at the end. For $000$, the probability is already down to $\frac{1}{8}$, and for ten zeroes it's around one in one thousand. So it's very unlikely that any one random number has a lot of zeroes at the end.
So what's the maximum number of zeroes can you expect when you take $d$ random numbers? It's unlikely that one of the $d$ numbers ends in loads of zeroes, but the probabilities are so that it's likely that at least one has $\log{d}$ zeroes.