Arnott
Reputation
Top tag
Next privilege 20 Rep.
Talk in chat
 Nov22 comment Estimate number of distinct items @leonbloy, downvote? Nov22 awarded Commentator Nov22 comment Estimate number of distinct items @leonbloy, Sorry I think I haven't explained this well. I meant fix $n$, (unknown) $N$, $y$ and then consider over all inputs that satisfy those parameters. So if $n=N$ then $E(X) = y$ (actually not quite right as we may have chosen the same position more than once). We can also say it is very unlikely that $N=y$ for example if $y= N/2$, say, as we would have been very likely to have hit a duplicate. Nov22 revised Estimate number of distinct items added 416 characters in body Nov22 comment Estimate number of distinct items @leonbloy, to be a little clearer. We could say something like "$\forall$ inputs, $a' \leq E(X) \leq b'$ and $P(X\geq a) \leq k$ etc." The point is that the probabilistic bounds hold for all possible inputs. Nov22 comment Estimate number of distinct items @leonbloy, there is randomness in the sampling. So for example we can potentially say $P(X \geq a) \leq k$ and $P(X \leq b) \leq k'$ and also $a' \leq E(X) \leq b'$. These bounds would hold no matter what the input looks like. Nov22 comment Estimate number of distinct items @leonbloy, I don't assume the integers are from a particular set. We can just assume that we can tell which are the same and which are different from each other. Nov22 comment Estimate number of distinct items @leonbloy, I would like probabilistic bounds assuming the worst case. As joriki points out these seem to be on the one hand when each symbol occurs the same number of times and on the other when there are $n-(N-1)$ copies of one symbol and one copy of the other $N-1$ symbols. Nov22 awarded Student Nov22 revised Estimate number of distinct items deleted 116 characters in body Nov22 comment Estimate number of distinct items @joriki, the two extreme cases you give seem to give upper and lower bounds for an estimator based on $X$. Maybe it would make more sense to give a confidence interval rather than a single estimate? I don't know how to do that however. Nov22 revised Estimate number of distinct items added 17 characters in body Nov22 comment Estimate number of distinct items @joriki, Does that mean that there is no good estimator for counting the number of distinct elements without knowing this a priori? Nov22 revised Estimate number of distinct items added 128 characters in body Nov22 comment Estimate number of distinct items @joriki. Oh dear. Do you know how to fix it? Nov22 comment Estimate number of distinct items @joriki, yes. Sorry that wasn't clear. Nov22 revised Estimate number of distinct items added 9 characters in body Nov22 revised Estimate number of distinct items added 10 characters in body Nov22 awarded Editor Nov22 revised Estimate number of distinct items edited tags