# Finding expected number of distinct binomial random variables

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.

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

## 1 Answer

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}

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