Two uncorrelated random variables both taking only two values are independent Let X and Y be random variables both taking only two values. Show that if they are uncorrelated then they are independent.
 A: Brute-forcing this exercise gets ugly quite fast, so here is a higher level look at the exercise:
Let $X \in \{a,b\}$, $Y \in \{c,d\}$. Our first observation is the following: The marginal distribution of $X$ is fully specified by 1 parameter, namely $\Pr[X=a]$ (since $\Pr[X=b] = 1 - \Pr[X=a]$). Similarly, the marginal distribution of $Y$ is fully specified by 1 parameter, namely $\Pr[Y=c]$. Finally, the joint distribution of $X,Y$ is fully specified by 3 parameters (since its support consists of maximally 4 points).
In fact, beyond the marginal distributions (2 parameters), to specify the joint distribution, it is enough to specify $\Pr[X=a \vert Y=c]$ (the third parameter).
We can see this as follows:
$$ \Pr[X=b \vert Y=c] = 1 - Pr[X=a \vert Y=c]$$
and by Bayes theorem:
$$ \Pr[Y=c \vert X=a] = \frac{\Pr[X=a \vert Y=c]\Pr[Y=c]}{\Pr[X=a]}  $$
And similarly as above we can recover all conditional probabilities.
Of course, here we are interested in the joint distribution and not the marginals, so let's assume these are given. Therefore we can get the joint distribution by finding $\Pr[X=a \vert Y=c]$. In fact, we are given an additional equation, since $X$ and $Y$ are uncorrelated:
$$ E[X]E[Y] = E[XY] $$
The LHS is a constant (since $\Pr[X=a]$, $\Pr[Y=c]$ are known), while the RHS is a linear function of  $\Pr[X=a \vert Y=c]$ (after expanding and using the formulas mentioned above). In other words we have a linear equation in  $\Pr[X=a \vert Y=c]$ .
Nowe we separate the following cases:
Case 1: $X$ or $Y$ is deterministic (e.g. $\Pr[X=a]=1$). Then the above equation is degenerate (i.e. has infinite solutions). But in this case, $X$ and $Y$ are independent anyway.
Case 2: Neither $X$ nor $Y$ are deterministic, then the above linear equation is not degenerate (this actually also takes some more work to show, but e.g. we can either brute-force it or exhibit a dependence structure such that $\Pr[X=a \vert Y=c]$ does not solve the above equation). Thus this linear equation has at most one solution (in fact exactly one solution but we also require the solution to lie in $[0,1]$).
But we actually do know one solution, since the equation holds if $X$ and $Y$ are independent. Thus $\Pr[X=a|Y=c] = \Pr[X=a]$ uniquely solves it and it follows that $X$ and $Y$ must be independent. 
