Question

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

Short answer

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

Step-by-step solution

Step 1:Given information

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$

Step 2:Explanation

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$

Step 3:Expected value

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$

Final answer

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