# How is this sum calculated?

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?

-

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

-

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

-