Suppose $p>q$, $X\sim \text{Bernoulli}(p)$, $Y\sim \text{Bernoulli}(q)$. Couple $X$ and $Y$ to maximise $P(X=Y)$. My professor's solution to this is as follows: "Create a 2 x 2 matrix with the first row (corresponding to $X=0$) summing to $P(X=0)=1-p$, the second row summing to $P(X=1)=p$, the first column ($Y=0$) summing to $P(Y=0)=1-q$ and the second column summing to $P(Y=1)=q$. We want to maximize the sum of the diagonal which is $P(X=Y)$. Since $p > q$, the first diagonal entry can be at most $1 − p$; the second can be at
most $q$. If we write these in we can fill out the rest of the table (below) to get the desired coupling."

The bit I'm confused about is why $p>q$ implies the first diagonal entry can be at most $1-p$? Can someone explain this please? If we want to maximise the sum of the main diagonal then isn't $1-q+p$ better than $1-p+q$ because $p>q \implies 1-p+q<1$ but $1-q+p>1$?

The first diagonal entry is the probability that $X=Y=0$, and we know that both of the following statements are true:


*

*Since $\Pr[X=Y=0] \le \Pr[X=0]$, it is at most $1-p$.

*Since $\Pr[X=Y=0] \le \Pr[Y=0]$, it is at most $1-q$. 


However, $p>q$, so the first constraint is stronger, and we can forget about the second constraint.
Similarly, the second diagonal entry is the probability that $X=Y=1$, and we know that both of the following statements are true:


*

*Since $\Pr[X=Y=1] \le \Pr[X=1]$, it is at most $p$.

*Since $\Pr[X=Y=1] \le \Pr[Y=1]$, it is at most $q$. 


However, $p>q$, so the second constraint is stronger, and we can forget about the first constraint.
This shows that $\Pr[X=Y]$ is at most $1-p+q$. Algebraically, $$\Pr[X=Y] \le \Pr[X=Y=0] + \Pr[X=Y=1] \le (1-p) + q.$$ We need to show that this upper bound is also a lower bound, and that's what the table does.
