2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thank you for the explanation $\endgroup$
    – Sushovan
    Mar 11 at 6:24
  • $\begingroup$ Glad to be of help ! $\endgroup$ Mar 11 at 6:28
1
$\begingroup$

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

$\endgroup$

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.