# Expected number of different colors selected in k picks from balls of n colors

Problem statement reads like this - There are n different colored balls available in a basket. What is value of expected number of distinct colors selected from k random picks with replacement. I approached the problem in following manner

Considering n = 4, k = 3.
Number of possibilities of selecting 3 different colors is $$\frac{4\times3\times2}{4^3}$$.
Number of possibilities of selecting 2 different colors is $$\frac{4\times3\times3}{4^3}$$ (selecting first color, then putting it any of three places, then choosing next color)
Number of possibilities of selecting 1 different color is $$\frac{4}{4^3}$$

This leads me to correct answer however, I'm not sure how to approach the problem when n and k is large like $$10^5$$.

It can easily be solved using indicator variables.

Let $$X_i$$ be an indicator variable that equals $$1$$ if the $$i_{th}$$ color appears in $$k$$ trials, and $$0$$ otherwise

Then $$\Bbb{P}(X_i) = 1 - (\frac{n-1}{n})^k$$

Now the expectation of an indicator variable is just the probability of the event it indicates,

so $$\Bbb{E}(X_i) = \Bbb{P}(X_i) = 1 - (\frac{n-1}{n})^k$$

and by linearity of expectation, which applies even if the variables are not independent,

$$\Bbb{E}(X) = \Bbb{E}(X_1) + \Bbb{E}(X_2) + .... \Bbb{E}(X_n)$$

$$= n\left(1 - (\frac{n-1}{n})^k\right)$$

• Thank you for the explanation Mar 11 '21 at 6:24
• Glad to be of help ! Mar 11 '21 at 6:28

Let $$X_i$$ be the event: the $$i$$-th color was already drawn. The expected value of this event after $$k$$ picks is just the probability that this event happens: $$\mathbb E(X_i)=1-\left(\frac{n-1}n\right)^k.\tag1$$ By the symmetry and linearity of expectation: $$\mathbb E\left(\sum_iX_i\right)=\sum_i\mathbb E(X_i)= n\left[1-\left(\frac{n-1}n\right)^k\right].\tag2$$