There are $k$types of coupons. Independently of the types of previously collected coupons, each new coupon collected is of type$i$with probability $pi$, $\sum _{i=1}^k{p}_i=1$. If n coupons are collected, find the expected number of distinct types that appear in this set. (That is, find the expected number of types of coupons that appear at least once in the set of $n$coupons.)

There are $k$types of coupons. Independently of the types of previously collected coupons, each new coupon collected is of type$i$with probability $pi$,$\sum _{i=1}^k{p}_i=1$

Given:

$k$types of coupon.

Coupons are independently selected

Coupon is of type $i$with probability $p_i$

$\sum _{i=1}^k{p}_i=1$

The number of successes among a fixed number of independent trials with a constant probability of success follows a binomial distribution.

Definition binomial probability:

$P(X=k)=\left(\begin{array}{l}n\\ k\end{array}\right)·p^k·(1-p{)}^{n-k}=\frac{n!}{k!(n-k)!}·p^k·(1-p{)}^{n-k}$

Let us evaluate the definition of binomial probability at $n=n,p=p_i$and $k=0$:

$P($no coupons of type $i)=P(X=0)$$=\left(\begin{array}{l}n\\ 0\end{array}\right)·p_i^0·{\left(1-p_i\right)}^{n-0}$

$=1·1·{\left(1-p_i\right)}^n$

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

Use the Complement rule:

$P\left(A^c\right)=P($not $A)=1-P(A)$

$P($At least one coupon of type $i)=1-P($no coupons of type$i)$

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

The expected value (or mean) is the sum of the product of each possibility $x$(number of types of coupons) with its probability $P\left(x\right)$.

$E($Number of types $)=\sum xP(x)$

$=\sum _{i=1}^{k}1\times \left(1-{\left(1-p_i\right)}^n\right)$

$=\sum _{i=1}^k\left(1-{\left(1-p_i\right)}^n\right)$

$=k-\sum _{i=1}^k{\left(1-p_i\right)}^n$

$E($Number of types$)=$$k-\sum _{i=1}^k{\left(1-p_i\right)}^n$