Coupon collecting problem

Question

Suppose there are 8 different types of coupons, each coupon has probability 1/8 of being selected. Suppose a total of 6 coupons are collected.

Let: $$ X_i=\begin{cases} 1, \textrm{if a type-i coupon is among the 6 coupons selected}\\ 0, \textrm{otherwise} \end{cases} $$

Let $X$ be the number of different types of coupons in the selected set, so $X = \sum_{i=1}^8 X_i$

How do I calculate the Covariance of ($X_i, X_j$) for $i \ne j$ and the variance of $X$?

I use the formula for Covariance: Cov($X_i, X_j$) = $E[X_i X_j] - E[X_i]E[X_j]$

I found $E[X_i]$ pretty easily, but how would I go about calculating $E[X_i X_j]$?

Answer 1

The only way that the product $X_iX_j=1$ is if both coupons i and j are selected. (Otherwise, either $X_i$ or $X_j$ will be 0, and the product will as well). Thus, $E[X_iX_j]$ is the probability coupons $i$ and $j$ are selected.

To calculate this probability: consider that at first, coupon $i$ has a $\frac{6}{8}$ probability of being selected. Then, conditional on the fact $i$ has already been selected, there is a $\frac{5}{7}$ probability coupon $j$ will be selected (5 coupons to select from 7 remaining). Thus:

$$E[X_iX_j]=E[X_i]E[X_j|X_i=1]=\frac{6}{8}\times\frac{5}{7}=\frac{15}{28}\approx0.535$$

You can test this with a simple line of (for example) R code:

mean(replicate(1e6, all(1:2 %in% sample(8, 6))))
# 0.535139

---

Plug this into the formula for covariance, using $\frac{6}{8}$ as $E[X_i]$ and $E[X_j]$:

$$\mbox{Cov}(X_i,X_j)=E[X_iX_j]-E[X_i]E[X_j]=\frac{15}{28}-\frac{6}{8}\times\frac{6}{8}\approx-0.0268$$