19 reputation
3
bio website
location
age
visits member for 1 year, 11 months
seen Nov 22 '12 at 17:51

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