# Covariance within the coat check problem

I'm working on a variant of the coat check problem (each person checks their coat, and at the end of the night each person is handed a random coat) in which each person has a friend who has an identical coat, so in total they are $2n$ people and $2$ coats that they consider 'their coat'.

It seems fairly straight forward, except for one thing - when I'm trying to calculate the variance, (given by $\sum\sum \mathrm{Var}(X_i,X_j)-\mathrm{Var}(X_i)\mathrm{Var}(X_j)$, where $i\neq j$ and $X$ is an indicator variable), I'm calculating $\mathrm{Var}(X_i,X_j)$ as $\frac{2}{2n} \cdot \frac{2}{2n-1}$... What i'm not sure of is if the $E(X_j)=\frac{2}{2n-1}$ is correct; since it does not account for the chance that $X_i$ is the other person with $X_j$'s coat.

Any thoughts?

Thanks!

-

I'm assuming $X_i = 1$ if person $i$ gets a correct coat. If $i$ and $j$ are not friends, then $$E[X_i X_j] = P(X_i=1) P(X_j = 1 | X_i = 1) = \frac{2}{2n} \frac{2}{2n-1}$$ and then $\text{Cov}(X_i, X_j) = E[X_i X_j] - E[X_i] E[X_j]$. Don't forget to do separately the case where $i$ and $j$ are friends.
Indeed, that was my question! (in the case where they are friends it should be $\frac{2}{2n}\cdot\frac{1}{2n-1}$, right? –  jamieL Nov 2 '12 at 17:41
So I'm having a little bit of trouble figuring out what I want to do - would it be proper to say $Var(X) = \sum\sum Cov(X_i,X_j) = \frac{2}{2n}\cdot(\frac{2}{2n-1}\cdot\frac{2n-2}{2n-1}+\frac{1}{2n-1}\cdot\frac{‌​1}{2n-1}) - (\frac{1}{n})^2$, i.e. Pr(first person gets hat)*(Pr(second gets hat and is not a friend)+Pr(second gets hat and is a friend))-$E(X_i)(EX_j)$? Does $E[X_j]$ change when the two are friends? –  jamieL Nov 2 '12 at 18:05
You have to add $Cov(X_i,X_j)$ for all ordered pairs $(i,j)$. There are three cases: $i=j$, $i$ and $j$ are friends, $i$ and $j$ are not friends. How many pairs in each case? –  Robert Israel Nov 2 '12 at 19:28