Arnott
Reputation
Top tag
Next privilege 50 Rep.
Comment everywhere
3
Impact
~132 people reached

• 0 posts edited

# 21 Actions

 Nov 22 comment Estimate number of distinct items @leonbloy, downvote? Nov 22 awarded Commentator Nov 22 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. Nov 22 revised Estimate number of distinct items added 416 characters in body Nov 22 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. Nov 22 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. Nov 22 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. Nov 22 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. Nov 22 awarded Student Nov 22 revised Estimate number of distinct items deleted 116 characters in body Nov 22 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. Nov 22 revised Estimate number of distinct items added 17 characters in body Nov 22 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? Nov 22 revised Estimate number of distinct items added 128 characters in body Nov 22 comment Estimate number of distinct items @joriki. Oh dear. Do you know how to fix it? Nov 22 comment Estimate number of distinct items @joriki, yes. Sorry that wasn't clear. Nov 22 revised Estimate number of distinct items added 9 characters in body Nov 22 revised Estimate number of distinct items added 10 characters in body Nov 22 awarded Editor Nov 22 revised Estimate number of distinct items edited tags