Probability of "At least one" with replacement

243 Views Asked by At

For a given set $S$ with $N$ element: $$S=\{x_1,x_2,x_3,...,x_N\}$$ we create another set $S'$ by choosing randomly $N$ elements from set $S$ with replacement: $$S' = \{x_1,x_1,x_2...,x_N\}$$ What percentage of elements of $S$ will occur at least once in $S'$, on average, if: $N=10$.

What I have tried is the following: To find at least one we have to do

$$P(x) = 1 - (\frac{(N-1)}{N})^N$$

based on this answer.

Now how can I find the percentage of all elements of $S$ that will occur at least once in the $S'$ set?

1

There are 1 best solutions below

7
On

The number of elements of $S$ that appear [at least once] in $S'$ can be written as $$I_1 + \cdots + I_n$$ where $I_j=\begin{cases} 1 & x_j \in S' \\ 0 & \text{otherwise}\end{cases}$.

Then use $E[I_1 + \cdots + I_n] = E[I_1] + \cdots + E[I_n]$. The terms on the right-hand side will be related to the computation you have already done. (It is not clear to me if $n \ne N$ or if you made a typo.)