I believe that standard averages wouldn't necessarily give you the maximum likelihood.
My intuition says that a straight average should give you fairly good results.. although antirez talks a bit about bias in HyperLogLog counts that he's trying to adjust for.
So maybe an average + some bias correction gives you better results?
The issue is that (e.g.) the arithmetic mean would be very influenced by the stats that gave randomly bad results - the very results you are trying to exclude by doing the test multiple times and taking an average.
From the article:
The standard error of HyperLogLog is 1.04/sqrt(m), where “m” is the number of registers used. Redis uses 16384 registers, so the standard error is 0.81%.
My understanding is that the error is very small because you're averaging over 16,000 registers.
Edit: also, I think you want the mean because it'll give you back a precise/fractional power of 2 that is pretty close to the actual count. The median would give you the nearest integer power of two, which is probably not a good estimate of the real count.
Double edit: looks like there's some research around improving averaging by throwing away outliers: http://blog.notdot.net/2012/09/Dam-Cool-Algorithms-Cardinali...
So also, you can combine this idea with the idea of bloom filters (another probabilistic data structure) in a really interesting way. The goal is to have a _lot_ of counters in a fixed amount of space.
First part is to encode your HyperLogLog counter in unary. So each counter generally only takes up a few bits.
Quick unary tutorial: in unary you count with a sequence of 1's (followed by 0 to signify the end of the number). 3 is encoded as 1110. 5 is 111110. 7 is 11111110. You get the idea.
So also, we're just estimating cardinality, not an exact count. We're estimating if we've seen 2^n things... not n things. Counting to a billion is going to be: 1 billion ~= 2^30 ~= 31 bits.
So you can store all these counters in a big array of bits (a bitmap) and index into it using a hash function. As you probably guessed, all these unary counters will end up overlapping each other in weird ways.
But! The cool thing is if you use a bloom filter to insert and retrieve multiple counters using different hash functions.. and then average the results. The more of these probabilistic and messed up counters you average .. the better the results get!
It's kind of opposite of the usual programmer "junk in, junk out" problem. In this case, the more junk you combine, the better the results. Pretty neat huh? :)
I don't have links to the papers behind these ideas sorry. I learnt most of this from a presentation by Alex Sharp at PyCon Au. Edit: found link to talk - http://pyvideo.org/video/1621/big-data-with-python
This article explains some of this stuff a bit better: http://highscalability.com/blog/2012/4/5/big-data-counting-h...