2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.)

enter image description here

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.