Am I correct in thinking the accuracy of this method has more to do with the distribution in the sample than the algo itself. Meaning, given a 100% unique list of items, how far off would this estimate be?
X <- X \ {a_i}
With probability p, X <- X U {a_i}