1
$\begingroup$

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.

$\endgroup$
3
  • 4
    $\begingroup$ Let the probability $X=Y=i$ be $\min(p_i,q_i)$. $\endgroup$ Jun 13, 2013 at 5:53
  • $\begingroup$ 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.) $\endgroup$ Jun 13, 2013 at 6:42
  • 3
    $\begingroup$ This is called the total variation distance. $\endgroup$ Jun 13, 2013 at 6:54

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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