How to choose two random variables taking values in a finite space, with given distributions, such that probability that they are equal is maximized? Let $A = \{1, 2,\dots, n\}$, and let $X$ and $Y$ be two random variables on the same space, taking values in $A$, and distributions given by:
$P(X = i) = p_i$, and $P(Y = i) = q_i$, for any $i\in\{1,2,\dots,n\}$.
What is the maximum possible value of $P(X = Y)$?
Basically, we have to choose a good joint distribution of $X$ and $Y$, such that the sum of diagonal entries in the joint distribution table/matrix is maximized. For $n = 2$, this is easy to do, and I get the answer $(1 - |p_1 - q_1|)$. But even for $n = 3$, I am not able to do much. A  solution/strategy for general n would be appreciated.
 A: A slightly complicated, but sometimes illuminating way to see this and fill details from Douglas Zare comment is to look at the prescribed laws for $X$ and $Y$ as sand piles. A joint law of a couple $(X,Y)$ can be seen as a "transport plan" : each probability of an elementary event $(X=i, Y=j)$ is interpreted as the amount of mass the plan says you move from $i$ to $j$.
Now, maximizing the probability of the event $X=Y$ is equivalent to transporting the mass from the distribution given by $(p_i)$ to the one given by $(q_i)$ in a way that maximizes the amount of mass that does not move in the process.
The solution is then obvious: let as much as you can in its initial position (this is $\min(p_i,q_i)$ for each $i$), take out everything that is in excess from the first distribution, and distribute it in any way where you need it so as to realize the distribution $(q_i)$ at the end.
A: Let $C = \Pr(X=Y)$. Then $$\Pr(C)=\sum_i \Pr(X=i \cap Y=i) \leq \sum_i \min(p_i,q_i).$$
Now let's construct a joining of $X$ and $Y$ for which $\Pr(C)= \sum_i \min(p_i,q_i)$.  
Put $c= \sum_i \min(p_i,q_i)$. Assume $c \in ]0,1[$ and consider four independent random variables $\epsilon$, $V$,  $X'$ and $Y'$ whose laws are given by:


*

*$\Pr(\epsilon=1)=1-\Pr(\epsilon=0)=c$

*$\Pr(V=i) = \dfrac{\min(p_i,q_i)}{c}$

*$\Pr(X'=i)= \dfrac{p_i - c \Pr(V=i)}{1-c}$

*$\Pr(Y'=i)= \dfrac{q_i - c \Pr(V=i)}{1-c}$
Set $$X=\begin{cases} V & \text{if }\epsilon=1 \\\ 
X' & \text{if } \epsilon=0 \end{cases}$$
and $$Y=\begin{cases} V & \text{if }\epsilon=1 \\\ 
Y' & \text{if } \epsilon=0 \end{cases}.$$
Then check.
