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

We have $N$ letters to $N$ different people, and $N$ envelopes addressed to those $N$ people. One letter is put in each envelope at random. Find the mean and variance of the number of letters placed in the right envelope.

Indicator variables are used and eventually the textbook arrives at

$$E(X_i)=\sum_{x_i=0}^{1} x_i f(x_i)$$ $$\text{Var}(X_i)=\frac{1}{N}\left(1-\frac{1}{N}\right)$$ $$E(X_iX_j)=\frac{1}{N(N-1)}$$ $$\text{Cov}(X_i,X_j)=\frac{1}{N(N-1)}$$

I get why this is true, but I don't really get the part where it calculates $\text{Var}(\sum_{i=1}^{N }X_i)$:

$$\text{Var}\left(\sum_{i=1}^{N}X_{i}\right) = \sum_{i=1}^{N}\text{Var}\left(X_{i}\right)+2\sum_{i<j}\text{Cov}(X_{i},X_{j}) = \sum_{i=1}^{N}\frac{1}{N}\left(1-\frac{1}{N}\right)+2\binom{N}{2}\frac{1}{N^{2}(N-1)} \vdots $$

Now wait a moment. How was the $\sum_{i<j}$ part calculated? Is there some identity I don't know? Where did that binomial thingy come from?

share|cite|improve this question

The $\binom{n}{2}$ comes from the number of pairs $i<j$. I think however, that either in the some it should be $\frac{1}{N(N-1)}$ or the $Cov(X_i,X_j)$ should have been $\frac{1}{N^2(N-1)}$

share|cite|improve this answer

Perhaps covariance could have been left out of the game. We defined $X_i$ to be $1$ if letter $i$ is in the right envelope, and $0$ otherwise. Suppose there are $n$ letters. Then $Y$, the number of letters in the right envelope, is given by $Y=X_1+\cdots+X_n$.

It is easy to see that $\Pr(X_i=1)=\frac{1}{n}$. So by the linearity of expectation, $E(Y)=n\cdot \frac{1}{n}=1$.

To calculate $\operatorname{Var}(Y)$, use the fact that $\operatorname{Var}(Y)=E(Y^2)-(E(Y))^2$.

To find $E(Y^2)$, expand out $(X_1+\cdots+X_n)^2$ and use the linearity of expectation. When we expand, we get $X_1^2+\cdots+X_n^2$, plus "mixed" terms.

Since $X_i^2=X_i$, we find that $E(X_1^2+\cdots+X_n^2)=1$.

The mixed terms are of the form $2X_iX_j$, where $i\ne j$. There are $\binom{n}{2}$ of these. We need to find the expectation of $X_iX_j$. This is a Bernoulli random variable. The probability that letter $i$ is in the right envelope is $\frac{1}{n}$. Given that this is the case, the probability that letter $j$ is in the right envelope is $\frac{1}{n-1}$. Thus $\Pr(X_iX_j=1)=\frac{1}{n(n-1)}$, and hence $E(X_iX_j)=\frac{1}{n(n-1)}$.

Multiply by $2$, then by $\binom{n}{2}$. We get $1$. It follows that $E(Y^2)=2$ and therefore $\operatorname{Var}(Y)=1$.

share|cite|improve this answer

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.