# Coupon collecting problem

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

• This looks rather like a routine bookwork question and should probably carry the self-study tag. How does this question arise? Jan 28, 2015 at 0:56

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

• (1) clearly the covariance should be negative (since selecting $i$ reduces the chances of selecting $j$ - you use up a slot!). (2) 15/28 - 36/64 is not close to 0.285 (and is in fact negative as we'd expect) Jan 28, 2015 at 0:40
• @Glen_b Thanks, corrected- I have no idea how I made such an obvious calculation error! Jan 28, 2015 at 0:49
• +1 with correction. No problem, we all make these kinds of error (I expect I make more than you). Jan 28, 2015 at 0:51