<p>Suppose we're sampling a discrete random variable from a distribution f, n times. Is there a simple analytical formulation for the expected number of unique items we obtain, or for the distribution of this number? Is there a name for this characteristic?</p>

<p>This question came up in a practical task: I have a stream of items arriving, every item having several Zipf-distributed parameters, and I'd like to answer queries like "how many items had a parameter equal to x" - I was wondering how feasible it is to just count each parameter value's occurrences (obviously, the space required is exactly what I'm asking about).</p>

CC BY-SA 3.0
2012-10-27T05:45:46.983Z
I found a similar question on math.stackexchange.com http://math.stackexchange.com/questions/41519/expected-number-of-unique-items-when-drawing-with-replacement
jkff
CC BY-SA 3.0
2012-10-27T05:57:10.347Z
The expected number of unique items is easy to calculate, using the linearity of expectation (exercise).
Yuval Filmus
CC BY-SA 3.0
2012-10-27T16:45:32.657Z
as to the algorithmic question: how accurate estimates do you want? a count-min sketch can give you estimates for each value within $\epsilon N$ additive error with probability $1-\delta$, where $N$ is the total number of items. the space requirement is $O(\log(1/\delta)\epsilon^{-1})$ words. the error is pretty miserable if you care about values that occur only a few times, but if you really only care about values that "dominate" the stream, it's good enough
Sasho Nikolov
CC BY-SA 3.0
2012-10-27T20:29:14.877Z
@SashoNikolov - yes, I know, I can use approximations, but I'm wondering how far I can get with exact answers.
jkff
<pr.probability><st.statistics>
Distribution of number of unique items in a sample
jkff
# Distribution of number of unique items in a sample

(Asked by: username_0 on 2012-10-27)

Suppose we're sampling a discrete random variable from a distribution f, n times. Is there a simple analytical formulation for the expected number of unique items we obtain, or for the distribution of this number? Is there a name for this characteristic?

This question came up in a practical task: I have a stream of items arriving, every item having several Zipf-distributed parameters, and I'd like to answer queries like "how many items had a parameter equal to x" - I was wondering how feasible it is to just count each parameter value's occurrences (obviously, the space required is exactly what I'm asking about).

**Tags:** pr.probability, st.statistics
> **Comments:**
> **username_0**: I found a similar question on math.stackexchange.com http://math.stackexchange.com/questions/41519/expected-number-of-unique-items-when-drawing-with-replacement  
> **username_1**: The expected number of unique items is easy to calculate, using the linearity of expectation (exercise).  
> **username_2**: as to the algorithmic question: how accurate estimates do you want? a count-min sketch can give you estimates for each value within $\epsilon N$ additive error with probability $1-\delta$, where $N$ is the total number of items. the space requirement is $O(\log(1/\delta)\epsilon^{-1})$ words. the error is pretty miserable if you care about values that occur only a few times, but if you really only care about values that "dominate" the stream, it's good enough  
> **username_0**: @SashoNikolov - yes, I know, I can use approximations, but I'm wondering how far I can get with exact answers.  

---

## 0 answers

