Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


share|cite|improve this question
up vote 1 down vote accepted

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.

share|cite|improve this answer
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
Indeed! Thanks for the help :) – jamieL Nov 3 '12 at 0:27

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.