# Proof for Linearity of Expectation Question It is mentioned that the second line of the proof is from the definition of the Union of Probabilities: I do not understand how that happened. I understand that the first line is the definition of Expectation expanded, but, why are the two random variables being operated by an AND?

It's actually in the first equality where you use (for the first time) that property. From lines 1 to 2 and 2 to 3 they just apply known properties of $\Sigma$ operator. And then from 3 to 4 we apply such a property of probability again. This last one happens because $$\bigcup_j \{Y=j\}$$ (where as explained in the proof $j$ takes values in $R_Y$) equals the whole sample space, and then you can say for any $i\in R_X$ $$\{X=i\}=\{X=i\}\cap \left(\bigcup_j \{Y=j\} \right)=\bigcup_j \big(\{X=i\}\cap\{Y=j\}\big).$$

This explains why (going from 4 to 3) $$P\big(\{X=i\}\big)=P\left(\bigcup_j \big(\{X=i\}\cap\{Y=j\}\big)\right)=\sum_j{P\big(\{X=i\}\cap\{Y=j\}\big)}.$$ (Second term of 4 comes from same argument interchanging $i$ and $j$.)

In addition, at the very beginning they omit the fact that by definition if we call $Z=X+Y$ then $$\mathrm{E}(X+Y)=\mathrm{E}(Z)=\sum_k k\mathrm{P}(Z=k).$$

But $Z=X+Y=k$ happens iff $k=i+j \wedge X=i \wedge Y=j$. Since there might be many $(i,j)$ pairs in $R_X \times R_Y$ such that $i+j=k$, then we can just say that $$\{X+Y=k\}=\bigcup_{i,j/i+j=k} \{X=i \cap Y=j\}$$ and so $$k\mathrm{P}(Z=k)=\sum_i \sum_{j / i+j=k} (i+j)\mathrm{P}(X=i \cap Y=j\})$$.

But since letting $i$ and $j$ take all values in $R_X$ and $R_Y$ respectively accounts for all possible values $k=i+j$, the final formula reduces just to $$\sum_k k\mathrm{P}(Z=k)=\sum_i \sum_j (i+j)\mathrm{P}(X=i \cap Y=j\}).$$

I do not understand how that happened. I understand that the first line is the definition of Expectation expanded, but, why are the two random variables being operated by an AND?

You have two variables, $X,Y$, and wish to perform a weighed sum over all outcomes in the samples space, $\Omega$.   We then partition the sample space by the joint supports of the random variables; thus we are weighting by the probabilities for the conjunction.

\begin{align}\text{In full:}\qquad\\\mathsf E(X+Y) ~&= \sum_{\omega\in\Omega}(X(\omega)+Y(\omega)) \,\mathsf P\{\omega\} \\ &= \sum_{i\in X(\Omega)}\sum_{j\in Y(\Omega)}\mathop{\sum\qquad\quad}_{\omega:(X(\omega)=i )\wedge(Y(\omega)=j)}(X(\omega)+Y(\omega))\, \mathsf P\{\omega\} \\ &= \sum_{i\in X(\Omega)}\sum_{j\in Y(\Omega)}(i+j)\mathop{\sum\qquad\quad}_{\omega:(X(\omega)=i )\wedge(Y(\omega)=j)} \mathsf P\{\omega\} \\ &= \sum_{i\in X(\Omega)}\sum_{j\in Y(\Omega)} (i+j) \,\mathsf P\{\omega:X(\omega)=i~\wedge~ Y(\omega)=j\} \\[3ex]\text{In short:}\quad\\\mathsf E(X+Y) ~ &=\sum_{i}\sum_{j} (i+j)\,\mathsf P(X=i\cap Y=j)\end{align}

Alternatively, you can view it as $\{X+Y=u\} = \bigcup_{i}\{X=i\}\cap\{Y=u-i\}$

So $\sum_{u}(u)\mathsf P\{X+Y=u\}~{=\sum_{u}(u)\sum_{i}\mathsf P\{X=i\}\cap\{ Y=u-i\}\\=\sum_i\sum_j (i+j)\mathsf P\{X=i\}\cap\{Y=j\}}$