Dgdrxrt

In cardinality problem (count-distinct problem) the goal is to estimate the number of unique elements in a set. HyperLogLog is one such algorithm [ref] Another approach is using order statistics, such as what Giroire did in MinCount [ref].

For background, following this [page]

Say we have $n$ iid random variables $X_i sim U(0,1)$ for $i=1,dots,n$. The pdf of the minimum $Y$ and range $R$ for $n>1$ is

$$f_Y(x) = n(1-x)^n-1$$
$$f_R(x) = n(n-1)(1-x)x^n-2$$

We have

$$E[Y]=frac1n+1$$

which, as Giroire also pointed out, we may hope that $1/Y$ may be a good estimate of $n$, but

$$Eleft[frac1Yright]=+ infty$$

Likewise, for the range we have

$$E[R]=fracn-1n+1$$

and we may hope solving for $n$ in terms of observed $r$ may be a good estimator, however

$$Eleft[frac1+R1-Rright]=2n-1$$

Which suggests that a better estimator is then

$$Eleft[frac11-Rright]=n$$

In MinCount Giroire subdivides the (0,1) interval into $m$ buckets of size $1/m$ and finds the (normalized) minimum within each set. This forms the set $M^(k)_i$ (for $k=1$), and derives three different algorithms. For $k=1$ only the logarithm family is valid.

Assuming all $n$ values are uniformly distributed as a first approximation we can make an assumption that exactly $n/m$ are in each bucket, and that each bucket is independent. (They are correlated and the joint distribution across all $m$ buckets should be taken into account, but doing first approximation) From that we can solve for the maximum likelihood estimate of $m$ samples of $Y$

$$hatell(theta,;y)=frac1m sum_i=1^m ln f_Y(y_imidtheta)$$

With $hattheta=frachatnm$ we have a solution for $hatn$ (Labeled subscript 1 for reference)

$$hatn_1 = frac-m^2sum log(1-y_i)$$

Likewise, with same assumptions of equal numbers across buckets and using the expected value of range we could have a second estimate

$$hatn_2 = sum frac11-r_i$$

Question: I know I'm either missing something fundamental or misunderstanding something. Both MinCount and HyperLogLog, and others, use more advanced procedures to estimate cardinality, with HLL using the harmonic means and bias corrections. Is MLE not applicable? Is even using $E[frac11-r_i]$ not valid, although being unbiased?

Even assuming exact counts of $fracnm$ across $m$ buckets, and independence across buckets, the MLE ($hatn_1$) and sum of $frac11-r_i$ ($hatn_2$) seems to perform on par with MinCount for $k=1$ (Logarithm Family) ($hatn_3$) with less complicated algorithm or formulas.

Experiment: $n=10^6$ iid random variables $X_i sim U(0,1)$. Using $m=64$ equally spaced buckets, and estimating $n_1,n_2,n_3$ with same data each. Repeat 10,000 Monte Carlo experiments. Distribution of $n_1,n_2,n_3$ below.