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$?

  • $\begingroup$ This seems to be a version of a coupon collector problem, search this site. $\endgroup$ – kjetil b halvorsen Aug 1 '17 at 22:22

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.