Suppose $p>q$, $X\sim \text{Bernoulli}(p)$, $Y\sim \text{Bernoulli}(q)$. Couple $X$ and $Y$ to maximise $P(X=Y)$.

Question

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

Answer 1

Here is a simple solution:

Pick a random number $z$ uniformly in $[0,1]$

for $0 \le z<q$ set $X=Y=1$;

for $q \le z<p$ set $X=1,Y=0$;

for $ p \le z \le 1$ set $X=Y=0$.

---

But if you prefer to do it using table you have to complete the following table:

The first row have to has sum equal to $1-q$ and the second one equal to $q$

[Analogously for the columns.]

The digonal entries have to be equal to minimum of the corresponding row and column probability since you want to maximaize $P(X=Y)$

[If you set a value greater than this minimum you have to set a negative value for the other entry!]

So you can complete the table as your professor said.

P.S. My table is transpose of yours.

Answer 2

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.