# dismantling the COVs into cases to evaluate $V[X]$

So I was trying to solve the following question and got stuck a little. the question: "The clerk Cirk puts $n$ red letters and $n$ blue letters (in total $2n$ letters) into $n$ envelopes. On each envelope there's an address written, and in total there're $n$ addresses. On each of these letters an address is written - one of $n$ addresses - while each address gets exactly two letters that're designated, 1 red letter and 1 blue letter.

Cirk is a little confused, thus he chooses randomly which of the letters to enter into each envelope. He only pays attention to enter one red letter and one blue letter (without paying attention to the addresses) into each envelope.

Let's mark: X - number of envelopes that at least one of the letters in it is with the correct address (the address on one of the letters or on both of the letters is the same as appears on the envelope). Find E(X), V(X) (find V(X) for n=10)"

So this is what I did:

• let's define for $1\le i \le n$: $X_i=\begin{cases}1 & \text{At least one of the letters of envelope i is inside the correct envelope} \\ 2 & \text{Otherwise}\end{cases}$

• then $X=\Sigma_{i=1}^n X_i$

• the probability space would be $\binom{n}{1}\binom{n}{1}$ for choosing one blue letter and one red letter for the current envelope.

• Then $P(X_i=1)=\frac{\binom{1}{1}\binom{n-1}{1}\times 2 + \binom{1}{1}\binom{1}{1}}{n^2}=\frac{2n-1}{n^2}$

• Then $E(X)=\Sigma_{i=1}^nE(X_i)=n\times P(X_i=1)=2-\frac{1}{n}$

• $V(X_i)=P(X_i=1)\times P(X_i=0)=(\frac{2n-1}{n^2})\times(1-\frac{2n-1}{n^2})=(\frac{19}{100})\times(\frac{81}{100})=0.1539$

• Now from the formula $V(X)=\Sigma_{i=1}^{10} V(X_i) +2\times \Sigma_{i<j} COV(X_i , X_j)$ I need to find all the possible COVs and evaluate them - here I got stuck.

first of all as I understand, there're at most $\binom{10}{2}$ possible cases to choose $X_i$ and $X_j$. Now what I tried is to separate it into cases and evaluate $COV(X_i , X_j)$ for each case:

1. $X_i$ gets the red $i$ correct letter, $X_j$ gets the red $j$ correct letter, $X_i$ gets the blue $j$ letter - there're twice as much these cases for choosing the color for the correct letter.
2. $X_i$ gets the red $i$ correct letter, $X_j$ gets the red $j$ correct letter, $X_i$ gets the wrong blue letter and not the $j$ blue letter. - there're twice as much these cases for choosing the color for the correct letter.
3. $X_i$ gets two correct letters and $X_j$ does get only one correct letter

• let's define for $1\le i \le n$: $X_i=\begin{cases}1 & \text{At least one of the letters of envelope i is inside the correct envelope} \\ 2 & \text{Otherwise}\end{cases}$

You want $X_i$ to equal $0$ if neither letter belongs in that envelope.

• then $X=\Sigma_{i=1}^n X_i$

The MathJax character spacing works better if you use \sum rather than \Sigma.   $X=\sum_{i=1}^n X_i$

• Then $P(X_i=1)=\frac{\binom{1}{1}\binom{n-1}{1}\times 2 + \binom{1}{1}\binom{1}{1}}{n^2}=\frac{2n-1}{n^2}$

• Then $E(X)=\sum_{i=1}^nE(X_i)=n\times P(X_i=1)=2-\frac{1}{n}$

• $V(X_i)=P(X_i=1)\times P(X_i=0)=(\frac{2n-1}{n^2})\times(1-\frac{2n-1}{n^2})=(\frac{19}{100})\times(\frac{81}{100})=0.1539$

• Now from the formula $V(X)=\Sigma_{i=1}^{10} V(X_i) +2\times \Sigma_{i<j} COV(X_i , X_j)$ I need to find all the possible COVs and evaluate them - here I got stuck.

Well,

\begin{align}\mathsf {Cov}(X_i, X_j) ~=~&\mathsf E(X_iX_j)-\mathsf E(X_i)\mathsf E(X_j)\\ =~& \mathsf P(X_i=1, X_j=1)-(\tfrac{2n-1}{n^2})^2\end{align}

Now, to evaluate the probability that both envelopes get at least one correctly addressed letter.

first of all as I understand, there're at most $\binom{10}{2}$ possible cases to choose $X_i$ and $X_j$. Now what I tried is to separate it into cases and evaluate $COV(X_i , X_j)$ for each case:

There are $\big(n(n-1)\big)^2$ ways to select envelopes for the two pairs of distinctly addressed red and blue letters.

There are three places each letter of the two addresses can be: their own envelope, the other address's envelope, or one of the $(n-2)$ remainders.   So we have $\{X_i=1, X_j=1\}$ iff:

• Both red letters select their own envelopes, and the blues go anywhere, in $n(n-1)$ ways.
• One red letter selects the wrong envelope, its blue is correct, and the other blue goes anywhere, in $\tbinom 21\cdot(n-2)\cdot(n-1)$ ways.
• Both blues letters select their own envelope, but neither red letter selects its own envelope such that
• Both red letters select the other's envelope in $1$ way
• Only one selects the other's envelope in $\tbinom 21\cdot(n-2)$ ways
• Neither selects the other's envelope in $(n-2)(n-3)$ ways

...