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

Question

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

Answer 1

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

Answer 2

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