HyperLogLog leading zeros distribution

Question

I'm reading this article.

In particular I'm having some trouble trying to replicate the results of the first image in that article.

For x=9, the graph says that the probability is 0.20 aprox. But from my calculations I get something different. After some thought I think I may be misinterpreting the idea of the calculation.

First attempt: Doing the sum of a X -> Bin(1024, 1/29), calculating f(X=1)+...+f(X=1024). My calculation equals 0.86 which is not 0.20

Then I thought that maybe he was talking about just having 1 result with 9 leading zeros. This means that from the 1024 numbers, we can have only 1 success in any of the 1024 numbers. Which is 0.27... closer but far from 0.20.

What am doing wrong here?

Answer 1

It looks like you could be more careful. "For x=9, the graph says that the probability is 0.20 approx." In fact, the graph says that probability is slightly less than 0.12.

---

Here is the relevant quote from the article on hyperloglog

This is a plot of probability of having x leading zeros, with 1024 distinct items. You can see that the probability peaks at around x = 10, as expected - but the distribution is quite wide, with x = 9, 11 or 12 being at least half as likely as x = 10. (The distribution peaks 0.5 units higher than expected, so this implies that 2k will overshoot by a factor of 20.5, or about 1.4. This shows up as a correction factor later.)

The probability of having exactly $x$ most leading zeros with 1024 terms is the difference of the probability of have no more than $x$ leading zeros and the probability of have no more than $x-1$ most leading zeros.

$$ P[x] = \left(1-\left(\frac12\right)^x\right)^{1024} -\left(1-\left(\frac12\right)^{x-1}\right)^{1024} $$

In particular, the probability of exactly 9 most leading zeros $P[9]\approx 0.1169$.

Here is a Python program that computes the probabilities shown in the above graph.

P = [0] * 23
for x in range(1, 23):
    P[x] = (1 - 0.5 ** x) ** 1024 - (1 - 0.5 ** (x - 1)) ** 1024
for x in range(4, 23):
    print(x, round(P[x], 4))

Here is its output.

4 0.0
5 0.0
6 0.0
7 0.0003
8 0.0178
9 0.1169
10 0.2326
11 0.2388
12 0.1723
13 0.1037
14 0.0569
15 0.0298
16 0.0153
17 0.0077
18 0.0039
19 0.0019
20 0.001
21 0.0005
22 0.0002

---

By the way, thanks for mentioning such a nice article that explains the hyperloglog algorithm that counts approximately using only $\log\log N$ bits. $\log\log N$ is arguably underestimating, since more powerful hash functions are needed as $N$ grows, which need more space to compute. Even if we add the space used by the has function, hyperloglog algorithm is amazingly ingenious in several ways.