Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
4  
Let the probability $X=Y=i$ be $\min(p_i,q_i)$. –  Douglas Zare Jun 13 '13 at 5:53
    
Douglas' nice solution is incomplete as you need to show there is a way to fill in the rest of the table with non-negative entries. Let $\tau$ be the sum of $\max(p_i,q_i)-\min(p_i,q_i)$. For $(i,j)$ such that $p_i\gt q_i$ and $q_j\gt q_i$, set the $(i,j)$ entry to $(p_i-q_i)(q_j-q_i)/\tau$. (If that doesn't work, I've misstated it. Something like that definitely works.) –  Brendan McKay Jun 13 '13 at 6:42
3  
This is called the total variation distance. –  Ori Gurel-Gurevich Jun 13 '13 at 6:54
add comment

2 Answers

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.