Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It only takes a minute to sign up.
Sign up to join this community
Given $X$ has a binomial distribution $B(n,p)$. Now I take $k$ samples from $X$. What's the expected value of how many distinct values I sampled?
My rather futile approach was: Given after $k$ draws, I have drawn the set $M_k$ of values. The probability of now drawing a previously undrawn value is $$a_k := 1-\sum_{v\in M_k}P(X = v).$$ I think I could compute $E[a_k]$ from $B(n,p)$. However, even then, how do I use this to answer the original question about the cardinality of $M_k$?
Let us reformulate and generalize a bit. Say we have a collection of $n$ objects ($n \ge 1$). We sample with replacement from this collection $k$ times. Each time the probability of selecting object $i$ is $p_i$. How many distinct objects do we see in the sample? If you for the $p_i$'s replace the binomial probabilities you recover your problem.
One interpretation of this reformulation is via the birthday problem, what is expected value of distinct birthdays present in a party of $k$ people ($n=366$). Introduce indicator variables $I_1, \dotsc, I_n$, $I_i=1$ if object $i$ was seen, 0 else. Then the number of distinct objects is $I=\sum_1^n I_i$ with expectation $$ \DeclareMathOperator{\E}{\mathbb{E}} \E I = \sum_1^n \E I_i = \sum_1^n (1-p_i^k)=n-\sum_1^n p_i^k $$ Here we used that $\DeclareMathOperator{\P}{\mathbb{P}} \P(I_i=1)=1-\P(I_i=0)=1-p_i^k$.
Returning to the original problem, first we must replace the index set $1,2,\dotsc,n$ with $0,1,2,\dotsc,n$ so the expression becomes $\E I = n+1-\sum_0^n p_i^k$ with $p_i=\left(\binom{n}{i}p^i(1-p)^{n-i}\right)^k$ so $$ \E I = n+1-\sum_0^n \left(\binom{n}{i}p^i(1-p)^{n-i}\right)^k $$ and I will leave for later if that can be simplified.
