Let $X_i$ be i.i.d. binomial random variables distributed as $B(n,1/4)$. If we consider $m$ such random variables, $X_1,\dots, X_m$, how can we work out the expected number of distinct $X_i$? We can assume $m>n$ and both are large.

  • $\begingroup$ Next time, try to add some personal input. $\endgroup$ – Did Mar 26 '14 at 17:50
  • $\begingroup$ @Did Good point. Will do. $\endgroup$ – user66307 Mar 26 '14 at 19:15

For $0\le k\le n$, define the Bernoulli random variable $U_k$ as follows: $$ U_k = \left\{ \begin{array} &0 & \mbox{if there exists}\ i\ \mbox{such that}\ X_i=k\\ 1 & \mbox{otherwise} \end{array} \right. $$

In other words, $U_k$ is one iff the value $k$ is not assumed by any $X_i$. Note that this happens with probability $$\left(1-\binom{n}{k}\left(\frac 1 4\right)^k\left(\frac 3 4\right)^{n-k}\right)^m.$$

Then the number of distinct $X_i$ will be equal to $$Z:= n-\sum_{k=0}^n U_k$$ and by the linearity of expectation we have: \begin{align} E[Z]&= n-\sum_{k=0}^n E[U_k]\\ &=n-\sum_{k=0}^n \left(1-\binom{n}{k}\left(\frac 1 4\right)^k\left(\frac 3 4\right)^{n-k}\right)^m \end{align}

  • $\begingroup$ That is nice and clean reasoning. Thank you. $\endgroup$ – user66307 Mar 26 '14 at 19:21

Your Answer

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